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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Ранній приклад загадок цього типу включал трьох мешканців на яких посилались як на на 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).

Посилання[ред.ред. код]