задачка

[avva]

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

Три человека входят в комнату. Для каждого из них бросают честную монету, и в зависимости от ее исхода надевают на голову красную либо синюю шляпу, с вероятностью 1/2 каждого исхода. Каждый видит цвета шляп двоих других игроков, но не цвет своей шляпы.

Любые средства передачи информации между игроками запрещены (кроме того, что им разрешается договориться об общей стратегии до начала игры, до того, как они входят в комнату). После того, как они увидели шляпы других игроков, по общему сигналу они все одновременно объявляют либо догадку насчет цвета своей шляпы - красный или синий - либо "пас". Если хотя бы один игрок правильно угадал цвет своей шляпы, и ни один из игроков не ошибся (пас не считается ошибкой), они получают 3 миллиона долларов. Если же была неправильная версия, или все трое сказали пас, они ничего не получают.

Какая стратегия приносит им наибольший шанс выиграть деньги? Скажем, если они заранее договорятся, что один из них скажет "красный", а двое других "пас", то вероятность выигрыша будет 50%. Можно ли улучшить этот результат?

Я пока что придумал решение, дающее 75%. Не знаю, лучшее ли это возможное.

Comments

[justsoul.livejournal.com]

Тоже нашел 75% и лучше имхо нельзя.

[avva.livejournal.com]

Да, мне тоже так кажется.

[monomyth.livejournal.com]

1й игро заходи одевает шляпу, второй игрок зачодит, одевает шляпу, становится справа от первого, третий игрок заходит, одевает шляпу и становится сорава от второго, если у него шляпа красная или слева от первого если у него шляпа красная. Он говорит "пас".

[monomyth.livejournal.com]

ктулху съе мо окончани

[avva.livejournal.com]

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

[avva.livejournal.com]

Или просто они садятся на заранее оговоренные стулья и не могут это изменить. В общем, нет возможности тут передавать информацию.

[avva.livejournal.com]

Мне тут показали смайлик Ктулху:

{:€

[monomyth.livejournal.com]

хаха, надо будет запомнить :)

[monomyth.livejournal.com]

если кто–то из них скажет вслух: "пас", "красная", "синяя" – это тоже передача информации. Значит они ответы на бумажке пишут?

[french-man.livejournal.com]

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

[avva.livejournal.com]

Просто говорят одновременно по сигналу.

[monomyth.livejournal.com]

тогда о какой стратегии может идти речь? :)

[asherin.livejournal.com]

Возможность передавать информацию есть. Потому что от игроков требуют сказать нечто. Можно договориться о самых различных стратегиях. Можно называть цвет игрока справа или слева от себя, говорить "пас" если цвет шляп у двоих других игроков одинаковый. Иными словами, можно наложить требуемую информацию на "дозволенный" код. Вот если бы ответы других игроков были неизвестны... Но тогда и вовсе неинтересно будет.

[avva.livejournal.com]

заранее оговоренной :)

[ded-maxim.livejournal.com]

Разве это смайлик Ктулху? Вот я придумал (http://ded-maxim.livejournal.com/215866.html) смайлик Ктулху.

[damn-ekibastuz.livejournal.com]

100%

Допустим, что игроков зовут Вова, Леша и Петя.

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

Так вот, у Вовы есть выбор: (1) заговорить в течение двух секунд; или (2) промолчать.

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

Дальше предлагается следующий алгоритм (простой до исступления):


1.Если Вова видит две шляпы одного цвета, говорит "пас". Это сигнал Леше (он по стратегии всегда говорит вторым), что у него шляпа того же цвета, что у Пети. Леша назывет цвет петиной шляпы, Петя говорит "пас".

2. Если Вова увидел две разные шляпы, он молчит больше двух секунд. Тогда говорит Леша, называя цвет, противоположный петиному. Петя говорит "пас". (Он "пасует" всегда. Ему отведена роль пассивного, в хорошем смысле слова.)

[french-man.livejournal.com]

Нельзя сигналить. Нельзя ждать 2 секунды. Надо говорить одновременно.

[damn-ekibastuz.livejournal.com]

Ну, можно сократить срок до каких-то долей секунды. Если у них шумахерская реакция, это вполне возможно. Ответить одновременно все равно не выйдет. Кстати, Пете ждать сигналов не надо.

[french-man.livejournal.com]

А еще проще: петя чешет левое ухо, если на васе синяя шляпа, и правое, если красная. Ухо можно очень быстро почесать.

[siludin.livejournal.com]

Для трех человек ответ довольно очевиден, конечно, 75%.

Для большего количества людей - есть несколько способов подойти к решению этой задачи... Скажем, для 15 человек можно получить результат лучше 90%.

Ключевое слово - коды Хэмминга.

[damn-ekibastuz.livejournal.com]

Небольшая поправочка. Говоря о том что Леша говорит "вторым", я имел в виду, вхто он говорит после Вовы.
И не имеет значения, когда скажет свое слово Петя.

[rakshas.livejournal.com]

75.

Что больше нельзя — можно доказать наверно только перебором, хотя вариантов не так много, поэтому можно считать, что это и не перебор ;)

Я в уме перебрал вроде, но записывать неохота.

[monomyth.livejournal.com]

вот, я про это же и говорю. Иначе с таким же успехом можно поочерди их впускать комнату одевать шапку невидимку и спрашивать какого она цвета..

100%

[azzo27.livejournal.com]

Договоренность: Если А видит, что у С - красная, он говорит пас сразу, иначе ждет, пока В скажет пас; В - наоборот.
С ждет пасов А и В; Если первым пасует А, С говорит -красная...

[flaass.livejournal.com]

Когда-то я подробно писал про эту задачу, только там Белоснежка измывалась над семью гномами. Щас поищу...
Угу, вот оно:
http://community.livejournal.com/ru_math/28836.html
http://flaass.livejournal.com/15560.html
http://flaass.livejournal.com/15713.html
http://flaass.livejournal.com/16279.html