Задача 2.3. Рыцари и лжецы во время эпидемии

Кто сейчас говорит правду

Слова «рыцарь» и «лжец» в условии называют вид жителя, а не то, говорит ли он сейчас правду. Болезнь меняет только поведение: больной рыцарь остаётся рыцарем, но теперь лжёт. Поэтому теперь жители бывают четырёх видов, и для каждого нужно понять, говорит ли он сейчас правду:

• здоровый рыцарь говорит правду, а больной рыцарь лжёт;
• здоровый лжец лжёт, а больной лжец говорит правду.

Итак, правду сейчас говорят здоровый рыцарь и больной лжец, а лгут больной рыцарь и здоровый лжец (рисунок ниже).

Это деление понадобится во всём решении: чтобы проверить чьи-то слова, важно не то, рыцарь житель или лжец, а говорит ли он правду сейчас. Додуматься до этого помогает само условие: оно предупреждает, что, говорят ли Альфа и Бета правду, «зависит от диагноза».

Теперь о вопросе задачи. Лекарство спасает только больного рыцаря и смертельно для всех остальных. Значит, дать его можно лишь тому, кто наверняка больной рыцарь, а точно нельзя — тому, кто наверняка им не является. Альфа и Бета знают диагнозы друг друга, поэтому каждый из них говорит о том, что точно знает.

Когда слова Альфы и Беты неверны

Прежде чем рассуждать, точно выясним, когда каждое высказывание верно, а когда нет.

Слова Альфы «мы оба рыцари и оба больны» — это четыре утверждения сразу: Альфа — рыцарь, Бета — рыцарь, Альфа болен, Бета болен. Они верны, только если верны все четыре, то есть оба — больные рыцари. Если не выполнено хотя бы одно условие, слова Альфы неверны.

Слова Беты «по крайней мере, один из нас — здоровый лжец» верны, если здоровым лжецом оказался хотя бы один из двоих. Неверны они только тогда, когда ни Альфа, ни Бета не является здоровым лжецом.

Это понадобится дальше: мы будем предполагать, что кто-то лжёт, и делать выводы из того, что его слова неверны. Здесь легко ошибиться: «неверно, что оба — больные рыцари» вовсе не значит «оба — здоровые лжецы». Например, если Альфа — больной рыцарь, а Бета — здоровый рыцарь, три условия из четырёх выполнены, но слова Альфы всё равно неверны.

Альфа лжёт

Предположим, что Альфа говорит правду. Тогда его слова верны, то есть оба — больные рыцари. В частности, сам Альфа — больной рыцарь. Но больной рыцарь лжёт (шаг 1). Выходит, Альфа одновременно говорит правду и лжёт — противоречие.

Значит, Альфа лжёт. Лгут только больной рыцарь и здоровый лжец, поэтому Альфа — больной рыцарь или здоровый лжец. А его слова неверны: оба больными рыцарями быть не могут.

Почему начать стоит с Альфы? Если его слова верны, они называют диагноз самого Альфы, а этот диагноз заставляет его лгать. Высказывание «опровергает само себя» — это стоит проверить первым. Заметь, что диагноз Беты нам ни разу не понадобился: довод работает при любом из четырёх. Всего сочетаний диагнозов $4\cdot4=16$, и этот шаг сразу вычёркивает $8$ из них — все, где Альфа говорит правду.

Бета говорит правду

Теперь предположим, что Бета лжёт. Тогда:

• Бета — больной рыцарь или здоровый лжец (только они лгут);
• его слова неверны, то есть среди них двоих нет здорового лжеца.

Раз Бета не здоровый лжец, он больной рыцарь. Альфа по шагу 3 — больной рыцарь или здоровый лжец; здоровым лжецом он быть не может, значит, и он больной рыцарь. Но тогда оба — больные рыцари, и слова Альфы верны. А в шаге 3 мы выяснили, что Альфа лжёт и его слова неверны. Противоречие.

Значит, Бета говорит правду: Бета — здоровый рыцарь или больной лжец. Почему стоило проверить именно «Бета лжёт»: ложь Беты сразу запрещает здоровых лжецов, а без них у Альфы остаётся один-единственный диагноз. Этот довод вычёркивает ещё $4$ сочетания — те, где лгут оба.

Здоровый лжец — это Альфа

Бета говорит правду, поэтому его слова верны: хотя бы один из двоих — здоровый лжец. Сам Бета — здоровый рыцарь или больной лжец, то есть не здоровый лжец. Значит, здоровый лжец — Альфа. Так вычеркнуты ещё $2$ сочетания: те, где Альфа — больной рыцарь.

Остались два варианта. Рассуждение показало только, что других нет, поэтому проверим каждый:

• Альфа — здоровый лжец, Бета — здоровый рыцарь. Альфа лжёт, и его слова неверны: Альфа не рыцарь. Бета говорит правду, и его слова верны: Альфа — здоровый лжец.
• Альфа — здоровый лжец, Бета — больной лжец. Альфа снова лжёт и говорит неверное (он не рыцарь). Больной лжец Бета говорит правду, и его слова снова верны.

В обоих вариантах никто себе не противоречит. Значит, возможны оба, и по условию нельзя узнать, какой из них на самом деле. На рисунке ниже — все $16$ сочетаний и шаги, которые их вычеркнули.

Кому давать лекарство

Лекарство спасает только больного рыцаря. Альфа — здоровый лжец, и лекарство его убьёт. Бета — здоровый рыцарь или больной лжец. Какой именно, мы не знаем, но в обоих случаях он не больной рыцарь, и лекарство убьёт и его. Больной лжец к тому же выздоровеет сам.

Значит, лекарство не нужно никому, а давать его нельзя ни Альфе, ни Бете. То, что диагноз Беты так и остался неизвестным, на ответ не влияет: важно лишь, что больного рыцаря нет ни в одном из возможных вариантов.