Задачи о рыцарях и лжецах
Задачи о рыцарях и лжецах — разновидность математических задач, в которых фигурируют персонажи:
- Лжец (плут, вампир, сумасшедший, оборотень, упырь) — человек (или иное существо), всегда говорящий ложь.
и его антагонист
- Рыцарь (человек, правдец), всегда говорящий правду.
Решение подобных задач обычно сводится к перебору вариантов с исключением тех, которые приводят к противоречию.
Существуют задачи с тремя типами персонажей — рыцари, лжецы и нормальные люди (вариант - шпионы). Последние могут как лгать, так и говорить правду (например: самая сложная логическая задача).
Также существуют целые классы задач того же типа, но с другими персонажами — задачи о пациентах и врачах, собранные в частности в книгах математика Рэймонда М. Смаллиана.
Примеры
На острове живут рыцари и лжецы. Путешественник, встретивший одного из местных жителей, спросил его, кем он является. Что ответит житель?
Путешественник вышел на дорогу, соединяющую город лжецов и город рыцарей. Он хочет узнать, в какой стороне находится каждый из городов. Какой вопрос он должен задать прохожему (не зная, рыцарь он или лжец), чтобы определить это?
Двое людей A и B, о которых известно, что каждый из них либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения:
A: B — рыцарь.
B: A — не рыцарь.
Доказать, что по крайней мере один из них говорит правду, но это не рыцарь.
На острове, население которого составляют только рыцари, всегда говорящие правду, и лжецы, которые всегда лгут, находится НИИ. Каждый из его сотрудников однажды сделал два заявления:
а) В институте нет и десяти человек, которые работают больше меня.
б) По крайней мере сто человек в институте получают зарплату большую, чем моя.
Известно, что нагрузка у всех работников разная, как и зарплата. Сколько человек работает в НИИ?
Один из вариантов задачи о рыцарях и лжецах упоминается в испанском триллере «Западня Ферма». Также задача подобного типа встречается в фильме «Лабиринт» Джима Хенсона.
Примечания
- Практически всегда в этих задачах рыцари и лжецы могут говорить лишь «да» или «нет» (исключаются варианты типа «невозможно дать ответ» или «не знаю»), сообщая таким образом один бит информации.
- Парадокс лжеца обычно игнорируется в этих задачах. В редких случаях указывается, что «все спрашиваемые должны быть в состоянии ответить на вопрос».
- В просторечии рыцаря время от времени называют «правдецом».
- Также в таких задачах могут присутствовать «хитрецы», они же «шутники», «обычные люди», «шпионы». Такие персонажи могут лгать или говорить правду — на своё усмотрение (как правило, из двух вопросов «шпион» на один отвечает верно, на другой — нет).