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