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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

Примеры[править | править вики-текст]

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

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

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

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

Один из вариантов задачи о рыцарях и лжецах упоминается в испанском триллере «Западня Ферма».

Примечания[править | править вики-текст]

  • Практически всегда в этих задачах рыцари и лжецы могут говорить лишь «да» или «нет» (исключаются варианты типа «невозможно дать ответ» или «не знаю»), сообщая таким образом один бит информации.
  • Парадокс лжеца обычно игнорируется в этих задачах. В редких случаях указывается, что «все спрашиваемые должны быть в состоянии ответить на вопрос».
  • В просторечии рыцаря время от времени называют «правдецом».
  • Также в таких задачах могут присутствовать «хитрецы», они же «шутники» «или обычные люди». Такие персонажи могут лгать или говорить правду - на свое усмотрение.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]