Бесполезная но необходимая информация Опции Рейтинг

[0]

Два ММ играют в игру. Один загадывает персонажа другой его отгадывает с помощью подсказок.
Подсказка это некий вопрос с ответом да или нет. Вопросы задает загадывающий и сам на них отвечает.
Так как ММ давно играют в эту игру друг с другом каждый знает всех персонажей которые могут быть загаданы. Плюс к этому ММ пришли к набору вопросов который однозначно идентифицирует любого персонажа и поэтому договорились пользоваться только этими вопросами.
Вообщем игра превратилась в рутину:
Первый ММ выбирает персонажа. Потом начинает отвечать на вопросы на бумажках до тех пор пока не поймет что персонаж определен однозначно. Затем берет каждый заполненный листок и смотрит однозначно ли определяется персонаж без этой подсказки, и если однозначно то выкидывает его. Каждую из оставшихся подсказок он упаковывает в индивидуальный конверт и отправляет второму.

Может ли оказаться что второй ММ назовет персонажа до того как откроет все конверты?



PS: можно писать прямо тут - т.к. это простая загадка и будет усложнение.

[panda-pandus]

Пусть персонажи - Буратино, Чак Норрис, Путин и краб.

Вопросов 4:
1. Это Буратино, Чак Норрис или Путин?
2. Это Чак Норрис?
3. Это Путин?
4. Это Путин или краб?

ММ1 загадал Путина. Вытянул карточки 1 и 4.
1. Это Буратино, Чак Норрис или Путин? - Да
4. Это Путин или краб? - Да
Однозначно определяют персонажа, выкинуть ни одну нельзя.

ММ2 открывает первую карточку:
1. Это Буратино, Чак Норрис или Путин? - Да

Он думает, что он может увидеть на оставшейся карточке, когда откроет:
"2 да" - тогда первую бы выкинули.
"2 нет" - тогда не хватит информации, чтобы угадать, а это не по правилам
"3 да" - тогда первую бы выкинули
"3 нет" - тогда не хватит информации, чтобы угадать, а это не по правилам
"4 нет" - тогда не хватит информации, чтобы угадать, а это не по правилам

Значит, остается только "4 да", и он отвечает "Путин", не открывая карточку.

[Лиходей]

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

[Лиходей]

Пусть N - количество вопросов.
При количестве персонажей 2^N второй ММ не может заранее угадать персонажа, так как каждая комбинация отвечает одному персонажу.

Рассмотрим один конкретный пример, когда количество персонажей - (2^N-1)

Представим вирутального 2^N-ого персонажа, при добавлении которого в список персонажей однозначность угадывания сохранилась бы. Для удобства примем, что все ответы на вопросы по этому персонажу - ДА.

Рассмотрим действия первого ММа.
Существуют персонажи, однозначность которых определяется по (n-1) вопросов. Это те, для которых все ответы на вопросы - ДА, кроме одного. Их количество - N.
Второму ММу для того, чтобы определить персонажа, придётся открыть все (n-1) конвертов.
Это группа персонажей №1.

Для остальных 2^N-N первый мегамозг отдаст все N ковернтов со всеми N вопросами.
Это группа персонажей №2.
И вот тут уже второй мм может угадать заранее (если повезёт)

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

Следовательно, персонажи из группы №2 всегда имеют 2 или больше ответов "нет". От этого и пляшем.
Если второй ММ, вскрывая конверты, вскроет (n-2) конвертов с ответом "да", то может быть уверен в том, что в оставшихся (одном или двух) конвертах ответ "нет". То есть он отгадает персонажа, не вскрывая эти оставшиеся конверты.

При N меньше 3-ех ситуация немного другая, ещё проще.

Если количество персонажей уменьшать ещё больше, ситуация для второго ММа будет всё благоприятней и благоприятней, там количество вариантов будет ещё больше. Сомневаюсь, что там появится какой-то "вырожденный" случай в результате которого не будет существовать такой ситуации, когда второй ММ угадывает персонажа заранее.

Оно?