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

dragan24

Когда решал ее в прошлом году, убил пару дней
Мож кто заинтересуется. А то вон целый некий форум бьется уже две недели, не может решить.
Вашу незначительную персону почтили своим присутствием трое богов. Их зовут True, False и Random. Бог по имени True всегда говорит правду, бог по имени False всегда лжёт, а бог по имени Random отвечает на все вопросы совершенно случайным образом.
К сожалению, вы не знаете, кто из них кто. Обозначим троих богов буквами A, B и C. Вы не знаете, кто из A, B и C на самом деле True, кто False, а кто Random. Сами боги это знают (о себе и других).
У вас есть возможность задать им три вопроса, на каждый из которых можно ответить только "да" или "нет". Hеобязательно задавать каждому богу по одному вопросу; вы можете, если вам хочется, задать все три вопроса одному и тому же богу, или ещё как-нибудь. Вопросы задаются по порядку, то есть, например, в зависимости от ответа на первый вопрос вы можете выбрать, кому задавать второй вопрос и каким он будет.
Боги понимают ваш язык и ваши вопросы, но отвечают всегда на своём языке. В этом языке вместо "да" и "нет" говорят "oui" и "ja". К сожалению, вы не знаете, что из них означает что - может быть, "oui" это "да", а "ja" - "нет", а может и наоборот.
Ваша задача: с помощью этих трёх вопросов точно определить, кто из них кто.
Замечание: На вопросы, ответ на которые неопределен, боги не-рандомы отвечают как рандом. Это чтобы никто не читерил

greekdom

Пиши ответ фигли

Ramm13

ну если мне кто скажет как вычислить рэндома, то я скажу как вычислить кто тру/фалс, и как на их языке да/нет соответственно
как вычислить рэндома: варианты перебирать ломает, а найти правильный вопрос, если таковой существует, тоже ломает.

dragan24

хрен! (в хорошем смысле этого слова) %)
пусть сначале мозги попухнут %)

dragan24

не слишком ли много вы хотите?

Ramm13

а хз =)

estochka

а ты сам дошел до ответа ?

dragan24

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

filippov2005

Теоретически ответ может существовать, что не может не радовать
С помощью ответов oui/ja на 3 вопроса теоретически мы можем различить 8 вариантов неизвестных условий. У нас искомые условия могут принимать 3! = 6 < 8 различных вариантов, поэтому таким способом д-ть неразрешимость нельзя
Правда, пока не понятно как влияет на ситуацию рэндом. Возможно, его присутствие делает ситуацию строгой, в том смысле, что гарантировано от трех богов мы можем состояние условия, которое принимает 6, а не 8 вариантов. Если это правильно и можно это доказать, то мб из доказательства выйдет и стратегия.
Правда, получается, что не всегда нам удастся узнать какое слово означает да, а какое нет, так как иначе мы смогли бы различить 3!*2 = 12 ситуаций.
Кроме того наша стратегия не должна быть инвариантной относительно замены oui - ja иначе мы сможем различить только 4 случая. Это наводит на определенные мысли на содержание вопросов.
А это задача всему форуму или лучше решать по отдельности? Интересно ее мозговым штурмом взять

dragan24

первое замечание очень даже имеет право на существование
предыдущие решатели собирались различать 12 комбинаций и пришли к выводу, что решения нет (а оно есть ).
А это задача всему форуму или лучше решать по отдельности? Интересно ее мозговым штурмом взять
Кто же вам мешает? Берите

filippov2005

предыдущие решатели собирались различать 12 комбинаций и пришли к выводу, что решения нет (а оно есть ).
Погоди, есть решение, которое отличает 12 комбинаций?
Но по принципу дирихле, на один из 8 вариантов ответа получится хотя бы две комбинации

dragan24

Погоди, есть решение, которое отличает 12 комбинаций?
Но по принципу дирихле, на один из 8 вариантов ответа получится хотя бы две комбинации
Ну это сути не меняет, получаицо %)

a7137928

Ну это сути не меняет, получаицо %)
Такое действительно теоретически возможно, если по трем вопросам мы узнаем, кто есть кто, но не узнаем, какое слово означает "да".

bredjuk

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

Sanych

Есть, между прочим, неплохая формула:
Является ли oui правильным ответом на вопрос (...)?
Ответ oui надо переводить как ответ "да" на (...)
ja соответственно как "нет" на (...)
С ней про так называемый язык богов мы можем совершенно забыть

naami_moloko

Перебор на 6*8 вариантов?

filippov2005

Круто!
Правда, после такой подсказки решать почти нечего
Можно считать, что и лжец, и рыцарь говорят правду:
Что бы ты ответил, если бы я задал вопрос (...)?
С помощью этой формулы несложно одним вопросом выяснить, кто из богов не рандом. И у него двумя вопросами выяснить кто рыцарь, а кто лжец. Вот и все...
ЗЫ Зато какие вопросы у нас закавыристые получились :
"Является ли oui правильным ответом на вопрос (Что бы ты ответил, если бы я задал вопрос (...)?)?"

Cepy

Такое действительно теоретически возможно, если по трем вопросам мы узнаем, кто есть кто, но не узнаем, какое слово означает "да".
А вот этого я совсем не понимаю. Допустим, мы решили задачу. То есть теперь мы знаем, кто есть кто. И мы знаем вопросы. То есть мы знаем правильные ответы (да или нет). И мы знаем, что, скажем, ответил Тру. Вот это слово и есть правильный ответ. То есть, если правильный ответ - да, и Тру ответил ja, то ja - это да. А oui - соответственно нет. И наоборот.
Или я чего-то не понимаю?

filippov2005

Не понимаешь. Ошибка в твоих рассуждениях в переходе от
То есть теперь мы знаем, кто есть кто. И мы знаем вопросы
к
То есть мы знаем правильные ответы (да или нет).
Например, мы знаем, что первый - рыцарь. И мы его спросили:
Верно ли, что qui - это правильный ответ на вопрос: "ты рыцарь?". Он нам, конечно, ответил: "qui" независимо от того обозначает ли это слово "да" или же это переводится "нет".
Наверно, запутано...
Короче, мы не сможем узнать, как на человеческом языке звучал бы ответ рыцаря на вопрос: Верно ли, что qui - это правильный ответ на вопрос: "ты рыцарь?"

Cepy

Теперь понял. Переход-то правильный, фишка именно в том, что мы, по сути, и сами вопросы не знаем

agroprom

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

filippov2005

этот один вопрос можно задать только одному богу
Ты поняла правильно.
Одним первым вопросом, задав его одному богу, можно определить кто из богов точно не рандом.
как?
Надо воспользоваться формулой:
Является ли oui правильным ответом на вопрос (Что бы ты ответил, если бы я задал вопрос (...)?)?
Вместо многоточия вставляешь свой вопрос. Ты можешь считать, что ответом на твой вопрос (который вместо многоточия) будет "да" или "нет". Причем рандом отвечает на твой вопрос случайно, а не рандом всегда отвечает правду.

filippov2005

Конечно, мой ответ не полный, т.к. сам вопрос я не формулирую. Это я оставляю "на подумать" (с)
Оставшаяся часть задачки выглядит так.
Есть три бога: два рыцаря и рандом. Рыцарь всегда говорит правду. Рандом отвечает случайно.
Как с помощью одного вопроса одному богу, ответ на который "да" или "нет", точно определить бога, который не может быть рандомом?

filippov2005

Ты знаешь 6*8 стратегий вопросов, такие что любая стратегия изоморфна одной из них?
Можно поподробнее

natunchik

Полтора часа трахался, наконец рюхнул. Первая табличка иллюстрирует идею вдремова, вторая - пуха, третья - собственно как правильно задавать вопросы.

Если спросить (1) "Является ли 'oui' правильным ответом на вопрос 'XXX' ?":
(1)=t 'oui'='true', answer='oui' => XXX = true
(1)=t 'oui'='true', answer='ja' => XXX = false
(1)=t 'oui'='false', answer='oui' => XXX = true
(1)=t 'oui'='false', answer='ja' => XXX = false
(1)=f 'oui'='true', answer='oui' => XXX = false
(1)=f 'oui'='true', answer='ja' => XXX = true
(1)=f 'oui'='false', answer='oui' => XXX = false
(1)=f 'oui'='false', answer='ja' => XXX = true
То есть в такой формулировке ответ 'oui' соответствует ответу 'true', 'ja' - 'false'

Что бы ты ответил, если бы я спросил YYY.
(1)=t, YYY=t, answer = true
(1)=t, YYY=f, answer = false
(1)=f, YYY=t, answer = true (потому что на YYY он бы ответил false)
(1)=t, YYY=f, answer = false
Таким образом для вопроса "Является ли 'oui' правильным ответом на вопрос 'Что бы ты ответил, если бы я спросил ХХХ'?" ответ 'oui' соответствует истинности 'XXX', 'ja' - ложности.
Теперь у нас есть прекрасная форрмулировка, но когда мы задаём первый вопрос, то мы в двух случаях из 6 попадаем на рандома, выкидывая максимум два случая. Поэтому следующие вопросы следует задавать так, чтобы гарантированно половинить вероятности (то есть нельзя спрашивать предположительного рандома, например).

t f r | f t r | t r f | f r t | r t f | r f t
1: Спрашиваем (1 XXX = "Является ли (3) рандомом?"
true: 1 1 0 0 1 1
Отсюда 2 точно не рандом.
2: Спрашиваем (2 XXX = "Является ли (2) тру?"
true: 0 1 - - 1 0
далее очевидно т.к. (2)=true, можем у него прямым текстом узнать кто (3 иначе
false: 1 0 - - 0 1
далее очевидно т.к. (2)=false, можем у него прямым текстом узнать кто (3)

Если же ответ на первый вопрос - false, то есть

1: Спрашиваем (1 XXX = "Является ли (3) рандомом?"
false: 0 0 1 1 1 1
(3) точно не рандом, спрашиваем у него в той же формулировке "Является ли (3) тру?",
поэтому из ответа точно узнаём кто он и так далее.

natunchik

Да, такая длинная формулировка нужна только для первого вопроса, на самом деле. Дальше можно спрашивать уже вопросы вида "Является ли 'oui' правильным ответом на вопрос ХХХ".

filippov2005

когда мы задаём первый вопрос, то мы в двух случаях из 6 попадаем на рандома, выкидывая максимум два случая
нельзя спрашивать предположительного рандома
Респект
Про то, что первым вопросом надо обязательно выяснить одного не рандома, я пришел по другим соображениям достаточно запутанным, если не сказать интуитивным.
ЗЫ И таблички замечательные

filippov2005

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

Cepy

Причем рандом отвечает на твой вопрос случайно, а не рандом всегда отвечает правду.
И что будет, если рандом ответит правду?
Я понимаю, если он ответит ложь, тогда сразу ясно, что он рандом.

filippov2005

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

dragan24

Монстры! %) Взяли-таки штурмом
Круто!
Правда, после такой подсказки решать почти нечего
На самом деле додуматься до такого несложно, если приходилось хоть раз решать задачки про рыцарей и лжецов. Но ввиду того, что ответы у нас непростые, приходится формулу немного доработать.
2Сатурн: Если мы задаем богу А вопрос "Ответил бы ты мне oui, если бы я тебя спросил об истинности высказывания (Бог В есть рандом)?", то в любом случае либо А - рандом (с этим ничего не поделаешь либо один из двух других. А именно, при ответе oui - либо А рандом, либо В; при ответе ja - либо А рандом, либо С. Таким образом, за один вопрос мы вычисляем одного точно нерандома

dragan24

Вот мое решение в полном виде с табличкой для наглядности

1. Изначально мы имеем 6 разных возможных вариантов (6 перестановок из 3
элементов):
TRF
TFR
RTF
RFT
FTR
FRT

2. Если у нас есть возможность задать 3 вопроса (и получить на них 3
ответа типа 0 или 1 значит всего мы получим 3 бита информации. Ими
можно закодировать 8 различных вариантов. Так как 8 > 6, значит
теоретически задачу решить можно :)

3. Узнать "ja" = "да" или "ja" = "нет" мы за 3 вопроса не можем, так
как в противном случае мы получили бы 12 возможных вариантов и 8 различных
исходов на основе полученных ответов (8 < 12).

коммент: если мы допускаем возможность задавать богам вопросы, на
которые они не могут дать ответа, то имеем уже не 8 вариантов (2^3 а
27 (3^3). Этого должно хватить для задачи с 4-мя богами :)

4. Заметим следующее:
Если мы задали богу не-рандому вопрос "Ответил бы ты мне ja, если бы
я тебя спросил <вопрос>?" и получили на него ответ ja, то это
означает, что мы получили ответ "да" на <вопрос>. Это легко можно
проверить (очень похоже на стандартный прием с двойным отрицанием в
задачах про лгунов).
Введем обозначение: [вопрос] = "Ответил бы ты мне ja, если бы я тебя
спросил <вопрос>?".

5. Собственно алгоритм:
1) Спрашиваем у бога А [B = R?], то есть является ли бог B рандомом.
1.+) В случае ответа ja либо A = R, либо B = R.
1.-) В случае ответа oui либо A = R, либо C = R.
2) У бога, который точно не рандом, спрашиваем [A = R?].
2.+) В случае ответа ja A=R. И спрашиваем повторно у того же бога
[оставшийся бог = T ?].
2.-) В случае ответа oui рандомом является бог, которого мы еще не
спрашивали. Спрашиваем у этого же бога [A = T?].

Вот как это будет выглядеть более наглядно:

Запись <xyz|yzx> означает что возможны 2 варианта xyz (A = x, B = y, C = z)
или yzx (A = y, B = z, C = x).

<TFR|TRF|RTF|RFT|FTR|FRT>
Спросили у бога А [B=R?]
|
|---------------------------------------|
ja oui
| |
<RTF|RFT|TRF|FRT> <RTF|RFT|TFR|FTR>
Спросили у бога С [A = R?] Спросили у бога B [A = R?]
| |
|------------------| |-------------------|
ja oui ja oui
| | | |
<RTF|RFT> <TRF|FRT> <RTF|RFT> <TFR|FTR>
Спросили у С: Спросили у C: Спросили у В: Спросили у А:
[B = T?] [A = T?] [C = T?] [B = T?]
| | | |
|--------| |--------| |---------| |---------|
ja oui ja oui ja oui ja oui
| | | | | | | |
RTF RFT TRF FRT RFT RTF FTR TFR

dragan24

Кроме того наша стратегия не должна быть инвариантной относительно замены oui - ja иначе мы сможем различить только 4 случая. Это наводит на определенные мысли на содержание вопросов.
Только что с Украины пришло решение задачи с вопросами, инвариантными относительно данной замены %) Хотя стратегия в целом не инвариантна. Сейчас посмотрим, является ли это решение тем, чем хочет быть, по своей сути; хотя форма меня уже порадовала

naami_moloko

Зря рассказал так рано

dragan24

Не. Кажись бред я сморозил в предыдущем сообщении. По поводу неинвариантности стратегии с инвариантными вопросами
Не прокатило такое красивое решение

dragan24

Да тут уж и решать-то оставалось нечего %) Неужели вы бы долго думали над тем, какой вопрос задается первому богу (если известна форма задавания вопроса)?

naami_moloko

Да нет конечно, но всё-таки А вообще задачка очень хорошая.
Оставить комментарий
Имя или ник:
Комментарий: