Dmytro Polovynka

Найскладніша логічна задача і власне рішення

Backup page for:

Свого часу мені задали так звану “найскладнішу логічну задачу”. Я бився над нею три дні і таки розв’язав. Я не впевнений, що саме по собі це - привід для гордості. Та метод вирішення вийшов відмінним від інших і, як на мене, досить милим, тому я таки вирішив ним поділитися. До речі, це - остання задача, на котру я витратив стільки часу.

Умова задачі

Є три боги - бог Правди, бог Брехні та бог Випадковості. Бог Правди завжди говорить правду, бог Брехні завжди бреше, а бог Випадковості видає абсолютно випадкові відповіді, які можуть бути як правдивими, так і брехливими, а то й суперечливими.

Ці боги чудово розуміють українську, але говорити вони можуть лише власною мовою, з якої ми знаємо лише два слова - “да” та “йа”. Одне з них означає “так”, а інше - “ні”, але ми не знаємо яке з них яке.

Треба визначити, який з цих богів - який, задавши загалом три питання, на які можна відповісти або “так”, або “ні”. Одне питання можна задати лише одному богу одночасно. Але обмежень кому задавати які питання - нема, можна хоч задати усі три питання одному богу підряд.

Підходи до розв’язку

Є відома задачка, в якій є два брати, один з них завжди бреше, а інший - завжди каже правду. Ми не знаємо хто з них хто. Треба визначити, яка з двох доріг - вірна, задавши лише одне питання. Розв’язок - треба поставити питання “що б сказав твій брат, якби я його спитав, чи це вірна дорога”. Оскільки брехня та правда разом дають брехню - то треба послухати відповідь і зробити навпаки. Схожий підхід можна також використати тут, але треба його значно ускладнити.

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

Ми також не знаємо, що означає ДА, а що означає ЙА, але насправді тут не все так складно, хоч і заплутано. Ми почнемо саме з цієї проблеми, але поки що забудемо про бога Випадковості, тому що його слова нам нічого не дадуть.

Самозамкнене ДА чи ЙА

Уявимо собі, що ми задали питання “Чи трава - зелена?”. Бог Брехні нам відповість - Ні, а бог Правди - Так. Але оскільки вони кажуть ДА чи ЙА, то це нам мало що дає.

Але уявимо собі, що ми поставимо їм питання так: “Якби я тебе спитав, чи трава - зелена, ти б відповів Так”? Звісно, що бог Правди скаже “Так”, бо він би дійсно відповів Так.

Але що цікаво - бог Брехні нам теж на таке питання відповість “Так”. Чому? Тому що бог Брехні ідеально бреше. Тобто на питання “Чи трава - зелена” він би звісно, відповів “Ні”, але оскільки питання було “… чи ти б відповів Так”, то він, мусячи брехати, скаже “Так”. Тобто “Так, я б відповів Так”, хоча насправді він би відповів “Ні”.

Змусивши бога Брехні брехати про власну брехливу відповідь, ми змусили його говорити правду.

Якщо ж ми поставимо питання: “Якби я тебе спитав, чи трава - зелена, ти б відповів Ні”? Бог Правди скаже Ні, бо насправді він би відповів Так.

Але, знову ж таки, бог Брехні теж відповість Ні, бо на питання чи трава зелена, він би насправді відповів “Ні” - збрехавши про колір трави, але оскільки питання було “…чи ти б відповів Ні”, то він зобов’язаний збрехати, адже якби він сказав “Так”, то він би сказав правду про власну відповідь. Але він не може сказати правду.

Що ми бачимо? На питання про колір трави ми отримуємо відповідь ТАК на ТАК і НІ на НІ не залежно від того, чи це бог Брехні, чи Правди. З цього ми можемо зробити висновок, що якщо ми чуємо відповідь ЙА на питання “чи ти б відповів ЙА” або ДА на питання “чи ти б відповів ДА” - то це істина. А в іншому випадку - брехня. І це не залежить від того, чи ми питаємо це в бога Правди, чи в бога Брехні.

[//]: # (Надалі я не використовуватиму цю формулу, але щойно ми чуємо питання на кшталт “Чи ти - бог Випадковості” ми розуміємо, що наше питання звучить “Якщо я тебе спитаю, чи ти бог Випадковості, то чи ти відповіш ДА”. ДА - це ствердна відповідь, ЙА - заперечна. )

Питання “Якби я тебе спитав …. чи ти б відповів ЙА” є самозамкненим питанням. ЙА буде відповідати істині, ДА буде відповідати брехні. Це - дуже зручно, якщо нам треба знати, де істина, а де - правда, не залежно від того, кого ми це питаємо. Схематично ЙА-ЙА відповідає істинному твердженню і умовно означає “Так”, а ЙА-ДА - брехливому і умовно означає “Ні”.

Приклад - “Якби я тебе спитав, чи ти бог Правди, чи ти б сказав ЙА”. Якщо ми чуємо ЙА - перед нами бог Правди, якщо ми чуємо “ДА”, то це - бог Брехні.

Два питання, які можна поставити невипадковому богу

Бог Випадковості - це той, кого нам треба уникати. Двоє решта - це боги невипадкові. Якби ми знали, де знаходиться хоч якийсь невипадковий бог, ми б могли поставити йому рівно два самозамкнені питання:

Перше: “Чи ти - бог Правди?” - пам’ятаємо, що ми задаємо це формулою “Якби я тебе спитав, чи ти бог Правди, то чи ти б відповів ЙА”. Така формула змушує невипадкового бога говорити правду, або, радше, технічно відповідати так само як бог Правди через самозаперечення. Чуючи ЙА, ми розуміємо, що перед нами - бог Правди, якщо ми чуємо ДА - то це бог Брехні.

Друге: “Чи це (показати на довільного іншого бога) - бог Випадковості?” - знову ж таки, використовуючи попередню формулу, ми змушуємо бога Брехні відповідати так само як бога Правди, тому ЙА на ЙА означає Так, а ДА на ЙА означає Ні. Ми зобов’язані використовувати самозаперечну формулу і надалі, хоч і знаємо, що це за бог, тому що ми все одно не знаємо, що означає ДА, а що означає ЙА.

Після цих двох питань ми точно знаємо де знаходиться який бог. Але як знайти бога “невипадкового”? Яке питання треба поставити першим?

Розташування по колу

Для того, щоб визначити, де знаходить який бог, дуже зручно їх розташувати по колу, щоб кожен бог мав одного бога по правиці, а іншого - по лівиці. Оскільки наші питання можуть бути досить довгими, то ми можемо уявити, що ми можемо почати питання зі слів “Якщо я розташую вас по колу так, що ти (показати на одного бога) стоятимеш тут, ти (показати на іншого бога) стоятимеш по його лівиці, а ти (показати на третього бога) стоятимеш по його правиці, то…”.

Для спрощення, я не буду повторювати ту ж формулу. Просто уявімо собі, що боги розташовані по колу.

Де нема бога Випадковості

Це - найскладніша частина пазла і саме над нею я бився більшість часу. Але рішення цієї проблеми не таке вже й складне.

Треба обрати довільного бога і поставити йому наступне питання:

Якби я спитав бога, що знаходиться ліворуч від бога Випадковості, чи він - бог Випадковості, чи він би сказав ЙА?

Якщо перед нами бог - Випадковості, то його відповідь можна не враховувати взагалі, але з іншого боку - якщо перед нами бог Випадковості, то ми можемо для наступного питання обрати довільного іншого бога. Це ми і зробимо. Але якого бога обрати? На це питання відповімо далі.

Якщо ж перед нами - невипадковий бог, то його відповіді можна довіряти. І тут є кілька можливостей. На відміну від попередніх питань, питання про “Чи він би відповів ЙА” не обов’язково є самозамкненим. Нас не цікавить істинна відповідь, адже і так ясно, що зліва від бога Випадковості знаходиться точно не бог Випадковості. Тому питання ставиться не “що б ти відповів”, а “що б він відповів”. Навіщо нам це треба?

Якщо дуже коротко, то якщо ми спитаємо це питання бога, що є ліворуч від бога Випадковості, то ми точно почуємо “ДА”. Адже якщо це буде бог Брехні, то питання вийде самозамкненим, а якщо - це бог Правди, то він говорить істину. В обох випадках відповідь буде однаково чесне ЙА-ДА, що відповідає неістинному твердженню.

Але якщо ми почуємо ЙА - то це означає, що ми отримали суперечливе твердження, адже ЙА-ЙА мало б означати істину, але тут позначає брехню. Це є можливим лише якщо бог Правди говорить про бога Брехні і навпаки (так само як у випадку з двома братами). Це означає, що ми говоримо з богом, що є праворуч від бога Випадковості.

Виходить, що при відповіді ДА ми говоримо з богом, що є ліворуч від бога Випадковості, а при відповіді ЙА - з тим, хто є по його правиці. Але таки розберемо кожен випадок окремо.

Детальніше пояснення

Припустимо боги розташовані так, що ліворуч від бога Випадковості знаходиться бог Брехні. На саме питання, чи він - бог Випадковості, він би нам відповів “Так”.

Випадок перший: уявимо собі, що ми спитали вищенаведене в бога Брехні, тобто його самого. Він змушений брехати про власну відповідь. На те, чи він відповість “Так” він змушений відповісти “Ні”, а на те, чи він відповість “Ні”, змушений відповісти “Так”. Тобто на ЙА він точно відповість ДА.

Випадок другий: якщо ж ми спитали бога Правди, то він точно знає, що бог Брехні збреше. На те, чи бог Брехні відповість “Так”, бог Правди скаже “Так”. На те, чи він відповість “Ні”, бог Правди відповість “Ні”. Тобто на ЙА він точно відповість ЙА.

Тепер уявимо собі, що ліворуч від бога Випадковості знаходиться бог Правди. На саме питання, чи він - бог Випадковості, він би нам відповів “Ні”.

Випадок третій: уявимо собі, що ми спитали вищенаведене в бога Брехні. Він знає, що бог Правди скаже “Ні”, тому на питання “чи той скаже Ні”, він відповість “Ні”. А на питання “Чи бог Правди відповість Так”, він скаже “Так”. Тобто на ЙА він точно відповість ЙА.

Випадок четвертий: якщо ж ми спитали про це бога Правди, то він нам відповість повністю правдиво. На те, чи він нам скаже “Так” він відповість “Ні”, а чи він відповість “Ні” він нам скаже “Так”. Тобто на ЙА він точно відповість ДА.

Що це нам дає?

Якщо ми почули відповідь ДА, то одне з трьох:

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

Міркуючи так само, ми можемо бути впевнені, що праворуч від бога, котрого ми щойно питали, нема бога Випадковості, якщо відповідь була ЙА (випадок другий та третій). Наступні два питання ми поставимо богу, що знаходиться праворуч від того, кому ми щойно ставили питання.

Найважливіше - ми визначили хто богом Випадковості точно не є.

Алгоритм

Спочатку розташовуємо богів по колу - ця умова включається в перше питання.

За три питання ми визначили усіх трьох богів.

Інші рішення

Це - не єдино можливий розв’язок. Цікавими розв’язками є ті, де задають настільки каверзні питання, що в бога Правди, або Брехні “вибухає голова” - це питання схожі на “Усі критяни - брехуни. Я - критянин. Чи я збрехав?”

Простіше рішення, аніж вище запропоноване, використовує мало не такі самі два останні питання, але перше питання значно простіше. Там не треба розташовувати богів по колу і можна знову ж таки задати самозамкнене питання “Якщо я спитаю тебе, чи це (вказати на іншого) - бог Випадковості, чи ти скажеш ЙА”. При відповіді ЙА, ми знаємо, що це - таки бог Випадковості (ЙА-ЙА - це умовне “так”), при відповіді ДА - це не бог Випадковості (ЙА-ДА - це умовне “ні”). Залежно від відповіді ми обираємо бога для наступних питань. Тобто при ЙА - обираємо іншого бога, а при відповіді ДА - того бога, на якого ми показували.