Задачи о рыцарях и лжецах

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

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

и его антагонист

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

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

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

Также существуют целые классы задач того же типа, но с другими персонажами — задачи о пациентах и врачах, задачи об упырях, собранные в частности в книгах математика Рэймонда М. Смаллиана.

Примеры

На острове живут рыцари и лжецы. Путешественник, встретивший одного из местных жителей, спросил его, кем он является. Что ответит житель?

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

Двое людей A и B, о которых известно, что каждый из них либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения:
A: B — рыцарь.
B: A — не рыцарь.
Доказать, что по крайней мере один из них говорит правду, но это не рыцарь.

На острове, население которого составляют только рыцари, всегда говорящие правду, и лжецы, которые всегда лгут, находится НИИ. Каждый из его сотрудников однажды сделал два заявления:
а) В институте нет и десяти человек, которые работают больше меня.
б) По крайней мере сто человек в институте получают зарплату большую, чем моя.
Известно, что нагрузка у всех работников разная, как и зарплата. Сколько человек работает в НИИ?

Один из вариантов задачи о рыцарях и лжецах упоминается в испанском триллере «Западня Ферма». Также задача подобного типа встречается в фильме «Лабиринт» Джима Хенсона.