Проект основателей компании «Ваш репетитор»
ERUDITOR.RU
Форум «Eruditor.ru»  →  Тема «"Самая сложная логическая задача"»
"Самая сложная логическая задача"
по версии создателей весьма популярного сайта

Есть три бога - Истинный, Ложный и Случайный. Истинный - всегда говорит правду. Ложный всегда обманывает. Случайный может ответить верно или солгать. Ваша задача состоит в том, чтобы определить, кто есть кто, задав три «да-нетных» вопроса, причем каждый вопрос должен быть адресован только одному богу. Боги понимают ваш язык, но отвечают на все вопросы на своем собственном языке словами «da» или «ja». Но вы не знаете, какое слово обозначает «да», а какое - «нет».
↓↓ 0 ↑↑   Zero (38 / 335)   20 июн 2007 00:02   »»


Можно каждому богу задавать вопрос "ja-это да?" тогда истиный в ответ скажет "ja" ложный «da» .Но как вычислить Случайного?? Впрочем на дзадачей надо еще подумать.
↓↓ 0 ↑↑   Paha (0 / 62)   21 июн 2007 12:12   «« #2 »»   Ответить


"...каждый вопрос должен быть адресован только одному богу"
↓↓ 0 ↑↑   Zero (38 / 335)   21 июн 2007 14:35   «« #3 »»   Ответить


честно говоря
так можно и голову свихнуть... предполагаю что эти вопросы должны быть сложными (т.е. использовать логические операторы "И" "ИЛИ", и затрагивать богов, к которым вопрос не обращен. Но:
ответ Случайного бога непредсказуем, поэтому любой вопрос связанный с его ответом у другого бога может вызвать "зависание". Т.е. условия задачи необходимо детализировать, можно ли задавать вопросы, на которые бог не сможет однозначно ответить? Какова будет его реакция на них?
Например интересен вариант вопроса к богу1: "Если я задам один и тот же вопрос богу 2 и 3 они ответят одинаково?"
Если условия предполагают, что правдивый и ложный боги промолчат в ответ на вопрос ответа на который не знают, то варианты решения можно подобрать. А если таких вопросов задавать нельзя, то и решение нужно искать в другой плоскости..
↓↓ 0 ↑↑   rex-RnD (4 / 22)   21 июн 2007 16:44   «« #4 »»   Ответить


вопрос Zero
на том самом весьма популярном сайте есть правильный ответ и вообще есть ли ответ? стоит ли вообще голову ломать? ))
↓↓ 0 ↑↑   kostyan (0 / 8)   21 июн 2007 22:32   «« #5 »»   Ответить


Ответ есть
↓↓ 0 ↑↑   Zero (38 / 335)   21 июн 2007 23:11   «« #6 »»   Ответить


Можно наверно
Попытать счастья на вопросах по образу "что бог 3 ответит на вопрос ...".Но это хорошо с задачами про двери и ручных крокодилов.
↓↓ 0 ↑↑   Paha (0 / 62)   22 июн 2007 08:37   «« #7 »»   Ответить


Если ответ есть,
так уточните ситуацию с вопросами, о которых пишет rex-RnD.
↓↓ 0 ↑↑   eruditor (128 / 439)   23 июн 2007 14:59   «« #8 »»   Ответить


Текст задачи оригинальный (никаких уточнений НЕТ).
Однако автор решения дает свои комментарии:
1) Одному богу можно задать больше чем один вопрос (и следовательно, кого-то не спрашивать вообще).
2) Каким будет второй (третий) вопрос и к какому богу он будет адресован может зависеть от ответа на предыдущий вопрос.
3) Ответ Случайного бога зависит от монеты, которая скрыта в его голове и постоянно вращается: если выпадает орел, он говорит верно, если решка - лжет.
4) Случайный бог ответит «da» или «ja» на любой «да-нетный» вопрос.
↓↓ 0 ↑↑   Zero (38 / 335)   23 июн 2007 16:36   «« #9 »»   Ответить


??? Zero
так одному богу можно задавать больше одного вопроса или нет?
↓↓ 0 ↑↑   kostyan (0 / 8)   23 июн 2007 22:10   «« #10 »»   Ответить


Один и тот же вопрос можно задавать только одному богу.
Одному (любому) богу можно задать больше одного вопроса.

Теперь понятно?
↓↓ 0 ↑↑   Zero (38 / 335)   24 июн 2007 12:59   «« #11 »»   Ответить


А вопросы с каверзой можно? Например, сначала спросить:" У случайного бога выпал ОРел?" Если выплала решка, то случ. бог "зависнет". Также можно Ложного "подвесить". "Ты мне сейчас правду скажешь?
↓↓ 0 ↑↑   Kronos (0 / 6)   31 июл 2007 17:57   «« #12 »»   Ответить


Задаем вопрос типа: Совпадет ли твой ответ на данный вопрос со случайным, если у него в голове выпадет решка". Случайный - виснет. Да - может сказать только Ложный (т.к. у случайного нет ответа. Нет - истинный. Если сначала был случайный, то другому здадим вопрсов: "Ты мне сейчас правду скажешь?". Ложный виснет, итинный - отвечает. Все : определиили. Тепеь если Истинному или Ложному попалось - ответ -нет. дальше -про правду. Все: определи, кто он. Дальше - снова про решку. Снова определяется , кто , так как случайный зависнет. Все , вроде.
↓↓ 0 ↑↑   Kronos (0 / 6)   31 июл 2007 18:17   «« #13 »»   Ответить


Если соблюдается 4-ый пункт условия (хотя это должно противоречить 3-му пункту) - верное решение.
Вопрос, адресованный одному из богов: "Ты сейчас скажешь слово, на твоем языке означающее "да"?" "Завис" - не дает ответа - бог Лжи, так как Случайный, даже если "выпала" решка, по 4-ому пункту условия должен ответить на любой "данеточный" вопрос, то есть он ДОЛЖЕН что-то сказать. Ответит - это истинное утверждение, причем мы будем знать слово, означающее "да" (хотя это и не понадобится). Но тогда перед нами или Случайный бог, у которого "выпал" орел, или бог Истины. Рассмотрим оба случая.
1)Одному из оставшихся богов задаем вопрос: "Ты сейчас скажешь слово, на твоем языке означающее "нет"?" Тогда: если "завис" - бог Истины, ответил - Случайный. Хватило двух вопросов, все боги идентифицированы.
2)Тому же богу задаем вопрос: "Ты сейчас скажешь слово, на твоем языке означающее "нет"?" "Завис" - бог Истины, ответил - Случайный.Опять два случая, а) и б)
а)Одному из оставшихся богов задаем вопрос:"Ты сейчас скажешь слово, на твоем языке означающее "да"? "Завис" - бог Лжи, ответил - Случайный.
б)Одному из оставшихся (боги Лжи и Истины) задаем любой из вышеозначенных вопросов, например, с "да". "Завис" - бог Лжи, ответил - Истины.
Все. :)
↓↓ 0 ↑↑   7777777 (3 / 130)   31 июл 2007 19:19   «« #14 »»   Ответить


Kronos
Случайный бог не "зависает".
↓↓ 0 ↑↑   Zero (38 / 335)   01 авг 2007 12:05   «« #15 »»   Ответить


7777777
Отвечу немного позже. Сейчас нет времени разбираться...
↓↓ 0 ↑↑   Zero (38 / 335)   01 авг 2007 12:06   «« #16 »»   Ответить


Не совсем то.
Один и тот же вопрос нельзя задавать нескольким богам. Тут, по-моему, такое есть...
Дальше, в одном из пунктов - 1) или 2) - явно опечатка.
В каком-то случае действительно хватает всего 2 вопросов.

В оригинале более красивое решение... И боги не зависают.
Представьте, что если какой-то бог не может ответить на заданный вопрос, то все трое мгновенно меняются местами (т.е. нельзя понять, где тот, кому задавался вопрос).

Дерзайте! :)

Кстати, почему это 4 пункт противоречит 3?
↓↓ 0 ↑↑   Zero (38 / 335)   01 авг 2007 19:34   «« #17 »»   Ответить


Задача решалась наскоро, пересмотрю вопросы. А о противоречии: Случайный ВСЕГДА отвечает "да" или "нет", НО при этом он не просто вставляет междометие, а говорит либо истину. либо ложь, в зависимости от "выпавшей" монетки. Но ведь есть вопросы (и они приведены), на которые нельзя ответить "да" или "нет", если тебя обязали говорить только правду или только ложь.
↓↓ 0 ↑↑   7777777 (3 / 130)   01 авг 2007 20:52   «« #18 »»   Ответить


И вообще, о Случайном уточните все же.. иначе не видно решения... :)
↓↓ 0 ↑↑   7777777 (3 / 130)   01 авг 2007 20:54   «« #19 »»   Ответить


Если бы решение было очевидным, то это не была бы "самая сложная логическая задача"...
↓↓ 0 ↑↑   Zero (38 / 335)   01 авг 2007 23:25   «« #20 »»   Ответить


Не знаю, я "доказал", что решения нет. Доказательство довольно большое, основывается на переборе возможных комбинаций.
↓↓ 0 ↑↑   igar (10 / 119)   02 авг 2007 12:38   «« #21 »»   Ответить


igar
Вы только не обижайтесь, пожалуйста.

Люди в древности много чего "понадоказывали". А потом пришли другие и все доказательства опровергли...
Если ВЫ не видите решения, это не означает, что его нет.
Если вы видите ОДНО решение, это не значит, что оно единственное...
↓↓ 0 ↑↑   Zero (38 / 335)   02 авг 2007 16:30   «« #22 »»   Ответить


Вот решение...
автором которого является Дж. Булос (George Boolos), если, конечно, кому-то это интересно...
Переведено на русский язык и доведено до массового читателя мной :)

Первое, что необходимо сделать, это определить бога, который ТОЧНО не Случайный (С), т.е. либо Истинный (И), либо Ложный (Л).
Для этого нужно задать вопрос, вариантов которого, в принципе, несколько.

Вот самый простой:
-------Если я задам тебе В, ты ответишь "ja"? (под В подразумевается любой да-нетный вопрос)
Если истинный ответ на В "да", то "ja" означает "да". Если истинный ответ на В "нет", то "da" означает "нет".

Рассмотрим 8 возможных случаев:
Предположим, что: "ja"="да", "da"="нет"
1. Спрашивают И, он отвечает "ja". Т.к. он говорит правду, то истинный ответ на В - "ja", что означает "да".
2. Спрашивают И, он отвечает "da". Т.к. он говорит правду, то истинный ответ на В - "da", что означает "нет".
3. Спрашивают Л, он отвечает "ja". Т.к. он лжет (при этом дважды - первый раз при ответе на В, второй раз - при ответе на вторую часть вопроса), то истинный ответ на В - "ja", что означает "да".
4. Спрашивают Л, он отвечает "da". Т.к. он лжет, то истинный ответ на В - "da", что означает "нет".

Предположим, что: "ja"="нет", "da"="да"
5. Спрашивают И, он отвечает "ja". Т.к. он говорит правду, то истинный ответ на В - "da", что означает "да".
6. Спрашивают И, он отвечает "da". Т.к. он говорит правду, то истинный ответ на В - "ja", что означает "нет".
7. Спрашивают Л, он отвечает "ja". Т.к. он лжет, то истинный ответ на В - "da", что означает "да".
8. Спрашивают Л, он отвечает "da". Т.к. он лжет, то истинный ответ на В - "ja", что означает "нет".

Дальше вспомним пункт 3 комментария:
"Ответ Случайного бога зависит от монеты, которая скрыта в его голове и постоянно вращается: если выпадает орел, он говорит верно, если решка - лжет".
Это означает, что С бог ведет себя то как И, то как Л. При этом он осознает свое состояние (орел-решка) и осознанно же говорит правду или нет.

Приняв это во внимание, видоизменим вопрос:
------Если я задам тебе В, в том состоянии, в котором ты находишься сейчас, ты ответишь "ja"?

А теперь собственно вопросы Булоса:
Для удобства обозначим богов через буквы А, Б и В.

1) Спрашиваем А: Если я задам тебе вопрос "Ты Случайный бог?", в том состоянии, в котором ты находишься сейчас, ты ответишь "ja"?
---Если А отвечает "ja", тогда А - Случайный.

2а) Спрашиваем Б: Если я задам тебе вопрос "Ты Истинный бог?", ты ответишь "ja"?
---Если Б отвечает "ja", тогда Б - Истинный, а В - Ложный (и все боги идентифицированы за 2 вопроса).

---Если А отвечает "da", тогда А - не Случайный.

2б) Спрашиваем А: Если я задам тебе вопрос "Ты Истинный бог?", ты ответишь "ja"?
---Если А отвечает "ja", тогда А - Истинный.
---Если А отвечает "da", тогда А - Ложный

3) Спрашиваем А: Если я задам тебе вопрос "Б - это Случайный бог?", ты ответишь "ja"?
---Если А отвечает "ja", тогда Б - Случайный, а В - Ложный.
---Если А отвечает "da", тогда B - Случайный, а Б - Истинный.

P.S. Кстати, существует еще один вариант этой задачи, из которого исключен 3 пункт комментария Булоса (т.е. Случайный бог отвечает действительно в абсолютно произвольном порядке).
Тоже решается за 3 вопроса по тому же принципу...
↓↓ 0 ↑↑   Zero (38 / 335)   02 авг 2007 16:35   «« #23 »»   Ответить


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

И второе: как быть с "зависаниями", т. е. вопросами, на которые нельзя ответить "да" или "нет", чтобы это было конкретно правдой или ложью?
↓↓ 0 ↑↑   7777777 (3 / 130)   06 авг 2007 08:06   «« #24 »»   Ответить


Корректировка
А в моем решении а) и б) действительно нуждаются в корректировке.
а) Одному из оставшихся богов задаем вопрос: "Когда ты говоришь "да", ты лжешь?" Завис - бог Лжи, ответил Случайный.
б)Любой конкретный вопрос, типа, "дважды два - четыре?" Да - бог Истины, нет - Лжи.
↓↓ 0 ↑↑   7777777 (3 / 130)   06 авг 2007 09:26   «« #25 »»   Ответить


Поправка
а) Одному из оставшихся богов задаем вопрос: "Когда ты говоришь "нет", ты лжешь?" Завис - бог Лжи, ответил Случайный. "Да" и "нет" мы определили в самом начале.
↓↓ 0 ↑↑   7777777 (3 / 130)   06 авг 2007 09:44   «« #26 »»   Ответить


7777777
В произвольном порядке - это значит в произвольном порядке. По-моему просто и понятно :)

Решение существует. Есть причины сомневаться?

Вопросы могут быть любыми. Кстати, в моем последнем посте есть подсказка...

На этот вопрос уже был ответ. Повторю:
"Представьте, что если какой-то бог не может ответить на заданный вопрос, то все трое мгновенно меняются местами (т.е. нельзя понять, где тот, кому задавался вопрос)".
↓↓ 0 ↑↑   Zero (38 / 335)   06 авг 2007 18:05   «« #27 »»   Ответить


можно спросить у любого:
если бы ты был богом правды то как будет звучать слово да
и дальше можно все вычислить
↓↓ 0 ↑↑   toro (-4 / 16)   06 мар 2010 21:56   «« #28 »»   Ответить


<:>. :: :.·· ..··:!!!!!!!!<:·>:::.:··.·.·.·, ::::·.:: .· .:. ..:.···.:·, ·. :: · ..·.. ·.·: ...:: :· ··.:. ····...::, ..·.···: :···.·: :..: ·:..·:..:· ...·:·:?????? :· ·. :..:. ·: .:·. .·::.·!!!!! ?????? :· ·:· :.·:·.·.·· .·.... ::::··.·, : .:: .··. .:·:. : :::·:·.:· .::: :.· ..:·: ...:.!!. ·. ·:· :·:. .·.::·..... ·::::: ·.·: :.:... ·:::..··. :.· ..: ::·., :·.· ·.·:·:· .·· ·:.... ::. :::.: ···..:·: :· .::..::·.: .·: .·:..· :··:.··:.::!:, ···. ·:.:: ·.··..::·· ·:·::- :· ·:·.:· .:::..·, .:..·.·. · :.·:.::· :·:.· · :.::· ·.···:. :: .· ..:.:··:·:::·:: ..:.··::·..·:!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ::.··:··...:..··.·::...·:·::.::.:·:.··:·::::··..:..·:..·:.·...·:.··:..·..:..!!!!!!
↓↓ −111 ↑↑   карпов (-111 / 3)   06 авг 2010 02:34   «« #29 »»   Ответить


Мы можем заметить, что на вопрос "da означает да?" бог правды ответит "da", а бог лжи ответит "ja", что бы "da" и "ja" не означали. Аналогично на вопрос "ja означает да?" бог правды ответит "ja", а бог лжи ответит "da".

Теперь я иду к богу A, и спрашиваю "da означает да?", затем иду к богу B, и спрашиваю "ja означает да?".
Допустим получил ответы: A — "da" и B — "ja". Это означает, что C — бог лжи. Я иду к нему и спрашиваю "C — бог лжи?". Его ответ (da/ja) означает нет, то есть у меня есть словарь значений da/ja. И последний вопрос "A — бог правды?". Ответ "нет" — означает "A — бог правды", "C — бог случая", ответ "да" A и C наоборот.
Допустим получил ответы: A — "ja" и B — "da". Значит C — бог правды. По тому же алгоритму получаем язык, и одного из богов.
Допустим получил ответы: A — "da" и B — "da". Тогда я иду к C, и задаю 2 вопроса: "A — бог правды?", "B — бог правды?". Если "C — бог правды?", то он ответит 2 раза нет, т.е: "da, da", или "ja, ja". Если "C — бог лжи", то он ответи один раз "да", один раз "нет", т.е "da, ja", или "ja, da". Бог слуйая ответит любым из 4-х варинтов. Если ответ "da, da", или "ja, ja", значит это не бог лжи, мы также знаем, что A не бог лжи, значит B — бог лжи. Идем к нему и спрашиваем "B — бог лжи?". Его ответ (da/ja) означает нет, то есть у меня есть словарь значений da/ja. И последний вопрос "A — бог случая?"... Если ответ "da, ja", или "ja, da", значит A — бог правды и опять за 2 вопроса находим кто есть кто
↓↓ 0 ↑↑   Александр (0 / 1)   19 июл 2015 10:49   «« #30 »»   Ответить


Господа знатоки у великой и всезнающей википедии написано что булос в своей задаче дает такой комментарий что нельзя задавать противоречивые вопросы ответ на который может быть и да и нет что собственно приводит к зависанию Исходя из этого все ваши решения не верны. Перечитав в той же википедии ответ булоса я насчитал в его решении 4 вопроса вместо 3. И если один из этих вопросов убрать то теряется смысл и ответа не будет. Писать долго но вывод таков даже создатель не ответил на свою загадку а вы куда умники рветесь? Читайте внимательно условие а уж тогда умничайте) стыдно товарищи попусту из себя грамоьтеев строить не зная или намеренно не обращая внимания на все условия задачи. Стыдно товарищи стыдно
↓↓ 0 ↑↑   алекс (0 / 1)   21 янв 2017 01:08   «« #31   Ответить


Форум «Eruditor.ru»  →  Тема «"Самая сложная логическая задача"»

Чтобы ответить на конкретное сообщение, нужно нажать на ссылку «ответить» справа под самим сообщением.
Эта форма — для ответов на исходное сообщение темы (на всю тему в целом).
Ваше имя
Email
Текст ответа
© 2006-2017   Авторы