Бредовая задачка (сам придумал).

Перед вами 100 идолов.

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

(количество идолов конкретного типа — случайно).

У вас 200 вопросов чтобы понять кто есть кто (где стоят какие идолы).

Дополнения:

1 вопрос — это вопрос заданный конкретному идолу.

Вопросы такие, чтобы ответ был Да или Нет (и все, идолы больше ничего не могут делать и не могу давать дополнительную информацию (типа прыгать или молчать) ).

Нельзя задавать вопросы, на которые идолы не знают ответа (в этом случае они от злости разрывают вас на части )).

Идолы знают друг о друге всю правду.

Идолы не знают что ответит другой идол на следующий вопрос (т.к. не знают будущего).

Здравствуйте, Gena_Popov, Вы писали:

GP>Бредовая задачка (сам придумал).

GP>Перед вами 100 идолов.

GP>Идолы бывают 3х типов
GP>- идол лжи всегда лжет
GP>- идол правды всегда говорит правду
GP>- идол дипломатии может соврать, а может сказать правду (т.е. при ответе на конкрентый вопрос, он как-бы становится либо идолом правды, либо идолом лжи)

GP>(количество идолов конкретного типа — случайно).

GP>У вас 200 вопросов чтобы понять кто есть кто (где стоят какие идолы).

GP>Дополнения:

GP>1 вопрос — это вопрос заданный конкретному идолу.

GP>Вопросы такие, чтобы ответ был Да или Нет (и все, идолы больше ничего не могут делать и не могу давать дополнительную информацию (типа прыгать или молчать) ).

GP>Нельзя задавать вопросы, на которые идолы не знают ответа (в этом случае они от злости разрывают вас на части )).

GP>Идолы знают друг о друге всю правду.

GP>Идолы не знают что ответит другой идол на следующий вопрос (т.к. не знают будущего).

ИМХО поведение системы "все дипломаты" может полностью эмулировать поведение системы "все лжецы" или "все правдецы", соответственно в этом случае ты ничего толком не узнаешь ни за какое количество вопросов..

Здравствуйте, Gena_Popov, Вы писали:

GP>Бредовая задачка (сам придумал).

GP>Перед вами 100 идолов.

GP>Идолы бывают 3х типов
GP>- идол лжи всегда лжет
GP>- идол правды всегда говорит правду
GP>- идол дипломатии может соврать, а может сказать правду (т.е. при ответе на конкрентый вопрос, он как-бы становится либо идолом правды, либо идолом лжи)

А можно им вопрос из нескольких частей состовлять, хотя ответом все равно будет Да/Нет. например:
"вы при ответе на мой вопрос скажете правду и вы идол правды???"
???

V>ИМХО поведение системы "все дипломаты" может полностью эмулировать поведение системы "все лжецы" или "все правдецы", соответственно в этом случае ты ничего толком не узнаешь ни за какое количество вопросов..

Я бы даже сказал, что это своеобразный Генератор Псевдо Случайных Чисел (по какому принципу он там решает как отвечать одному богу известно)

Здравствуйте, Gena_Popov, Вы писали:

GP>Перед вами 100 идолов.

GP>Идолы бывают 3х типов
GP>- идол лжи всегда лжет
GP>- идол правды всегда говорит правду
GP>- идол дипломатии может соврать, а может сказать правду (т.е. при ответе на конкрентый вопрос, он как-бы становится либо идолом правды, либо идолом лжи)

GP>(количество идолов конкретного типа — случайно).

GP>У вас 200 вопросов чтобы понять кто есть кто (где стоят какие идолы).

Это делается примерно так. Составляется шаблон вопроса так, чтобы в него можно было вставить любой вопрос и на полученный в результате расширенный вопрос любой отвечал бы так, как правдец на вставленный. Для этого в шаблоне должно быть утверждение о правдивости самого ответа. Например

Правда ли, что $s верно если и только если, когда вы отвечаете мне на этот вопрос правдиво. (согласен, можно придумать и получше)

$s <- сюда вставляется утверждение, ответ на который вы хотите получить.

Болдом выделено условие эквивалентности, если кто не признал.

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

Например, при $s = "Волга впадает в Каспийское море?"

Если он говорит правду, то вторая часть — верна, первая — верна, он говорит "Да".
Если неправду, то вторая часть — неверна, первая — верна, утверждение неверно, соответственно он говорит "Да".

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

Подходим к первому, объясняем ему про системы счисления и начинаем спрашивать про представление состояния идолов в двоичной системе. Итого 100 * ln3/ln2 вопросов, округление вверх.

Здравствуйте, Gena_Popov, Вы писали:

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

Дополнитльное уточнение (по материалам обсуждения):

Когда дипломат решает отвечать на вопрос пользуется ли он системой станпиславского?
Т.е. верит ли он сам в то что он действительно тот за кого себя признаёт?
Т.е. до какой степени полностью он становится либо лжецом либо правдецом?

если верит, то отвечая за правдеца "правда ли что вы правдец" он ответит "да",
так как дейститвельно в данный момент он превратился в правдеца и является им..

Здравствуйте, Gena_Popov, Вы писали:

GP>Перед вами 100 идолов.

GP>Идолы бывают 3х типов
GP>- идол лжи всегда лжет
GP>- идол правды всегда говорит правду
GP>- идол дипломатии может соврать, а может сказать правду (т.е. при ответе на конкрентый вопрос, он как-бы становится либо идолом правды, либо идолом лжи)
GP>(количество идолов конкретного типа — случайно).
GP>У вас 200 вопросов чтобы понять кто есть кто (где стоят какие идолы).
GP>Дополнения:
GP>1 вопрос — это вопрос заданный конкретному идолу.
GP>Вопросы такие, чтобы ответ был Да или Нет (и все, идолы больше ничего не могут делать и не могу давать дополнительную информацию (типа прыгать или молчать) ).
GP>Нельзя задавать вопросы, на которые идолы не знают ответа (в этом случае они от злости разрывают вас на части )).
GP>Идолы знают друг о друге всю правду.
GP>Идолы не знают что ответит другой идол на следующий вопрос (т.к. не знают будущего).

Предположим что идол стоят в ряд: тогда совсем мало вопросов

1. Подходим к каждому идолу и задаем 3 вопроса "Идол правды?" "Второй идол правды?" "Третий идол правды?"
Результаты ответов такие:

                    | П | Л | Д |
--------------------------------
П(вопрошаемый идол) | 1 | 0 | 0 |
--------------
Л(вопрошаемый идол) | 0 | 1 | 1 |
--------------
Д(вопрошаемый идол) |0/1|0/1|0/1|
--------------------------------

Теперь намного проанализируем таблицу, точнее последнюю строку
0 0 0 — однозначно дипломат
1 1 1 — однозначно дипломат
В этом случае все уже решено

Иначе
1 0 0 — имеем стопроцентного лжеца с комбинацей 0 1 1
0 1 0 — имеем стопроцентного лжеца с комбинацей 0 1 1
0 0 1 — имеем стопроцентного лжеца с комбинацей 0 1 1

1 1 0 — имеем стопроцентного правдивца с комбинацей 0 0 1
0 1 1 — имеем стопроцентного правдивца с комбинацей 0 0 1
1 0 1 — имеем стопроцентного правдивца с комбинацей 0 0 1

Допустим нашли стопроцентного правдивца, тогда задаем у него всего один вопрос "Второй идол — идол лжи?": Да — Второй — Лжец, Третий Дипломат; иначе наоборот.

И последний вариант: Нашли лжеца => внимательно смотрим на строку №2 и теперь вдруг понимаем "финит аля комедия!!!"

Здравствуйте, uzzy, Вы писали:

единственный косяк: забыл, что имеется 100 идолов

Здравствуйте, vvaizh, Вы писали:


V>Дополнитльное уточнение (по материалам обсуждения):

V>Когда дипломат решает отвечать на вопрос пользуется ли он системой станпиславского?
V>Т.е. верит ли он сам в то что он действительно тот за кого себя признаёт?
V>Т.е. до какой степени полностью он становится либо лжецом либо правдецом?

V>если верит, то отвечая за правдеца "правда ли что вы правдец" он ответит "да",
V>так как дейститвельно в данный момент он превратился в правдеца и является им..

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

Другое дело, что тогда лучше не спрашивать у идола о нем же.

Здравствуйте, SiAVoL, Вы писали:

V>>ИМХО поведение системы "все дипломаты" может полностью эмулировать поведение системы "все лжецы" или "все правдецы", соответственно в этом случае ты ничего толком не узнаешь ни за какое количество вопросов..

SAV>Я бы даже сказал, что это своеобразный Генератор Псевдо Случайных Чисел (по какому принципу он там решает как отвечать одному богу известно)


Я все-таки утверждаю что решение есть и я его расскажу через некоторое время.

Здравствуйте, vvaizh, Вы писали:

V>Здравствуйте, Gena_Popov, Вы писали:

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

V>Дополнитльное уточнение (по материалам обсуждения):

V>Когда дипломат решает отвечать на вопрос пользуется ли он системой станпиславского?
V>Т.е. верит ли он сам в то что он действительно тот за кого себя признаёт?
V>Т.е. до какой степени полностью он становится либо лжецом либо правдецом?

V>если верит, то отвечая за правдеца "правда ли что вы правдец" он ответит "да",
V>так как дейститвельно в данный момент он превратился в правдеца и является им..


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

Здравствуйте, uzzy, Вы писали:

U>Здравствуйте, uzzy, Вы писали:

U>единственный косяк: забыл, что имеется 100 идолов

и всего 200 вопросов ))

Здравствуйте, mihoshi, Вы писали:

M>Здравствуйте, Gena_Popov, Вы писали:

GP>>Перед вами 100 идолов.

GP>>Идолы бывают 3х типов
GP>>- идол лжи всегда лжет
GP>>- идол правды всегда говорит правду
GP>>- идол дипломатии может соврать, а может сказать правду (т.е. при ответе на конкрентый вопрос, он как-бы становится либо идолом правды, либо идолом лжи)

GP>>(количество идолов конкретного типа — случайно).

GP>>У вас 200 вопросов чтобы понять кто есть кто (где стоят какие идолы).

M>Это делается примерно так. Составляется шаблон вопроса так, чтобы в него можно было вставить любой вопрос и на полученный в результате расширенный вопрос любой отвечал бы так, как правдец на вставленный. Для этого в шаблоне должно быть утверждение о правдивости самого ответа. Например

M>Правда ли, что $s верно если и только если, когда вы отвечаете мне на этот вопрос правдиво. (согласен, можно придумать и получше)

M>$s <- сюда вставляется утверждение, ответ на который вы хотите получить.

M>Болдом выделено условие эквивалентности, если кто не признал.

M>Тогда если демон соврет, то вторая часть утверждения ложна, следовательео чтобы все оно было ложно первая часть должна быть истинна. Если он скажет правду, то тогда на первую часть он также ответил правду.

M>Например, при $s = "Волга впадает в Каспийское море?"

M>Если он говорит правду, то вторая часть — верна, первая — верна, он говорит "Да".
M>Если неправду, то вторая часть — неверна, первая — верна, утверждение неверно, соответственно он говорит "Да".

M>Таким образом нам пофигу говорит ли идол правду или нет, мы можем получить правильный ответ у любого идола на лбой вопрос.

M>Подходим к первому, объясняем ему про системы счисления и начинаем спрашивать про представление состояния идолов в двоичной системе. Итого 100 * ln3/ln2 вопросов, округление вверх.

А можно попонятней объяснить? ))
Какие именно вопросы будешь задавать идолам?

Здравствуйте, Gena_Popov, Вы писали:

M>>Подходим к первому, объясняем ему про системы счисления и начинаем спрашивать про представление состояния идолов в двоичной системе. Итого 100 * ln3/ln2 вопросов, округление вверх.

GP>А можно попонятней объяснить? ))
GP>Какие именно вопросы будешь задавать идолам?

Принцип шаблона понял?
Вопросы задаем так.

"Пронумеруем состояния идолов так: 0-лжец, 1-правдец, 2-дипломат. Тогда состояние всех идолов описывается 100значным троичным числом. Переводим его в двоичную систему. Назовем это число индексом состояния идолов. Внимание: вопрос. верно ли, что i-я цифра в индексе состояния равна 1?"

Так бы мы спросили, если бы точно знали, что идол — правдец. Так как мы этого не знаем, то мы засовываем этот вопрос в шаблон.

Таким образом в цикле по i выясняем все цифры индекса состояния, переводим его обратно в троичную систему и получаем число, полностью описывающее состояние всех идолов. J-й идол имеет такое состояние, какая J-я цифра в троичной записи индекса состояния.