Тема: "Рыцари и лжецы"

Задачи о рыцарях и лжецах - разновидность увлекательных  математических задач, в которых фигурируют персонажи:

Лжец (плут, вампир, сумасшедший, оборотень) - человек, всегда говорящий ложь.

Рыцарь (человек, поступающие правдиво и правильно, правдец) - человек, говорящий всегда правду.

Решение подобных задач обычно сводится к перебору вариантов с исключением тех, которые приводят к противоречию.

Существуют задачи с тремя типами персонажей - рыцари, лжецы и нормальные люди (вариант - шпионы). Последние могут как лгать, так и говорить правду.

Задача №1 : По кругу сидят рыцари и лжецы – всего 12 человек. Каждый из них сделал заявление: «Все кроме, быть может, меня и моих соседей – лжецы". Сколько рыцарей сидит за столом, если известно, что лжецы всегда врут, а рыцари всегда говорят правду?

Решение:

Все не могут быть лжецами – тогда все заявления были бы истинными. Значит, есть рыцарь. Все, кроме, быть может, его двух соседей – лжецы. Оба соседа не могут быть лжецами – тогда они сказали бы правду; оба не могут быть рыцарями – тогда бы они солгали. Единственная оставшаяся возможность – один сосед — лжец, другой – рыцарь (то есть два рыцаря рядом, остальные — лжецы) удовлетворяет условиям задачи.

Ответ: 2 рыцаря.

Задача №2 : На острове живут 100 рыцарей и 100 лжецов, у каждого из них есть хотя бы один друг. Рыцари всегда говорят правду, а лжецы всегда лгут. Однажды утром каждый житель произнес фразу «Все мои друзья — рыцари», либо «Все мои друзья — лжецы», причем каждую из фраз произнесло ровно 100 человек. Найдите наименьшее возможное число пар друзей, один из которых рыцарь, а другой — лжец.

Решение: Заметим, что в паре рыцарь-лжец каждый должен сказать, что другой лжец: рыцарь скажет правду, а лжец соврёт, в паре рыцарь-рыцарь оба скажут правду, а в паре лжец-лжец оба скажут неправду. Значит фраза «Все мои друзья — лжецы» употребляется только в парах рыцарь-лжец. Минимальное кол-во пар рыцарь-лжец, когда фразу сказали 100 человек, это 50. Если пар будет меньше, то и фраз тоже будет меньше.

Задача №3 : Перед нами трое людей A, B и C. Один из них рыцарь, другой лжец и третий - нормальный человек  Эти люди  высказывают следующие утверждения.

A: Я нормальный человек.

B: Это правда.

C: Я не нормальный человек.

Кто такие A, B и C?

Решение:  Прежде всего заметим, что A не может быть рыцарем, потому что рыцарь не назвал бы себя нормальным человеком. Следовательно получается что, A - либо лжец, либо нормальный человек. Тогда истинно высказывание человека B. Значит, B - либо рыцарь, либо нормальный человек. Но B не может быть нормальным человеком (так как A - нормальный человек), поэтому B -  это доблестный рыцарь, а C - маленький лжец. Но лжец не может сказать о себе, что он не нормальный человек (так как любой лжец - не нормальный человек), и мы приходим к противоречию. Итак, A не может быть нормальным человеком. Следовательно, A -  хитрый лжец. Это означает, что высказывание человека B ложно, в силу чего B должен быть нормальным человеком (лжецом он быть не может, так как лжец - человек A). Итак, A -  хитрый лжец, а B - нормальный человек. Отсюда мы заключаем, что C -  доблестный рыцарь.

Задача №4 : Двое людей A и B, о которых известно, что каждый из них либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения:

A: B - рыцарь.

B: A - не рыцарь.

Докажите, что по крайней мере один из них говорит правду, но это не рыцарь.

Решение: Эта задача обладает интересной особенностью. Условия ее не позволяют установить, кто из двух островитян говорит правду, не будучи рыцарем: A или B. Мы можем доказать более слабое утверждение: по крайней мере один из двух островитян A и B говорит правду, не будучи рыцарем. Островитянин A либо говорит правду, либо не говорит правду. Докажем два утверждения: 1) если A говорит правду, то он говорит правду, не будучи рыцарем; 2) если A лжет, то B говорит правду, не будучи рыцарем.

1) Предположим, что A говорит правду. Тогда B - рыцарь и, следовательно, говорит правду. Значит, A - не рыцарь. Таким образом, если A говорит правду, то A - лицо, говорящее правду, не будучи рыцарем.

2) Предположим, что A не говорит правду. Тогда B - не рыцарь. Но B должен говорить правду, так как A не может быть рыцарем (ведь A не говорит правду). Следовательно, в этом случае B говорит правду, не будучи рыцарем.

Задача №5 : Трое людей A, B и C, о каждом из которых известно, что он либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения: A:

B по рангу выше, чем C.

B: C по рангу выше, чем A.

Затем у C спрашивают: "Кто старше по рангу - A или B?" Что ответит C?

Решение:  Первый шаг. Прежде всего докажем, что в силу высказывания A островитянин C не может быть нормальным человеком. Действительно, если A - рыцарь, то B - особа более высокого ранга, чем C. Следовательно, B должен быть нормальным человеком, а C - лжецом. Таким образом, в этом случае C - не нормальный человек. Предположим, что A - лжец. Тогда B по рангу не выше C. Следовательно, B - особа более низкого ранга, поэтому B должен быть нормальным человеком, а C - рыцарем. Таким образом, и в этом случае C - не нормальный человек. Предположим, наконец, что A - нормальный человек. Тогда C - заведомо не нормальный человек (так как из трех островитян A, B и C только один – нормальный человек). Итак, C - не нормальный человек.

Второй шаг. При аналогичных рассуждениях из высказывания B можно вывести, что A - не нормальный человек. Таким образом, ни A, ни C не нормальны. Следовательно, B - нормальный человек.

Третий шаг. Поскольку C - не нормальный человек, то он может быть рыцарем или лжецом. Предположим, что он рыцарь. Тогда A - лжец (так как B - нормальный человек). Следовательно, B - особа более высокого ранга, чем A, и C, будучи рыцарем, даст правдивый ответ: "В по рангу выше A". С другой стороны предположим, что C - лжец. Тогда A должен быть рыцарем, поэтому B по рангу не выше A. В этом случае C, будучи лжецом, солгал бы и ответил так: "В по рангу выше A". Таким образом, независимо от того, кто такой островитянин C - рыцарь или лжец, он ответит, что B по рангу выше A