?

Log in

No account? Create an account
логическая задачка - Поклонник деепричастий [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:
Страница 1 из 2
<<[1] [2] >>
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)
Страница 1 из 2
<<[1] [2] >>