Задача 1. Что услышал журналист

Что на самом деле говорит каждый ответ

Каждый отвечает про одного человека — своего правого соседа. Разберём все четыре случая.

• Рыцарь о рыцаре: говорит правду — «рыцарь».

• Рыцарь о лжеце: говорит правду — «лжец».

• Лжец о рыцаре: правда была бы «рыцарь», а он лжёт — «лжец».

• Лжец о лжеце: правда была бы «лжец», а он лжёт — «рыцарь».

Посмотрим на результат: ответ «рыцарь» звучит ровно тогда, когда говорящий и его сосед одного вида (оба рыцари или оба лжецы), а ответ «лжец» — ровно тогда, когда они разного вида. Сам ответ ничего не говорит о том, кто именно сосед: он говорит лишь, одинаковы ли эти двое (рисунок ниже).

Зачем это нужно: вместо «кто что сказал и солгал ли» мы получили простое правило про каждую пару соседей, и дальше можно рассуждать только про «одинаковые — разные».

По ответам стол восстанавливается с точностью до обмена

Пронумеруем места $1, 2, \ldots, n$ так, чтобы правый сосед сидящего на месте $i$ сидел на месте $i+1$, а правый сосед места $n$ — на месте $1$. Тогда ответ места $i$ — про место $i+1$.

Представим, что журналист знает все ответы и ещё кто сидит на месте $1$. Тогда он восстановит всех: по шагу 1 ответ места $1$ говорит, одного ли вида места $1$ и $2$, значит, вид места $2$ известен; ответ места $2$ даёт вид места $3$; и так по кругу до места $n$. Поэтому под один и тот же набор ответов подходит не больше двух рассадок: одна, в которой на месте $1$ рыцарь, и одна, в которой там лжец.

А теперь возьмём любую рассадку и поменяем всех: каждого рыцаря на лжеца, каждого лжеца на рыцаря. Если двое соседей были одного вида, они остались одного вида; если разного — остались разного. По шагу 1 все ответы сохранились! Значит, под набор ответов подходят ровно две рассадки: сама рассадка и её «обмен» (рисунок ниже). Других нет — мы только что показали, что больше двух быть не может.

Как это заметить: выпиши ответы для маленького стола и поменяй всех — ответы не изменятся. В модели это делает кнопка «Поменять всех», а «Кто мог так ответить?» показывает обе подходящие рассадки.

Лжецов ровно 8: когда журналист всё-таки не справится

Пусть за столом рассадка $S$, в ней ровно $8$ лжецов. По шагу 2 журналист по ответам знает, что за столом либо $S$, либо её обмен $\bar S$. В $\bar S$ лжецами стали все рыцари из $S$, то есть лжецов там $n-8$, а рыцарей — $8$.

Журналисту известно, что лжецов ровно $8$. Если $n-8\ne 8$, в рассадке $\bar S$ лжецов не $8$, она не подходит, и остаётся только $S$ — журналист точно знает, кто лжецы. Но по условию установить лжецов невозможно. Значит, обе рассадки должны содержать по $8$ лжецов: $n-8=8$, то есть $n=16$.

Итак, другого $n$ быть не может. Осталось проверить, что $n=16$ действительно подходит — для этого нужен пример.

Пример: 16 человек

Посадим подряд $8$ рыцарей (места $1$–$8$), а затем $8$ лжецов (места $9$–$16$). Выпишем ответы по шагу 1: у мест $1$–$7$ сосед справа тоже рыцарь — «рыцарь»; место $8$ (рыцарь) о месте $9$ (лжец) — «лжец»; у мест $9$–$15$ сосед — лжец, одного с ними вида — «рыцарь»; место $16$ (лжец) о месте $1$ (рыцарь) — разного вида, «лжец».

Теперь поменяем всех: места $1$–$8$ — лжецы, места $9$–$16$ — рыцари. Ответы те же самые: «лжец» снова только на местах $8$ и $16$ (рисунок ниже). В обеих рассадках ровно $8$ лжецов, и журналист не может сказать, лжецы сидят на местах $1$–$8$ или на местах $9$–$16$. Значит, при $n=16$ описанное в условии возможно.

Заметим, что при $n=16$ годится вообще любая рассадка с $8$ лжецами: её обмен тоже содержит $8$ лжецов и даёт те же ответы.