?

Log in

логическая задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

логическая задачка [апр. 26, 2004|03:09 pm]
Anatoly Vorobey
Булос (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:
From: (Anonymous)
2004-04-26 05:23 am
Р. Смаллиан - классический автор для советских школьников.
Зачем же звать его Смульяном.
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 05:29 am
Спасибо. Тем более стыдно, что "Принцессу или тигра" очень любил в детстве. Исправил.
(Ответить) (Parent) (Thread)
[User Picture]From: rydel23
2004-04-26 05:42 am

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

It was "da" and "ja" in the original article.
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 05:45 am
А также "yes" и "no", и что? :)
(Ответить) (Parent) (Thread)
[User Picture]From: arno1251
2004-04-26 05:46 am
И всего три вопроса?! Невероятно. И что, эта задача действительно имеет решение (решения)?
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 05:51 am
Ага, есть решение.
(Ответить) (Parent) (Thread)
[User Picture]From: rukenau
2004-04-26 05:49 am
А oui и ja могут менять значения с каждым ответом? Т.е. False ответил ja, имея в виду "да", а на следующий раз -- имея в виду "нет"?
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 05:52 am
Нет, oui и ja заданы раз и навсегда.
(Ответить) (Parent) (Thread)
[User Picture]From: egmuri
2004-04-26 05:56 am
а можно задавать вопросы из серии "вертится ли земля вокруг солнца?" :)
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 05:59 am
Да. Главное, чтобы это были вопросы типа да/нет. Фактические вопросы, на которые известен точный ответ, разрешаются.
(Ответить) (Parent) (Thread)
[User Picture]From: anton
2004-04-26 05:56 am
А можно задавать составные вопросы — скажем — "Ты то-то бог и то-то [из внешнего мира] правда?" ?
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 05:59 am
Да. Или даже "ты либо то-то, либо то-то, правда?" Или ещё более сложные. Как угодно ;)
(Ответить) (Parent) (Thread)
From: prince_felix
2004-04-26 06:20 am
ИМХО, нерешаемая задача.
Ответы Random могут в точности совпадать с ответами True и False, так что даже если вычислить False или True (вопросами типа 2+2=4?), то затем отличить Random от оставшегося бога невозможно.

Любопытно посмотреть на правильные вопросы.
(Ответить) (Thread)
[User Picture]From: manco
2004-04-26 06:23 am
О том, кто Random, можно спросить, например, True :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: sabalin
2004-04-26 06:30 am
Интересно, а что ответит Truth если его спросить например "Ответит ли Рэндом на мой вопрос правильно?"
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 06:36 am
По-моему, у такого вопроса нет точного ответ да/нет, т.к. даже True не может предсказать, что ответит Random :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: sirin
2004-04-26 07:19 am
может быть я что-то упускаю из виду, но
если спросить всех троих, например: "бог ли вы?", то один из трёх даст ответ, отличный от двух других. это будет либо А, ответивший "да", либо В, сказавший "нет".
если этого одного спросить: "вы А?", то в обоих случаях ответ будет "да", следовательно, если на первый вопрос был дан тот же ответ, что и на второй, то, значит, перед нами А.
а уж зная А это или В, мы можем спокойно спросить, указав на одного из двух оставшихся: "это С?" и получить заведомо правдивый или заведомо ложный ответ.
(Ответить) (Thread)
[User Picture]From: kidd79
2004-04-26 08:01 am
Вы не укладываетесь в лимит :)

----- [ just kiddin' ] -----
I try to make everyone's day a little more surreal.
----- [ stop kiddin' ] -----
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: sabalin
2004-04-26 07:28 am
А про будущее их можно спрашивать?
Например вопрос "Ответит ли Рэндом правильно на следующий вопрос" должен быть легитимен...

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

в данный момент - мне слабо:)
(Ответить) (Thread)
[User Picture]From: ollka
2004-04-26 07:32 am
компьютерный язык Лисп :)))))))))
Computer! pleathe perform thith tathk for me - and fatht, cauthe i'm in a hurry!
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 09:00 am
:))
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2004-04-26 07:50 am
Самое интригующее - что 8 < 12.
Правда, язык выучить не требуется, так что надежда есть :)
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 09:13 am
Ага ;)
(Ответить) (Parent) (Thread)
[User Picture]From: mi_b
2004-04-26 08:20 am
Ясно, что незнание языка - позднейшее усложнение. Оно легко обходится XOR вопросов задачки со знанием языка с высказыванием "oui=нет". Дальше тоже XORами, но проверять лень ;)
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 09:00 am
Да, незнание языка - усложнение, которое придумал Маккарти ;)
(Ответить) (Parent) (Thread)
[User Picture]From: vnarod
2004-04-26 08:25 am
Хорошая задачка. Сижу уже 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
(Ответить) (Thread)
[User Picture]From: avva
2004-04-26 08:58 am
Вроде бы без iff решения нет. То есть можно, понятно, замаскировать его xor'ом или словами, но это неинтересно.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2004-04-26 09:59 am
Ага, у этой задачки ноги растут еще из Гарднера -- он рассматривает классическую, про вруна и честного, стоящих на развилке, и надо одним вопросом найти правильную дорогу, не зная, кто врун, а кто честный. Обычно ответом "спросить у любого, что ответит его приятель на вопрос, правильная ли это дорога" все и заканчивается, но потом соображается, что можно спросить этого любого и про него же самого(заменить "плюс на минус равно минус на плюс равно минус" на "плюс на плюс равно минус на минус равно плюс"), а дальше -- что и сигналы для "да" и "нет" можно не знать, а спрашивать "ответишь ли ты "уи" на вопрос о правильности этой дороги" и смотреть на совпадение ответного звука с "уи".
Получается, что если мы локализуем не глухого(мне "Глухой" больше нравится, чем "Рандом"), мы сможем задать ему два вопроса об именах остальных(или его и еще одного), и будем знать все. Задача, значит, за один вопрос найти не глухого. Спрашивать человека о нем самом -- бессмысленно, т.к. у обоих неглухих результаты опыта просто совпадут, а у глухого таки останется случайным. Но ежели спросить "ответишь ли ты "куку", если тебя спросят, глухой ли вон тот чувак", то, если спрошенный не глухой, мы точно узнаем, где оставшийся не глухой(если звуки совпали -- глух тот, о ком мы спрашивали, а значит, третий -- таки не глухой, а если разные -- значит, не глух тот, о ком мы спрашивали). Если же спрашиваемый оказался глухим, то мы, вычисляя неглухого из оставшихся(исходя по-прежнему из неглухости спрашиваемого), не можем промахнуться, бо они оба неглухие. Ну вот, значит, заведомо не глухого нашли одним вопросом, и дальше зададим ему оставшиеся два вопроса об именах(например, один -- о его имени, которое уже либо Тру, либо Фолс, второй -- об имени любого оставшегося, которое уже либо Рандом, либо Тру/Фолс, в зависимости от результата первого вопроса).
Замечательная задачка, ага. Смаллианова революционность -- в вовлечении глухого, который, на первый взгляд, вносит нерешаемость, а на самом деле -- не меняет ровно ничего. Но все-таки не устаешь поражаться, насколько исходная классическая задачка(врун и честный и развилка) избыточна:и двоих не надо, и значения сигналов знать не надо -- а это все заметил еще Гарднер, еще когдаааа...
(Ответить) (Thread)
[User Picture]From: _under_score_
2004-04-27 06:14 am
а почему никто не прокомментировал это - очевидно, верное - решение?
(Ответить) (Parent) (Thread)
[User Picture]From: stas
2004-04-26 10:27 am
У Смаллиана, кажется, целая книга посвящена этой задаче, только вот не помню, какая именно из них. Там вроде есть общее решение, правда получающиеся вопрос у него там в стиле "если бы я вас спросил, что ..., то ответили бы вы мне то же самое как если бы я вас спросил, ответили ли бы вы на вопрос "..." словом ja?" Недаром в задаче упоминатся боги - обычный человек на такой вопрос ответит "чё?" ;)
(Ответить) (Thread)
[User Picture]From: talash
2004-04-26 10:50 am
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.
(Ответить) (Thread)
[User Picture]From: lom
2004-04-26 11:02 am

Solution - funny

У задачи 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сть....
(Ответить) (Thread)
[User Picture]From: russian_bob
2004-04-26 12:03 pm

Re: Solution - funny

Такое решение противоречит одному из условий задачи: "можно задать три вопроса, на каждый из которых можно ответить только “да” или “нет”." В Вашем варианте подразумевается что есть третий ответ - "не знаю".
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2004-04-27 08:47 am
Я покорнейше прошу прощения за офф-топ, но всё-таки:
не знаете ли вы, что случилось с ЖЖ Романа Лейбова?
журнал r_l был удалён им самим? почему?!
(Ответить) (Thread)
[User Picture]From: avva
2004-04-27 01:57 pm
Так ему захотелось.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2004-04-28 11:20 am
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. Спасибо за внимание.
(Ответить) (Thread)
From: (Anonymous)
2005-02-05 12:14 pm
И ты тоже тупой!
5. А если он врун и второй действительно глухой?
Короче дерьмо ты придумал!
Проверяйте себя перед ответами!
(Ответить) (Parent) (Thread)