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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Примечания

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

См. также

• Логика
• Популяризация науки

Ссылки

• [web.archive.org/web/20030329201720/ntl.narod.ru/logic/smullyan/name/p3.html/ Рэймонд М. Смаллиан «Рыцари и лжецы»]
• [www.xkcd.ru/246/ XKCD — шутка про класс задач «Рыцари и лжецы»]

Отрывок, характеризующий Задачи о рыцарях и лжецах

Ход рассуждения руководителя совести был следующий. В неведении значения того, что вы предпринимали, вы дали обет брачной верности человеку, который, с своей стороны, вступив в брак и не веря в религиозное значение брака, совершил кощунство. Брак этот не имел двоякого значения, которое должен он иметь. Но несмотря на то, обет ваш связывал вас. Вы отступили от него. Что вы совершили этим? Peche veniel или peche mortel? [Грех простительный или грех смертный?] Peche veniel, потому что вы без дурного умысла совершили поступок. Ежели вы теперь, с целью иметь детей, вступили бы в новый брак, то грех ваш мог бы быть прощен. Но вопрос опять распадается надвое: первое…
– Но я думаю, – сказала вдруг соскучившаяся Элен с своей обворожительной улыбкой, – что я, вступив в истинную религию, не могу быть связана тем, что наложила на меня ложная религия.
Directeur de conscience [Блюститель совести] был изумлен этим постановленным перед ним с такою простотою Колумбовым яйцом. Он восхищен был неожиданной быстротой успехов своей ученицы, но не мог отказаться от своего трудами умственными построенного здания аргументов.
– Entendons nous, comtesse, [Разберем дело, графиня,] – сказал он с улыбкой и стал опровергать рассуждения своей духовной дочери.


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