Загадки про рыцарей и лжецов. Задачи о рыцарях и лжецах
Загадки про рыцарей и лжецов. Задачи о рыцарях и лжецах
Задачи о рыцарях и лжецах — разновидность математических задач, в которых фигурируют персонажи:
и его антагонист
Решение подобных задач обычно сводится к перебору вариантов с исключением тех, которые приводят к противоречию.
Существуют задачи с тремя типами персонажей — рыцари, лжецы и нормальные люди (вариант - шпионы). Последние могут как лгать, так и говорить правду (например: самая сложная логическая задача ).
Также существуют целые классы задач того же типа, но с другими персонажами — задачи о пациентах и врачах , задачи об упырях , собранные в частности в книгах математика Рэймонда М. Смаллиана .
На острове живут рыцари и лжецы. Путешественник, встретивший одного из местных жителей, спросил его, кем он является. Что ответит житель?
Путешественник вышел на дорогу, соединяющую город лжецов и город рыцарей. Он хочет узнать, в какой стороне находится каждый из городов. Какой вопрос он должен задать прохожему (не зная, рыцарь он или лжец), чтобы определить это?
Двое людей A и B, о которых известно, что каждый из них либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения:
A: B — рыцарь.
B: A — не рыцарь.
Доказать, что по крайней мере один из них говорит правду, но это не рыцарь.
На острове, население которого составляют только рыцари, всегда говорящие правду, и лжецы, которые всегда лгут, находится НИИ. Каждый из его сотрудников однажды сделал два заявления:
а) В институте нет и десяти человек, которые работают больше меня.
б) По крайней мере сто человек в институте получают зарплату большую, чем моя.
Известно, что нагрузка у всех работников разная, как и зарплата. Сколько человек работает в НИИ?
Один из вариантов задачи о рыцарях и лжецах упоминается в испанском триллере « Западня Ферма ». Также задача подобного типа встречается в фильме « Лабиринт » Джима Хенсона.
Как решать логические задачи про рыцарей и лжецов. ОСТРОВ РЫЦАРЕЙ И ЛЖЕЦОВ
Существует множество хитроумных задач об острове, населенном "рыцарями", всегда говорящими только правду, и лжецами, изрекающими только ложь. Предполагается, что каждый обитатель острова либо рыцарь, либо лжец. Мы начнем с одной хорошо известной задачи этого типа.
3. Трое жителей острова (А, B и C) разговаривали между собой в саду. Проходивший мимо незнакомец спросил у A: "Вы рыцарь или лжец?" Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у B: "Что сказал A?" "А сказал, что он лжец", - ответил B. "Не верьте B! Он лжет! - вмешался в разговор островитянин C. Кто из островитян B и C рыцарь и кто лжец?
Решение. Ни рыцарь, ни лжец не могут сказать: "Я лжец" (высказав подобное утверждение, рыцарь солгал бы, а лжец изрек бы истину). Следовательно, A, кем бы он ни был, не мог сказать о себе, что он лжец. Поэтому B, утверждая, будто A назвал себя лжецом, заведомо лгал. Значит, B - лжец. А так как C сказал, что B лгал, когда тот действительно лгал, то C изрек истину. Следовательно, C - рыцарь. Таким образом, B - лжец, а C - рыцарь. (Установить, кем был A, не представляется возможным.)
4. Предположим, что A говорит: "Или я лжец, или B рыцарь". Кто из двух персонажей A и B рыцарь и кто лжец?
Решение. Предположим, что A - лжец. Тогда высказанное им утверждение ложно. "Перевести" это можно так: неверно, что A - лжец и что B - рыцарь. Таким образом, если бы A был лжецом, то из этого следовало бы, что он не лжец, то есть мы пришли бы к противоречию. Отсюда мы заключаем, что A должен быть рыцарем. Итак, мы установили, что A - рыцарь. Следовательно, его высказывание о том, что выполняется по крайней мере одна из двух альтернатив (1) A - лжец, 2) B - рыцарь), истинно. А поскольку первая альтернатива (А - лжец) ложна, то должна выполняться вторая альтернатива, то есть B - рыцарь.
Таким образом, установлено, что A и B - оба рыцари.
5. Перед нами снова три островитянина A, B и C, о каждом из которых известно, что он либо рыцарь, либо лжец. Двое из них (А и B) высказывают следующие утверждения:
A: Мы все лжецы.
B: Один из нас рыцарь.
Кто из трех островитян A, B и C рыцарь и кто лжец?
Решение. Прежде всего, заметим, что A должен быть лжецом. Действительно, если бы A был рыцарем, то из его высказывания следовало бы, что все трое лжецы. Но тогда A (по предположению, рыцарь) оказался бы лжецом, что невозможно. Следовательно, A - лжец. Но тогда его высказывание ложно и по крайней мере один из трех островитян A, B и C - рыцарь.
Предположим теперь, что B - лжец. Тогда A и B - оба лжецы, поэтому C должен быть рыцарем (так как, по крайней мере, один из трех островитян рыцарь). Это означает, что ровно один из трех островитян рыцарь, и, следовательно, высказывание B истинно, но это невозможно, так как любое высказывание лжеца не истинно. Отсюда мы заключаем, что B должен быть рыцарем.
Итак, мы установили, что A - лжец, а B - рыцарь. Так как B - рыцарь, то его высказывание истинно, поэтому ровно один из трех островитян - рыцарь. Им должен быть B, следовательно, C должен быть лжецом. Итак, A - лжец, B - рыцарь и C - лжец.