Итак озвучиваю задачу:

Есть три бога А,Б,В : один бог всегда говорит правду, второй всегда лжёт, третий отвечает случайно : то правду то лжёт.
Вы задав три вопроса (да/нет) должны узнать кто из богов как отвечает. Один вопрос задаётся только одному богу. Боги эти инозємные и отвечают они не да  и нет , а йта и дйа и что с них что значит нипанятна.

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

В оригинале задача звучит немного по другому, но если я выложу в оригинале, то вы легко найдёте ответ в интернете, что не интересно...дерзайте ).


P.s. задача действительно очень не простая: около часа думал - решения не нешёл, но и прочитав решение далеко не сразу его понял 
P.s. 2 После выходных добавлю одну подсказку ).

P.s. 3 Если точно знаете ответ - пишите что знаете, но не пишите ответ, плиз.

Засекаем. Я начал думать. 23.12

Добавлено @ 23:13
З.Ы.
Тему надо из алгоритмов перенести.

З.Ы.Ы. "Случайный" бог всю малину портит.

Это сообщение отредактировал(а) Kangaroo - 29.8.2008, 23:33

ну мне этот раздел показался наиболее подходящим 

Я встречал более простой (хотя и тоже весьма заковыристый) вариант - где герои (тоже не буду уточнять, кто там фигурировал;) говорили по-нашему и строить словарь их языка было не нужно. Правда, условие там было другое - надо было лишь определить "непостоянного" отвечающего, зато на это давался один-единственный вопрос. Но подозреваю, что дерево решений, по крайней мере для первого хода, будет очень-очень похоже...

SelenIT, угу. Это первый шаг в сабжевой задаче - самый сложный.

ну может, это и не совсем задача по программированию, но в целом, ИМХО, больше сюда подходит...
(перенёс из Алгоритмов)

тут тема умрёт =(.

v2v, у случайного может быть два раза одинаковый ответ?

Hades, 

Так что ты не прав.


З.Ы. Вчера не придумал решение, сегодня некогда было.

Добавлено через 48 секунд
vinter, у случайного все может быть. Поэтому он и случайный.

Это сообщение отредактировал(а) Kangaroo - 30.8.2008, 18:47

да
11111111001010101010000000000000101

v2v, а что разве можно задать один и тот же вопрос, одному богу?

если тебе это поможет то да.

я знаю что это не поможет, но зачем писать

в смысле один вопрос не задаётся сразу двум или более лицам. только по одиночке

точно!

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

v2v, давай подсказки   

SelenIT уже дал подсказку, которую я подтвердил: первым вопросом надо определить кто из богов отвечает не случайно.

итак, ваши варианты ответа вопроса?

Это сообщение отредактировал(а) v2v - 31.8.2008, 21:01

Я вообще думаю, что случайного только за 2 вопроса можно найти (Хотя пока не придумал как). Потому что случайный может "случайно" ответить точно так же как и 1й, и 2й.

Что-то я упускаю..

Это сообщение отредактировал(а) Kangaroo - 30.8.2008, 22:58

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

ЗЫ хм

Это сообщение отредактировал(а) Rpahut - 1.9.2008, 00:29

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

v2v, я так понимаю надо спрашивать о других богах, да?

я ж уже дал подсказку: надо в первом вопросе спрашивать так, что бы однозначно узнать не случайного бога.
Подумайте что вам это даст , какие будут вопросы 2,3?

Судя по то мому, что сказал SelenIT чтобы за один вопрос определить случайного бога из трёх, кам минимум должно быть три варианта ответов. Вариант, когда бог вообще ничего не ответит, допустим по условию задачи?
Если да, то можно, например тогда задать вопрос, на который нет ответа, например "Что было в начале - курица или яйцо. Курица?" Случайный что нить ответит, а правдивый и врун, не должны ответить, потому что нет ответа, а они должны либо говорить правду, либо врать. Так можно узнать, случайный ли тот, которого мы спрашиваем или нет.
Но вот, чтоб с одного вопроса точно определить случайного, даже если они будут отвечать да/нет, это хз   , по моему нельзя....

Это сообщение отредактировал(а) ivg - 1.9.2008, 01:51

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


Мне кажется есть смысл еще разок выписать условия задачи, но другими словами. Где-то чего-то нехватает.

Отсечь одного бога в ходе одного вопроса легко, можно например задать вопрос ответ на который 100% известен, допустим: "Ты бог?". Но в последующем это заводит в тупик, да ещё и алфавита не знаем. Вчера пытался строить дерево решений и в итоге на 1-2 ветки получалась неопределённость, хотя остальные прорешивались.

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

Пока, что я не понимаю, как за один вопрос узнать конкретного бога. Мат. ожидание любого ответа 1/2, вероятность, что бог случаен между всеми богами разделена поровну. Значит при любом первом вопросе/ответе мы с одинаковой вероятностью полагаем, что ответ случаен и не в праве утверждать обратное. 

В условии точно ничего не упущено? Например то, что случайный бог чередует свои ответы? Т.е. в независимости от вопроса он отвечает "да-нет-да-нет" или "нет-да-нет-да". 

Это сообщение отредактировал(а) W4FhLF - 1.9.2008, 06:57

нет, в условиях задачи ничего не упущено!



это очень правильные мысли!

ivg, вы немного не правильно поняли условия задачи: один вопрос - отвечает один бог, а не все вместе перебивая друг друга!

А сложносочинённые вопросы задавать можно? Т.е. вопросы с несколькими условия и/не? 

почему бы и нет ;-)
единственное условие: вопросы должны быть такими что бы однозначно можно было ответить Да/Нет.

Вот к чему я пришёл: 



Везде неопределённость на одной ветке решений. Следовательно один из вопросов надо делать с оператором "и", но тогда рассуждения усложняются. Либо менять вообще стратегию, на какую не знаю 

Это сообщение отредактировал(а) W4FhLF - 1.9.2008, 10:07

W4FhLF,

Retro, я знаю. Если будет полное дерево решений для да/нет, то алфавит роли не играет.

Добавлено через 1 минуту и 44 секунды
Что касается твоего второго замечания: "Ты человек И ты не умеешьлетать?" Можешь ответить на него да/нет? 

Ок.

И это делается односложным вопросом?

del

Это сообщение отредактировал(а) vinter - 1.9.2008, 10:15

А начальное состояние генератора случайных ответов у бога-случайности не задано?

Это то я понял, я и не имел ввиду, что надо задавать один вопрос сразу всем. Вы не ответили на мой вопрос:

Если да, то, с первого вопроса (на который нет ответа) мы можем установить случайный ли тот бог, которому мы этот вопрос задали. Если да, то дальше вроде решается. А вот если он не случайный, что то пока не просёк...
W4FhLF, в любом случае, в начале надо исключить фактор случайности, а иначе другие вопросы бесполезны...

Пока вот это придумал:

Hades, а что ответят другие два, если у них всего два варианта ответа: да; нет. 

W4FhLF, Лгун и Честный должны ответить нет

не могу ответить.


у случайного бога в голове есть монетка : при каждом вопросе он её подбрасывает выпадает решка - отвечает йда , выпадает орел - отвечает тйа, что выпадет первым не может сказать ни один бог 


нет , один вопрос - один ответ да/нет (= тйа/дйа).

Добавлено @ 11:03

это не однозначный вопрос.
ты должен задать такой вопрос что бы боги могли ответить да/нет

НО ЭТО УЖЕ ОЧЕНЬ ГОРЯЧО!!

Это сообщение отредактировал(а) v2v - 1.9.2008, 11:04

Почему? Не улавливаю твою логику рассуждений.

Добавлено через 6 минут и 13 секунд
А может надо спросить что-нибудь типа: "Какое слово получится, если поставить рядом буквы Д и А?"

Добавлено через 7 минут и 11 секунд
Не, под условия задачи не подходит 

1)Первый Честный, значит неслучайный это Лгун, на вопрос 2*2=4, Лгун ответит нет, и на мой вопрос Честный ответит нет
2)Первый Лгун, значит неслучайный это Честный, на вопрос 2*2=4, Честный ответит да, а на мой вопрос Лгун ответит нет

Всё, я понял 

Hades, так так так так ...
теперь да / нет надо перевести на дйа/тйа...

Это сообщение отредактировал(а) v2v - 1.9.2008, 11:18

3) Первый Случайный. 

Что тогда? 

а если это случайный, и он ответит "нет"?

W4FhLF, так в этом то и проблема

я ещё не написал решение, а только хотел узнать, в нужном ли направлении я смотрю.

Ладно, вопрос такой (я задаю его богу): Утвердительно ли ответит случайный бог на вопрос 2x2=4?
v2v, и что мне должен ответить правдивый если он попадётся? Он ведь заранее не знает, что скажет случайный.

Давайте порассуждаем. 

Т.к. один из богов может совершенно случайно выдавать ответы НЕЗАВИСИМО от вопроса. Т.е. это два независимых события, известна лишь их последовательность(сначала вопрос, потом ответ). Если ответ бога не зависит от вопроса, то как мы, вротмненоги, может утверждать, что это точно один из богов, если какой вопрос бы мы ни задали, ответ на него всё равно будет случаен. 

Я где-то не прав?

Добавлено через 1 минуту и 54 секунды





Это сообщение отредактировал(а) W4FhLF - 1.9.2008, 11:37

Вот именно, отсутствие ответа - тоже ответ...

Добавлено через 2 минуты и 39 секунд

кроме случайного, потому что ему по сути пофиг на вопрос, он подкидывает монетку и отвечает

ivg, у нас может одно из двух состояний на выходе: истина (да), ложь (нет). Другого не дано 

Это я понимаю, поэтому и задал вопрос:

ivg, ыыы, зависнет.  

Я тоже думаю, что в двух вариантах (да/нет) задачка неразрешима, по крайней мере, до тех пор пока мы не отсеем случайного бога.

Это сообщение отредактировал(а) ivg - 1.9.2008, 11:55

Итак, ivg нашёл в системе баг. Как будем решать?

Добавлено через 7 минут и 59 секунд


Если бы не SelenIT, который на первой странице не утверждал обратное, то я бы даже не сомневался.  

Просто может мы не в той плоскости мыслим. Никакого интуитивно-понятного ответа тут нет. 

Дак вот меня тоже это смутило. Вариантов ответа два, а богов три. Чтобы точно найти случайного за один вопрос - вариантов ответа тоже должно быть как минимум три.

Имеется 6 вариантов отношения богов ко вранью. Плюс 2 варианта, что какой ответ значит. Итого 12.
Задав три вопроса, мы получим три ответа. Вариантов наборов ответов - 8.

Akina, тут суть в том, что вопросы не должны быть односложными и за один вопрос мы можем получить ответ(или отсеять) на несколько из 12-ти вариантов.

Это очевидно. Но также очевидно, что один из двух вариантов ответа отсеивает не более половины вариантов. 

Я весь день на работе голову ломал  . Не сломал

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

Это сообщение отредактировал(а) Rpahut - 1.9.2008, 18:58

Я думаю что решил, но не уверен... 

Состояние: Если я не решу до среды, то:   *убью себя об стену*

И стану:   *Без зубов, а мозги у меня и так уже довно выбили)))*

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

очень интересный вопрос. по идее правдивый может ответить ДА, потому что случайный как минимум раз ответит ДА. А может ответить НЕТ , потому что случайный ответит НЕТ ... вобщем это не однозначный вопрос и он не влияет.. вы двигаетесь не в ту сторону.


таки не в той...


 

подсказка. в каком то из постов проскольнула мысль, уточню.

Боги, они на то и БОГИ - они знают ВСЁ, всё включает в себя и информацию о своих собратьях! Не спрашивайте то, что вы и так знаете, спросите то, что вам действительно нужно знать!!!

Добавлено через 2 минуты и 27 секунд
я могу озвучить первый вопрос, а общество постарается объяснить что он нам даёт.

Я думаю можно ещё подумать. Как решить задачку точно зная одного из неслучайных богов, я вроде бы знаю.   

Лгун и Честный знают какая сторона монеты выпадет если я что-то спрошу Случайного?

ИМХО предсказательные вопросы должны конкретно адресоваться не-случайным богам. Т.е. вопрос-
если я спрошу правдивого бога "[вопрос правдивому богу здесь]", что он мне ответит?
-допустИм.

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

Добавлено через 2 минуты и 56 секунд

если вы зададите этот вопрос правдивому богу - он ответит правду
лжецу - солжёт
а случайному - ответит случайно.

Кажись я допёр в чём тут фишка   и как исключить фактор случайности, если мы зададим вопрос случайному богу. Короче суть в том, что если мы задаём вопрос случайному богу, то двое других не случайные и если среди них искать не случайного, то ответ случайного не имеет значения. Вот в табличке все варианты расположения богов, задаём вопрос всегда первому. Жирным выделены искомые варианты. Короче если придумать такой вопрос, который соответствующий вариант расположения богов однозначно свяжет с ответом, то из второго или третьего бога можно однозначно определить кто из них не случайный. Ну то есть один вариант ответа будет означать, что не случайный - это второй, а другой вариант, что не случайный - это третий. Поскольку словаря мы их не знаем, то нутром чую, что ихний вариант должен быть как то включён в вопрос.
------------------------
| 1 | 2 | 3 | Ответ |
------------------------
| П | В | С |    Да   |
| П | С | В |    Нет |
| В | П | С |    Да   |
| В | С | П |    Нет |
| С | П | В |     х     |
| С | В | П |     х     |
------------------------
П - правдивый, В - врун, С - случайный

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

а как ты расшифровал их ответы?


так же случайный может два раза соврать

ПОЗДРАВЛЯЮ!
Это правильный вопрос!! Объяснение которое ты предоставил выше, запутано но верно!!
Второй и третий вопросы не представляют собой большой сложности , если найден первый.
Так что, вот оригинал, где всё расписано довольно подробно:
http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

так.. задаем мы этот вопрос случайному, он отвечает "йта". И че дальше? мы не имеем ничего после этого.

vinter, 
Спрашиваем у А.
Если я вас спрошу  "Б случайный?" вы ответите тйа?
А отвечает тйа  = да (Если я вас спрошу  "Б случайный?" вы ответите ДА?)
 - правдивый - сказал правду, Б случайный и он ответит ДА.
 - лжец - он только что соврал сказав ДА, если его спросить Б случайный? то он ответит НЕТ.
 - случайный - А - случайный.

ответ тйа  = нет (Если я вас спрошу  "Б случайный?" вы ответите НЕТ?)
правдивый - сказал правду : Б - случайный, то он не ответит НЕТ.
лжец - солгал - Б - случайный, И ОН ОТВЕТИТ НЕТ.
случайный - А - Случайный.
---------
отсюда заключение: ЛИБО А ЛИБО Б случайны - значит С ТОЧНО не Случайный!!!


Это сообщение отредактировал(а) v2v - 2.9.2008, 14:34

что то я не понимаю твоих рассуждений, каким образом это исключает С из случайности?

Добавлено через 1 минуту и 8 секунд
вообще странная задачка, задачки не должны впадать в ступор от вопроса. 

потому что если бог не случайный и ответил тйа , то значит B- случайный, иначе это отвечал случайный бог.
если же ответ будет йда то можно такими же вариантами доказать что B - точно не случайный(случайный либо А либо С).
Почитай в оригинале , может быть там тебе яснее будет.

Прикольно.
Интересно, это действительно самая сложная логическая игра, или есть сложнее?