Здравствуйте, MichaelP, Вы писали:
MP>Подумав как сделать задачу с идолами разрешимой, родил следующее:
MP>Существуют идолы двух типов: MP>1. Идолы правды всегда говорят правду. MP>2. Идолы лжи могут как ответить правду, так и солгать.
MP>Известно, что идолов правды больше, чем идолов лжи.
MP>За какое количество впросов можно узнать, кто есть кто?
MP>P.S. Мне кажется, что я нашел решение за ~3N вопросов.
См. мой ответ на Идолы-1. Только в твоем случае у каждого всего два состояния, так что и вопросов хватит ровно 100.
Здравствуйте, mihoshi, Вы писали:
M>См. мой ответ на Идолы-1. Только в твоем случае у каждого всего два состояния, так что и вопросов хватит ровно 100.
Мне кажется, что vvaizh более прав — "дипломат" может подстроиться по кого угодно. И на нем метод даст сбой. А я, собственно говоря, "дипломатов" и оставил.
MP>Существуют идолы двух типов: MP>1. Идолы правды всегда говорят правду. MP>2. Идолы лжи могут как ответить правду, так и солгать.
MP>Известно, что идолов правды больше, чем идолов лжи.
MP>За какое количество впросов можно узнать, кто есть кто?
MP>P.S. Мне кажется, что я нашел решение за ~3N вопросов.
Чтобы не возникало вопросов, что есть ложь на "сложновложенных" вопросах, переформулирую пункт два:
2. Идолы лжи выбирают, ответить на вопрос: Да или Нет, из только им известным соображений
Здравствуйте, MichaelP, Вы писали:
MP>Подумав как сделать задачу с идолами разрешимой, родил следующее:
MP>Существуют идолы двух типов: MP>1. Идолы правды всегда говорят правду. MP>2. Идолы лжи могут как ответить правду, так и солгать.
MP>Известно, что идолов правды больше, чем идолов лжи.
MP>За какое количество впросов можно узнать, кто есть кто?
MP>P.S. Мне кажется, что я нашел решение за ~3N вопросов.
Предположим, что N — тепень числа 2,
тогда алгоритм следующий:
а) задаем всем идолам в вопрос "Правда ли, что в группе идолов с 1 по N/2 , идолов правды болльше чем лжи?"
Выясняем каких ответов большенство, выясняем правдивый ответ на вопрос.
б) если правдивых больше в первой половине, то выполняем (а), для первой половины идолов, иначе для второй.
и так, пока в отрезке не останится два идола. (оба правдивые, поскольку число правдивых больше чем лживых.
в) задаем одному из правдивых идолв вопросы о всех оставщихся идолах (N-2 вопросов)
всего задано 3N-6 вопросов.
Метод может быть ускорен до ~2.5N ( в случае соглассованного вранья идолов) и до ~2N (в случае "случайного вранья"), если использовать следующие модификации алгоритма.
1) вопрос в (а) задавать не последовательно всем идолам а поочередно идолам первой и втоой половины группы.
2) Прекращать опрос, как только число ответов "да" или ответов "нет" превысит половину размера множества.
3) исключать из исследуемого множества идолов, ответы которых не совпадают с истиной.
В целом решение совпадает с моим, но есть некоторые тонкости.
C>Предположим, что N — тепень числа 2,
А если нет? C>тогда алгоритм следующий: C>а) задаем всем идолам в вопрос "Правда ли, что в группе идолов с 1 по N/2 , идолов правды болльше чем лжи?" C>Выясняем каких ответов большенство, выясняем правдивый ответ на вопрос. C>б) если правдивых больше в первой половине, то выполняем (а), для первой половины идолов, иначе для второй.
Если N не степень 2, то количество вопросов я более осторожно оценил ~2N C>и так, пока в отрезке не останится два идола. (оба правдивые, поскольку число правдивых больше чем лживых. C>в) задаем одному из правдивых идолв вопросы о всех оставщихся идолах (N-2 вопросов) C>всего задано 3N-6 вопросов.
Опять же, если N != 2^N, то у нас может остаться 1 идол, которому надо задать N-1 вопрос.
C>1) вопрос в (а) задавать не последовательно всем идолам а поочередно идолам первой и втоой половины группы.
Т.к. изначально у нас обе группы равноправны, то, имхо, выигрыша это не даст. C>2) Прекращать опрос, как только число ответов "да" или ответов "нет" превысит половину размера множества. C>3) исключать из исследуемого множества идолов, ответы которых не совпадают с истиной.
Целиком согласен.
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, Chorkov, Вы писали:
MP> В целом решение совпадает с моим, но есть некоторые тонкости.
C>>Предположим, что N — тепень числа 2, MP>А если нет? C>>тогда алгоритм следующий: C>>а) задаем всем идолам в вопрос "Правда ли, что в группе идолов с 1 по N/2 , идолов правды болльше чем лжи?" C>>Выясняем каких ответов большенство, выясняем правдивый ответ на вопрос. C>>б) если правдивых больше в первой половине, то выполняем (а), для первой половины идолов, иначе для второй. MP>Если N не степень 2, то количество вопросов я более осторожно оценил ~2N C>>и так, пока в отрезке не останится два идола. (оба правдивые, поскольку число правдивых больше чем лживых. C>>в) задаем одному из правдивых идолв вопросы о всех оставщихся идолах (N-2 вопросов) C>>всего задано 3N-6 вопросов. MP>Опять же, если N != 2^N, то у нас может остаться 1 идол, которому надо задать N-1 вопрос.
MP> C>>1) вопрос в (а) задавать не последовательно всем идолам а поочередно идолам первой и втоой половины группы. MP>Т.к. изначально у нас обе группы равноправны, то, имхо, выигрыша это не даст. C>>2) Прекращать опрос, как только число ответов "да" или ответов "нет" превысит половину размера множества. C>>3) исключать из исследуемого множества идолов, ответы которых не совпадают с истиной. MP>Целиком согласен.
Группы не могут считаться равноправными, поскольку дипломатам известно в какой подгруппе приобладают правдивые идолы, поэтому стратегия вранья у дипломатов располоэженных в правдивой и в не правдивой подгруппах различна.
Дипломаты в правдивой группе могут говорить правду, чтобы их не отсеяли при переходе к следующей подгруппе. В то время как у дипломатов в подгруппе лжецов, лож сократит число будущих вопросов только на 1 (за счет не задавания вопроса о нем, на последнем этапе тестирования).
Таким образом, дипломаты в подгруппе "правды" говарят правду чаще (не реже) чем дипломаты в лживой группе.
Если дипламаты могут выбирать свое расположение (или, что тоже самое, мы исследуем случай наихудшего расположения), а выбор половины начиная с которой мы исследум множество идолов предсказуем, то оакжется, что большенство дипломатов, расположено в половине, которую мы исследовали первой. Таким образом, число вопросов на каждой итерации деления может возрасти, а число оставшихся идолов будет падать медленнее.
Кстати, нашел ошибку в предудущей оценке (2.5N вопросов)
4) Если в лживом подмножестве выявлено X>N/4 лжецов, то из рассмотрения на следующей итерации исключим (X-N/4) посдених (которым еще не задавались вопросы) идолов. Поскольку вне зависимости от того являются ли исключенные лжецами или нет, в оставшемся подмножестве, все-равно доминируют правдивые.
Правильная оценка 2N, даже при худшем раскладе.
обозначения:
N = число идолов в множестве, исследуемом на текущей итерации (а);
N*K = число задаваемых вопросов на текущей итерации;
N*S = число идоловв множестве, которое будет обработанно на следующей итерации
N*A = число вопросв, заданных чтобы определиться с правдивостью всех идолов
в текущем множестве (включая вопросы заданные на этапе (в)).
N*X = число выявленных на данной итерации лгунов (число полученных ложных ответов)
N*P = число лгунов, выявленных в подмножестве, которое будет признано более правдивым
теперь несколько уравнений:
Задавание вопросов, на данной итерации, будет прекращено, когда число правдивых ответов достигнет N/2
K*N-N*X=N/2
K=X+1/2
На следующей итерации обрабатываются только те идолы из правдивого подмножества, которые не лгуны:
N*S=N/2-N*P
S=1/2-P
Поскольку дипломаты из менее правдивого подмножества должны врать как можно больше. С учетом правила (4),
дипаломаты из лгущего подмножества не заинтересованы давать более чем N/4 ложных ответов.
N*X-N*P=N/4
X-P=1/4
Число вопросов, заданных на текущей итерации: K*N, при этом пределимся с N-N*S идолами.
Число вопросов, которые необходимы чтобы полностью определиться с этими N(1-S) идолами на последнем этапе: N-N*S-N*X
Таким образом:
Здравствуйте, Chorkov, Вы писали:
C>Кстати, нашел ошибку в предудущей оценке (2.5N вопросов)
C>4) Если в лживом подмножестве выявлено X>N/4 лжецов, то из рассмотрения на следующей итерации исключим (X-N/4) посдених (которым еще не задавались вопросы) идолов. Поскольку вне зависимости от того являются ли исключенные лжецами или нет, в оставшемся подмножестве, все-равно доминируют правдивые.
C>Правильная оценка 2N, даже при худшем раскладе.
Я после некоторых рассуждений тоже стал склоняться к такому выводу, но, в отличии от Вас, не дошел до конкретных формул .
C>обозначения: C>N = число идолов в множестве, исследуемом на текущей итерации (а); C>N*K = число задаваемых вопросов на текущей итерации; C>N*S = число идоловв множестве, которое будет обработанно на следующей итерации C>N*A = число вопросв, заданных чтобы определиться с правдивостью всех идолов C> в текущем множестве (включая вопросы заданные на этапе (в)). C>N*X = число выявленных на данной итерации лгунов (число полученных ложных ответов) C>N*P = число лгунов, выявленных в подмножестве, которое будет признано более правдивым
C>теперь несколько уравнений:
C>Задавание вопросов, на данной итерации, будет прекращено, когда число правдивых ответов достигнет N/2 C>K*N-N*X=N/2 C>K=X+1/2
C>На следующей итерации обрабатываются только те идолы из правдивого подмножества, которые не лгуны: C>N*S=N/2-N*P C>S=1/2-P
C>Поскольку дипломаты из менее правдивого подмножества должны врать как можно больше. С учетом правила (4),
Спорное утверждение. Более того, могу показать, что "лжецам" всегда выгодно говорить правду :
Если лжец солжет, то для "компенсации" его лжи понадобиться, в худшем случае, один правдивый ответ, но зато он раскрыл информацию о том, что он лжец, которую мы можем впоследствии использвать (как минимум не выяснять, кто он такой), если же он скажет правду, то на выяснение его принадлежности всегда понадобится лишний вопрос.
И действительно, если все лжецы говорят правду , то в предложенном алгоритме, мы получаем те же ~2N вопросов, о которых Вы и говорили.
К сожалению, данное рассуждение не дает конструктивного алгоритма.
Впрочем, похоже (я не до конца вник в рассуждения) это не влияет на последующие выводы.
Здравствуйте, MichaelP, Вы писали:
MP>Подумав как сделать задачу с идолами разрешимой, родил следующее:
MP>Существуют идолы двух типов: MP>1. Идолы правды всегда говорят правду. MP>2. Идолы лжи могут как ответить правду, так и солгать.
MP>Известно, что идолов правды больше, чем идолов лжи.
MP>За какое количество впросов можно узнать, кто есть кто?
MP>P.S. Мне кажется, что я нашел решение за ~3N вопросов.
У той задачи тоже есть решение )))
И там нужно 2N вопросов )). В твоем случае их нужно N а не 3N (причем условие о том что идолов лжи больше не нужно))
Здравствуйте, MichaelP, Вы писали:
MP>>Существуют идолы двух типов: MP>>1. Идолы правды всегда говорят правду. MP>>2. Идолы лжи могут как ответить правду, так и солгать.
MP>>Известно, что идолов правды больше, чем идолов лжи.
MP>>За какое количество впросов можно узнать, кто есть кто?
MP>>P.S. Мне кажется, что я нашел решение за ~3N вопросов.
MP> MP>Чтобы не возникало вопросов, что есть ложь на "сложновложенных" вопросах, переформулирую пункт два: MP>2. Идолы лжи выбирают, ответить на вопрос: Да или Нет, из только им известным соображений
т.е. идол лжи = генератор случайных ответов. тогда надо подумать )))
В целом решение совпадает с моим, но есть некоторые тонкости.
.
