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

[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

[(Anonymous)]

Р. Смаллиан - классический автор для советских школьников.
Зачем же звать его Смульяном.

[avva.livejournal.com]

Спасибо. Тем более стыдно, что "Принцессу или тигра" очень любил в детстве. Исправил.

[rydel23.livejournal.com]

> говорят “oui” и “ja”

It was "da" and "ja" in the original article.

[avva.livejournal.com]

А также "yes" и "no", и что? :)

[arno1251.livejournal.com]

И всего три вопроса?! Невероятно. И что, эта задача действительно имеет решение (решения)?

[avva.livejournal.com]

Ага, есть решение.

[igorlord.livejournal.com]

Почему бы и нет?
Есть 3! = 6 разных комбинаций (вариантов кто есть кто), из которых надо найти 1.
Дано 3 вопроса, что соответственно 2^3 = 8 комбинаций ответов. Значит в принципе можно сделать покрытие из 8 в 6.

Но это значит что выяснить что такое "да" и что такое "нет" не удасться (да и не требуется) т.к. это уже требует из 8 последовательностей ответов найти одну из 2*3!=12 комбинаций

[rukenau.livejournal.com]

А oui и ja могут менять значения с каждым ответом? Т.е. False ответил ja, имея в виду "да", а на следующий раз -- имея в виду "нет"?

[avva.livejournal.com]

Нет, oui и ja заданы раз и навсегда.

[egmuri.livejournal.com]

а можно задавать вопросы из серии "вертится ли земля вокруг солнца?" :)

[avva.livejournal.com]

Да. Главное, чтобы это были вопросы типа да/нет. Фактические вопросы, на которые известен точный ответ, разрешаются.

[anton.livejournal.com]

А можно задавать составные вопросы — скажем — "Ты то-то бог и то-то [из внешнего мира] правда?" ?

[avva.livejournal.com]

Да. Или даже "ты либо то-то, либо то-то, правда?" Или ещё более сложные. Как угодно ;)

[prince-felix.livejournal.com]

ИМХО, нерешаемая задача.
Ответы Random могут в точности совпадать с ответами True и False, так что даже если вычислить False или True (вопросами типа 2+2=4?), то затем отличить Random от оставшегося бога невозможно.

Любопытно посмотреть на правильные вопросы.

[manco.livejournal.com]

О том, кто Random, можно спросить, например, True :)

[sabalin.livejournal.com]

Интересно, а что ответит Truth если его спросить например "Ответит ли Рэндом на мой вопрос правильно?"

[avva.livejournal.com]

По-моему, у такого вопроса нет точного ответ да/нет, т.к. даже True не может предсказать, что ответит Random :)

[sirin.livejournal.com]

может быть я что-то упускаю из виду, но
если спросить всех троих, например: "бог ли вы?", то один из трёх даст ответ, отличный от двух других. это будет либо А, ответивший "да", либо В, сказавший "нет".
если этого одного спросить: "вы А?", то в обоих случаях ответ будет "да", следовательно, если на первый вопрос был дан тот же ответ, что и на второй, то, значит, перед нами А.
а уж зная А это или В, мы можем спокойно спросить, указав на одного из двух оставшихся: "это С?" и получить заведомо правдивый или заведомо ложный ответ.

[kidd79.livejournal.com]

Вы не укладываетесь в лимит :)

----- [ just kiddin' ] -----
I try to make everyone's day a little more surreal.
----- [ stop kiddin' ] -----

[sabalin.livejournal.com]

А про будущее их можно спрашивать?
Например вопрос "Ответит ли Рэндом правильно на следующий вопрос" должен быть легитимен...

впрочем это мало чего дает... просто нужно очень много вероятностей перебрать...

в данный момент - мне слабо:)

[ollka.livejournal.com]

компьютерный язык Лисп :)))))))))
Computer! pleathe perform thith tathk for me - and fatht, cauthe i'm in a hurry!

[avva.livejournal.com]

:))

[flaass.livejournal.com]

Самое интригующее - что 8 < 12.
Правда, язык выучить не требуется, так что надежда есть :)

[avva.livejournal.com]

Ага ;)

[mi-b.livejournal.com]

Ясно, что незнание языка - позднейшее усложнение. Оно легко обходится XOR вопросов задачки со знанием языка с высказыванием "oui=нет". Дальше тоже XORами, но проверять лень ;)

[avva.livejournal.com]

Да, незнание языка - усложнение, которое придумал Маккарти ;)

[vnarod.livejournal.com]

Хорошая задачка. Сижу уже 40 минут, нашел одно решение, но только используя iff. Существует ли простое решение, без iff?
мой вариант:
1. to A: (A=True iff oui=yes) iff C=Random
2. if answer is oui (if ja then ask C the same)
to B: 2=2 iff oui=yes
3. to B: A=Random iff oui=yes

[avva.livejournal.com]

Вроде бы без iff решения нет. То есть можно, понятно, замаскировать его xor'ом или словами, но это неинтересно.

[(Anonymous)]

Ага, у этой задачки ноги растут еще из Гарднера -- он рассматривает классическую, про вруна и честного, стоящих на развилке, и надо одним вопросом найти правильную дорогу, не зная, кто врун, а кто честный. Обычно ответом "спросить у любого, что ответит его приятель на вопрос, правильная ли это дорога" все и заканчивается, но потом соображается, что можно спросить этого любого и про него же самого(заменить "плюс на минус равно минус на плюс равно минус" на "плюс на плюс равно минус на минус равно плюс"), а дальше -- что и сигналы для "да" и "нет" можно не знать, а спрашивать "ответишь ли ты "уи" на вопрос о правильности этой дороги" и смотреть на совпадение ответного звука с "уи".
Получается, что если мы локализуем не глухого(мне "Глухой" больше нравится, чем "Рандом"), мы сможем задать ему два вопроса об именах остальных(или его и еще одного), и будем знать все. Задача, значит, за один вопрос найти не глухого. Спрашивать человека о нем самом -- бессмысленно, т.к. у обоих неглухих результаты опыта просто совпадут, а у глухого таки останется случайным. Но ежели спросить "ответишь ли ты "куку", если тебя спросят, глухой ли вон тот чувак", то, если спрошенный не глухой, мы точно узнаем, где оставшийся не глухой(если звуки совпали -- глух тот, о ком мы спрашивали, а значит, третий -- таки не глухой, а если разные -- значит, не глух тот, о ком мы спрашивали). Если же спрашиваемый оказался глухим, то мы, вычисляя неглухого из оставшихся(исходя по-прежнему из неглухости спрашиваемого), не можем промахнуться, бо они оба неглухие. Ну вот, значит, заведомо не глухого нашли одним вопросом, и дальше зададим ему оставшиеся два вопроса об именах(например, один -- о его имени, которое уже либо Тру, либо Фолс, второй -- об имени любого оставшегося, которое уже либо Рандом, либо Тру/Фолс, в зависимости от результата первого вопроса).
Замечательная задачка, ага. Смаллианова революционность -- в вовлечении глухого, который, на первый взгляд, вносит нерешаемость, а на самом деле -- не меняет ровно ничего. Но все-таки не устаешь поражаться, насколько исходная классическая задачка(врун и честный и развилка) избыточна:и двоих не надо, и значения сигналов знать не надо -- а это все заметил еще Гарднер, еще когдаааа...

[http://users.livejournal.com/_under_score_/]

а почему никто не прокомментировал это - очевидно, верное - решение?

[stas]

У Смаллиана, кажется, целая книга посвящена этой задаче, только вот не помню, какая именно из них. Там вроде есть общее решение, правда получающиеся вопрос у него там в стиле "если бы я вас спросил, что ..., то ответили бы вы мне то же самое как если бы я вас спросил, ответили ли бы вы на вопрос "..." словом ja?" Недаром в задаче упоминатся боги - обычный человек на такой вопрос ответит "чё?" ;)

[talash.livejournal.com]

question: what do these gods do aboutlogical paradoxes, such as some of them may get into (for instance if i ask all of them "will all of you give them same answer when asked this question?") in their turn.

Solution - funny

[lom.livejournal.com]

У задачи eсть фантастичeскоe и очeнь смeшноe рeшeниe - абсолютно в духe "Дурацких шуточeк" Рэймонда Смаллиана...

1. Спрашиваeм бога А: отвeтят ли два других одно и то жe на вопрос, правда ли, что 2х2=4. Eсли получаeм отвeт, то мы спросили у Random.
Два других нe могут "шутить" с прeдсказаниями. Рассматриваeм только сложнeйший вариант, когда отвeта нeт - что означаeт, мы спросили
либо у True , либо у False

2. Тeпeрь надо отдeлить True от False. Это дeлаeтся с помощью вопроса об истинности прeдиката:

Спрашиваeм того жe бога (True от False): Истинно ли высказываниe " Из отвeта бога нe-Random из оставшeйся пары на вопрос '2х2=4?'
СЛEДУEТ отвeт бога-Random на тот жe вопрос" ?

Очeвидно, только True сможeт отвeтить ДА (oui or ja ) на вопрос об истинности этого прeдиката: ибо из лжи слeдуeт всe, что угодно. False
отвeтить нe сможeт, ибо истинность прeдиката True -> (?) зависит от отвeта Random.

3. Послeдний вопрос, когда мы нашли True, тривиалeн: спросить eго про любого из оставшихся богов, кто тот eсть....

Re: Solution - funny

[russian-bob.livejournal.com]

Такое решение противоречит одному из условий задачи: "можно задать три вопроса, на каждый из которых можно ответить только “да” или “нет”." В Вашем варианте подразумевается что есть третий ответ - "не знаю".

[(Anonymous)]

Я покорнейше прошу прощения за офф-топ, но всё-таки:
не знаете ли вы, что случилось с ЖЖ Романа Лейбова?
журнал r_l был удалён им самим? почему?!

[avva.livejournal.com]

Так ему захотелось.

[(Anonymous)]

avva, наверняка задача уже решена кем-нибудь из 75 комментаторов, но я, однако, не удержусь от того, чтобы дать свой вариант.

1. Добавляя к вопросу xor (ja="да"), мы можем добиться того, что oui будет означать "да", а ja - "нет".

2. Добавляя к вопросу xor (ты=False), мы можем добиться того, что False будет отвечать так же, как и True - т. е. говорить правду.

3. Итак задача сводится к следующей: есть три бога, 2 говорят правду (и ответы их нам понятны), а третий бредит.

4. Зададим первому вопрос, не является ли второй Random'ом.

5. Если он ответит утвердительно, из этого можно сделать вывод, что либо он сам не понимает, что говорит, либо второй действительно Random. Важно то, что третий бог в этом случае быть Random'ом не может.

6. Если он ответит отрицательно, то есть два варианта: либо он говорит правду, и второй бог не Random, либо он несет чушь и второй бог опять-таки не Random, потому что Random - первый.

7. Итак, теперь мы знаем одного бога, которому можно доверять. Ему-то мы и зададим оставшиеся нам два вопроса. Сначала спросим его, True он или False. Потом спросим про одного из его приятелей, Random ли он.

8. Полученной информации достаточно для выводов.

9. Я нигде не ошибся?

10. Спасибо за внимание.

[(Anonymous)]

И ты тоже тупой!
5. А если он врун и второй действительно глухой?
Короче дерьмо ты придумал!
Проверяйте себя перед ответами!