Версия для печати темы

Автор: 0 16.1.2012, 1:16

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

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



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

Автор: panda-pandus 16.1.2012, 13:23

"начинает отвечать на вопросы на бумажках"
"берет каждый заполненный листок и смотрит однозначно ли определяется персонаж"
"Каждую из оставшихся подсказок он упаковывает в индивидуальный конверт"

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

Автор: 0 16.1.2012, 13:40

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

Автор: panda-pandus 16.1.2012, 16:13

Если я правильно понял условие, то нет.

Если второй ММ определил персонажа, не открыв все конверты - значит, персонаж однозначно определяется без этих неоткрытых конвертов. Но тогда каждый неоткрытый конверт был бы выкинут на этапе отбора.

Или я неправильно понял, как он их выкидывает.

Автор: losse_narmo 16.1.2012, 16:49

Ну если я все правильно понял, то возможны ситуации "досрочного ответа"
Например у нас 3 персонажа и 2 вопроса, при этом ответы:
1) 00
2) 01
3) 11

Тогда открыв конверт и увидев вопрос 1 и ответ "1" однозначно можно сказать, что персонаж 3, не вскрывая второго конверта

Автор: сапер 16.1.2012, 17:05

...Не знаю, но мне кажется , что тему лучше прикрыть..

Автор: Лиходей 16.1.2012, 17:17

Смею предположить, что в общем виде ответ звучит так.

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

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

Автор: 0 16.1.2012, 17:24

Загадывающий это тоже знает и когда проверяет нужность подсказок он выкинет второй конверт

Автор: Powered by Java 16.1.2012, 17:33

Тогда на загаданного 3-его он выкинет все конверты А на первого и второго оставит по одному.

Автор: panda-pandus 16.1.2012, 17:37

Похоже, что все-таки может. Сейчас придумаю пример.

Автор: panda-pandus 16.1.2012, 17:48

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

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

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

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

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

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

Автор: Лиходей 16.1.2012, 17:53

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

Автор: Лиходей 16.1.2012, 18:21

Пусть 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-ех ситуация немного другая, ещё проще.

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

Оно?

Автор: 0 16.1.2012, 18:36

Ну да. Где-то так.
Стоило бы задать вопрос - какая же информация помогла решить.
Ответ на него - количество конвертов.
Можно было попроще - как в примере losse_narmo - три персонажа и два вопроса:
1) 00
2) 01
3) 11
для идентификации первого и третьего достаточно одного конверта соответственно если видим два конверта то можно не вскрывать ни одного.

Правда в вашем примере использование информации о количестве неоткрытых конвертов не столь явно.
А можно ли вообще не использовать эту информацию?
Т.е. отвечающий не знает сколько конвертов - запрашивает у загадывающего их по одному если еще не готов назвать персонажа.

Автор: Лиходей 16.1.2012, 18:51

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

Второй ММ знает, что первый сделал либо (N-1) конвертов полностью с ответами "да", либо N конвертов, где ответов "нет" два или более.

Следовательно, после вскрытия (N-1) конвертов, если в них будет лишь один ответ "нет", второй ММ поймёт, что N-ый конверт существует, и что в нём ответ "нет", после чего можно угадать персонажа.

Автор: panda-pandus 16.1.2012, 18:53

Та же схема.

1) 00
2) 01
3) 11

Открываем конверт - видим там первый вопрос и ответ 0.
Чтобы угадать персонажа этого недостаточно - значит, будет второй конверт.
Будет второй конверт - значит, это второй персонаж.

Автор: Лиходей 17.1.2012, 10:58

А обещанное усложнение будет?

Автор: losse_narmo 17.1.2012, 12:09

Просьба уточнить вопрос.
То есть есть "набор" персонажей и вопросы.
Я прошу следующий конверт, открываю его. Вижу вопрос и ответ. Если не готов сказать персонажа, то прошу следующий конверт и так далее.
Тогда вопросы-уточнения:
1) могу ли я "нарваться" на ситуацию, что конвертов больше нету.
2) могу ли я взяв новый конверт ответить не вскрывая его. Тогда опять получается неявное использование информации о количестве конвертов.

Автор: panda-pandus 17.1.2012, 12:34

А как такое может быть?

1. По условию первый ММ выбирает такой набор подсказок, чтобы по ним можно было однозначно угадать персонажа. Если вскрыты уже все конверты, то как второй ММ мог все еще не угадать (и запросить еще конверт)?

2. То же самое. Если из уже открытых конвертов персонаж угадывается однозначно - то второй ММ не запросит еще один конверт, а назовет ответ. Если же персонаж еще не угадывается однозначно, то наличие еще хотя бы одного конверта - уже известный факт, и, взяв его, мы не получим никакой новой информации, пока не вскроем.

Автор: losse_narmo 17.1.2012, 13:32

Все, немного для себя разобрался, будем думать.
Тогда для схемы выше будет чуть иначе:

1) х0
2) 01
3) 1х

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