Лицарі та Шахраї

Лицарі та Шахраї — тип логічних загадок винайдений Реймондом Смалліаном.

На вигаданому острові, всі мешканці якого або лицарі, які завжди кажуть правду, або шахраї, які завжди брешуть. Загадки включають відвідувача острова, який зустрічається з маленькими групами мешканців. Зазвичай метою відвідувача є визначити типи остров'ян через їхні твердження, хоча деякі загадки потребують виведення інших фактів. Також завданням може бути визначити запитання на так/ні, яке відвідувач може запитувати з метою розкрити те, що йому потрібно знати.

Ранній приклад загадок цього типу включав трьох мешканців на яких посилались як на A, B і C. Відвідувач запитує в A до якого типу він відноситься, але не чує його відповідь. Тоді B каже "A сказав, що він брехун" і C каже "не вір B: він бреше!" Для розв'язання цієї загадки зауважте, що жоден мешканець не може сказати, що він шахрай. Тож твердження B є неправдивим, тобто він брехун, що робить твердження C правдою, тобто він лицар. Звідси відповідь A однозначно була "Я лицар", і за допомогою наданих даних неможливо визначити лицар A чи ні.

В деяких різновидах, мешканці дають почергово правдиві та брехливі відповіді, або звичайні люди, які кажуть те, що забажають (Як у випадку загадки Лицар/Шахрай/Шпигун). Подальше ускладнення полягає в надання мешканцям можливості давати відповіді на рідній мові, і відвідувач знає, що «бел» і «де» значать «так» і «ні», але не знає яке саме «так», а яке «ні». Ці типи загадок головно вплинули на те, що ми знаємо як «найскладніша логічна задача».

Декілька прикладів загадок типу «Лицарі та Шахраї» ред.

Великий клас простих логічних загадок може бути розв'язаним із використанням законів Булевої алгебри і таблиць істинності. Знайомство з булевою алгеброю і її процесом спрощення допоможе в розумінні наступних прикладів.

Василь і Григір є постійними мешканцями острова лицарів і шахраїв.

Питання 1 ред.

Василь каже: Ми обидва шахраї.

Хто є хто?

Питання 2 ред.

Тут подається, мабуть, найвідоміша з цього типу загадок:

Василь і Григір стоять на розгалуженні дороги. Відомо, що один з них лицар, а другий шахрай, але невідомо хто саме. Також відомо, що одна дорога веде до смерті, друга до свободи. Чи можете ви визначити з допомогою одного запитання яка дорога веде до свободи?

Розв'язок для питання 1 ред.

Василь шахрай, а Григір лицар.

Василь твердить, що "Василь і Григір шахраї."

Якщо Василь лицар, він не зміг би сказати, що він шахрай бо він не може брехати. Те що Василь шахрай робить його твердження брехнею. Тоді хтось з них лицар, або обидва вони лицарі. Ми вже знаємо, що Василь не може бути лицарем, тоді Григір має бути лицарем.

Розв'язок для питання 2 ред.

Існує декілька шляхів для розв'язання. Один з них наступне запитання: "Чи скаже мені другий, що твій шлях веде до свободи?"

Зауважимо, що попередній розв'язок вимагає знання кожного про тип другого. Другий розв'язок полягає в запитанні кожного з них, "Якою буде твоя відповідь, якщо я запитаю тебе чи веде твій шлях до свободи?"

Іще одним варіантом є запитання: "Чи вірне одне з наступних запитань? Ти Лицар і одночасно цей шлях веде до свободи; або ти шахрай і це не шлях до свободи". Додаткові різновиди запитань можна знайти за допомогою булевої алгебри.

Література ред.

George Boolos, John P. Burgess, Richard C. Jeffrey, Logic, logic, and logic (Harvard University Press, 1999).