Розбираємо задачу «Заплутаний острів»

Надрукувати

Умова:

 

 

Відома логічна задача, може бути корисною для програмістів-початківців. Я пообіцяв учасникам i7.juniors детально її пояснити. Давайте розбиратися.

 

Давайте сформулюємо всі логічні запитання, які можна задати аборигену. Це запитання стосуються як самого аборигена, так і місцезнаходження вашої з ним зустрічі:

  1. Ти лицар?
  2. Ти брехун?
  3. Ти хитрун?
  4. Ми в селі лицарів?
  5. Ми в селі брехунів?
  6. Ми в селі хитрунів?

 

Шість запитань. Інші запитання на кшталт «Чи є життя на Марсі» нам не підійдуть, тому що нам треба не просто побалакати, а розв’язати задачу за мінімальну кількість запитань.

 

Далі пропоную розділити задачу на дві проміжні.

 

Перша – допомогти мандрівнику дізнатися, з ким він розмовляє.

Друга – допомогти мандрівнику дізнатися, в якому селі він знаходиться.

 

Першу задачу можна розв’язати, якщо задати аборигену запитання номер три двічі поспіль. Тобто запитати два рази: «Ти хитрун?»

 

Якщо абориген двічі відповість «ні» — перед нами лицар. Якщо абориген відповість двічі «так», то він брехун. Якщо ж він дасть різні відповіді, то це хитрун. В такому випадку нам треба запам’ятати послідовність його відповідей. Тобто, якщо хитрун на запитання «Ти хитрун?» спочатку сказав «так», а потім – «ні», це означає, що спочатку він сказав правду, а потім збрехав. Нам це важливо, тому що, згідно умови задачі, наступний раз хитрун скаже правду. І навпаки.

 

Далі, дізнавшись «характеристику» аборигена, мандрівнику треба дізнатися, в якому селі вони знаходяться.

 

Для цього йому потрібно задати запитання номери чотири і п’ять в будь-який послідовності, а саме:

— Ми в селі лицарів?

—  Ми в селі брехунів?

 

Розглянемо три випадки – коли на ці два запитання відповідають лицар, брехун і хитрун.

 

Нехай перед ним лицар. Тоді мандрівник гарантовано отримає інформацію про своє місцезнаходження за два питання. (якщо на перше питання лицар відповів «так», то вистачить і одного запитання.)

 

Нехай перед ним брехун. Якщо на перше питання брехун відповів «ні», то мандрівник знаходиться в селі лицарів. Якщо на перше питання брехун відповів «так», значить, мандрівник не в цьому селі, і він повинен поставити ще одне запитання, щоб дізнатися, знаходиться він в селі брехунів або в селі хитрунів. Для того щоб гарантовано це визначити, мандрівнику і знадобиться отримати відповідь на друге запитання.

 

Третій варіант. Нехай перед ним хитрун. Запам'ятавши відповіді на попередні два запитання, мандрівник може зрозуміти, чи скаже хитрун в наступний раз правду або він збреше. Якщо прийшов час хитруну казати правду і у відповідь на запитання «Я в селі лицарів?», хитрун скаже «так», то мандрівник якраз в цьому селі. Якщо хитруну прийшов час брехати,  і на запитання «Чи ми в селі лицарів?" він скаже «ні», то мандрівник також в цьому селі. В інших випадках мандрівнику знадобиться ще одне запитання, четверте.

 

Отже, мандрівнику потрібно два запитання, щоб зрозуміти, з ким він розмовляє, і ще два запитання, щоб безумовно зрозуміти, в якому він селі. Всього чотири питання.

 

Нагадаємо які вони:

— Ти хитрун?

— Ти хитрун?

— Ми в селі лицарів?

—  Ми в селі брехунів?

 

Правильна відповідь: 4 запитання.

 

p.s. Маєте інші версії? Чудово! Пишіть в коменти або приходьте на i7.juniors!

p.p.s.  - Мені підказують, що перші два запитання можуть бути звичайними і простими. На кшталт "У людини зазвичай дві руки?" або "Трава зазвичай зелена?". Погоджуюсь ))