логическая задачка

[avva]

Булос (Boolos) предлагает следующую задачку в качестве “The Hardest Logical Puzzle Ever”. Это, на мой взгляд, несколько преувеличено, но задачка действительно очень непростая. Придумал её Смаллиан (Smullyan) , а ещё более усложнил Джон Маккарти (John McCarthy, который изобретатель компьютерного языка Лисп).

Условие:

Вашу незначительную персону почтили своим присутствием трое богов. Их зовут True, False и Random. Бог по имени True всегда говорит правду, бог по имени False всегда лжёт, а бог по имени Random отвечает на все вопросы совершенно случайным образом.

К сожалению, вы не знаете, кто из них кто. Обозначим троих богов буквами A, B и C. Вы не знаете, кто из A, B и C на самом деле True, кто False, а кто Random. Сами боги это знают (о себе и других).

У вас есть возможность задать им три вопроса, на каждый из которых можно ответить только “да” или “нет”. Необязательно задавать каждому богу по одному вопросу; вы можете, если вам хочется, задать все три вопроса одному и тому же богу, или ещё как-нибудь. Вопросы задаются по порядку, то есть, например, в зависимости от ответа на первый вопрос вы можете выбрать, кому задавать второй вопрос и каким он будет.

Боги понимают ваш язык и ваши вопросы, но отвечают всегда на своём языке. В этом языке вместо “да” и “нет” говорят “oui” и “ja”. К сожалению, вы не знаете, что из них означает что — может быть, “oui” это “да”, а “ja” — “нет”, а может и наоборот.

Ваша задача: с помощью этих трёх вопросов точно определить, кто из них кто.

Comments

[prince-felix.livejournal.com]

Как вычислить кого-то, кто точно не Random, если ответы Random'а будут совпадать (а они могут совпадать) с ответами True или False по всем пунктам? :)

Я бы даже задачу сформулировал так...

Два бога, один (да хоть сотня) из которых отвечает на вопросы правдиво (Good), а другой отвечает случайным образом (Bad). Задать любое количество вопросов таким образом, чтобы найти, кто из A и B является Good, а кто Bad.

Любопытность в том, что при "плохом" стечении случайностей наборы вопрос-ответ для обоих богов окажутся одинаковыми.

А в сети есть сборники "правильных" (я-то их правильными не считаю :)) вопросов?

[avva.livejournal.com]

Есть, и даже здесь уже появились, правда, в не совсем корректной форме.

[prince-felix.livejournal.com]

Ага, с iff уже прочитал. Метод понял, но решение как-то не очень. Распечатаю и дома пересмотрю. Хорошая задача.

[manco.livejournal.com]

Про два бога, мне кажется, достаточно одного вопроса (любому):

(Вы Bad) xor (Вы лжете, отвечая на этот вопрос)?

Good ответит: нет (нет xor нет)

Bad ответит:
- если решил сказать правду: да (да xor нет)
- если решил солгать: да (да xor да = нет, но он лжет, значит должен сказать да)

[prince-felix.livejournal.com]

Bad ничего не решает, а отвечает _случайно_ вне зависимости от того, что его спросили. Можно даже не спрашивать, а просто нажимать кнопку на его лбу, чтобы получить "да" или "нет". Так что на Ваш вопрос Bad вполне может ответить "нет". :)