Задача 6. Рыцари, лжецы и марсиане

Кто может сидеть рядом

Все говорят одну и ту же фразу «Ты не рыцарь». Она правдива, если сосед — лжец или марсианин, и ложна, если сосед — рыцарь. Посмотрим, кому её может сказать каждый гость.

• Рыцарь говорит правду, значит, его сосед — не рыцарь.
• Лжец лжёт, значит, фраза ложна: его сосед — рыцарь.
• Марсианин говорит правду только марсианам. Соседу-марсианину он сказал правду — всё в порядке. Любому другому соседу он солгал, значит, этот сосед — рыцарь.

Соседи говорят фразу друг другу, поэтому каждую пару проверяем с обеих сторон:

• рыцарь и рыцарь — нельзя: рыцарь сказал бы неправду;
• рыцарь и лжец — можно;
• рыцарь и марсианин — можно;
• лжец и лжец — нельзя: лжец говорит эту фразу только рыцарю;
• лжец и марсианин — нельзя: лжец сказал бы марсианину правду;
• марсианин и марсианин — можно.

Почему начинаем с пар: каждое высказывание здесь — о соседе. Когда ясно, кто с кем может сидеть, задача о словах превращается в задачу о рассадке.

Стол распадается на звенья

Из шага 1 следует: рыцари не сидят рядом; у лжеца оба соседа — рыцари; рядом с марсианином сидят только рыцари и марсиане.

Хотя бы один рыцарь за столом есть. Иначе не было бы и лжецов: лжецу нужны соседи-рыцари. А лжецов по условию больше, чем марсиан, — значит, хотя бы один лжец есть.

Разрежем стол перед каждым рыцарем. Получатся звенья: рыцарь и все, кто сидит после него по часовой стрелке до следующего рыцаря (если рыцарь один, то звено одно — весь стол). Кто может оказаться в звене после рыцаря? Второго рыцаря рядом с ним нет, значит, следом сидит лжец или марсианин. Если лжец, то за ним снова рыцарь — звено на этом кончается. Если марсианин, то рядом с ним только марсиане и рыцари: до следующего рыцаря подряд сидят одни марсиане.

Итак, звенья бывают только двух видов (см. рисунок):

• «РЛ» — рыцарь и лжец, $2$ места;
• «РМ…⁠М» — рыцарь и один или несколько марсиан подряд.

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

Считаем места

Звенья идут друг за другом без пропусков и вместе покрывают весь стол. Поэтому места во всех звеньях вместе дают ровно $13$ — посчитаем их отдельно для каждого вида звеньев.

Каждый лжец сидит в своём звене «РЛ», а в каждом таком звене один лжец. Значит, звеньев «РЛ» столько же, сколько лжецов, и вместе они занимают вдвое больше мест, чем лжецов. Это чётное число.

Всего мест $13$ — число нечётное. Поэтому на звенья с марсианами остаётся нечётное число мест, то есть не ноль: хотя бы одно звено с марсианами есть.

В звене с марсианами один рыцарь, а остальные — марсиане. Значит, такое звено занимает на одно место больше, чем в нём марсиан. Итак, $13$ мест складываются из двух частей:

• звенья «РЛ» — по $2$ места на каждого лжеца;
• звенья с марсианами — все марсиане и ещё по одному рыцарю на каждое такое звено.

Теперь вспомним условие: лжецов больше, чем марсиан. Предположим, что марсиан $4$ или больше. Тогда лжецов хотя бы $5$, и звенья «РЛ» занимают не меньше $2\cdot5=10$ мест. Звенья с марсианами занимают не меньше $4+1=5$ мест: в них не меньше $4$ марсиан и хотя бы один рыцарь. Всего получается не меньше $10+5=15$ мест, а за столом их только $13$. Значит, марсиан $1$, $2$ или $3$.

Один, два или три марсианина

Марсиан мало, поэтому переберём все способы разбить их на звенья. Для каждого способа посчитаем места в звеньях с марсианами (см. рисунок). Остальные места заняты звеньями «РЛ», поэтому их число должно быть чётным — по $2$ места на каждого лжеца.

Один марсианин. Звено «РМ» занимает $2$ места, на звенья «РЛ» остаётся $13-2=11$ — нечётное число. Не подходит.

Два марсианина.

• Одно звено «РММ»: $3$ места, остаётся $13-3=10$ мест — это $5$ звеньев «РЛ», то есть $5$ лжецов.
• Два звена «РМ»: $4$ места, остаётся $13-4=9$ — нечётно, не подходит.

Три марсианина.

• Одно звено «РМММ»: $4$ места, остаётся $9$ — нечётно, не подходит.
• Звенья «РМ» и «РММ»: $5$ мест, остаётся $13-5=8$ мест — это $4$ звена «РЛ», то есть $4$ лжеца.
• Три звена «РМ»: $6$ мест, остаётся $7$ — нечётно, не подходит.

Остались два случая: $5$ лжецов при $2$ марсианах и $4$ лжеца при $3$ марсианах. В обоих лжецов действительно больше: $5>2$ и $4>3$. Значит, лжецов может быть только $4$ или $5$ — других вариантов нет.

Оба варианта возможны

Осталось показать, что такие рассадки существуют. Посадим гостей по кругу и запишем их по звеньям (точки разделяют звенья); последний в строке сидит рядом с первым:

• $5$ лжецов: РЛ · РЛ · РЛ · РЛ · РЛ · РММ — пять звеньев «РЛ» и звено «РММ»;
• $4$ лжеца: РЛ · РЛ · РЛ · РЛ · РМ · РММ — четыре звена «РЛ», звенья «РМ» и «РММ».

Проверим по списку пар из шага 1: рядом сидят только пары «рыцарь — лжец», «рыцарь — марсианин» и «марсианин — марсианин», а они все разрешены. Рыцарей в обеих рассадках по $6$, и гостей ровно $13$: $6+5+2=13$ и $6+4+3=13$. Лжецов больше, чем марсиан, — значит, оба ответа возможны.