задачка

[avva]

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

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

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

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

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

Comments

[justsoul.livejournal.com]

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

[avva.livejournal.com]

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

[monomyth.livejournal.com]

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

[monomyth.livejournal.com]

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

[french-man.livejournal.com]

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

[damn-ekibastuz.livejournal.com]

100%

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

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

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

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

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


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

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

[french-man.livejournal.com]

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

[siludin.livejournal.com]

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

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

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

[rakshas.livejournal.com]

75.

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

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

[(Anonymous)]

Сударь, а что именно Вы перебирали?
Возможные стратегии?
Их довольно много - даже для одного человека. А уж для группы из троих - перебор ого какой получается.

100%

[azzo27.livejournal.com]

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

Re: 100%

[bukin.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

[(Anonymous)]

В условии в том посте (комментарии не в счёт) нет упоминаний про то, что Белоснежка выбирает шапочки с помощью честной монетки. И вроде бы это предположение действительно не нужно, рандомизированная стратегия (with secretly shared random bits) выигрывает с той же вероятностью у сколь угодно злонамеренной Белоснежки.

[kvasha.livejournal.com]

Легко показать что 75%, есть визуализировать возможные варианты в виде вершин куба.
Каждый человек соответствует одному из измерений, каждая вершина -- одной из 8 комбинаций (ККК, ККС, КСК, etc), каждое ребро -- ответ человека при заданных координатах (наблюдаемых шляпах) других двух людей. Ответ может быть либо нейтральным (пас), либо стрелкой от одной вершины к другой (выбор одного из цветов) -- в случае выбора одна из вершин оказывается угаданной, а другая неугаданной.
Теперь задача переформулируется так: рисуя стрелки на ребрах куба, какое можеть быть максимальное колличество вершин на которые указана стрелка, от которых при этом не отходит других стрелок.
Очевидно, одна вершина может указать на три соседних, всего вершин 8, так что как минимум 2-мя вершинами нужно пожертвовать.

[azzo27.livejournal.com]

В этом варианте а)происчодит передача информации б)Одновременность - физическая (сколь угодно малый интервал времени между началом деклараций), а не математическая (точно 0).
Без передачи информации лучший результат = 50% , результат 75% невозможен.

[french-man.livejournal.com]

результат 75% невозможен

Ви таки уверены?

[mfi.livejournal.com]

Нет проблем сделать 75% - надо называть противоположный цвет если оба партнера одного цвета и пасовать в противном случае. Впрочем, выше уже написали. А вот улучшить результат трудно, ибо игра всего одна и индикатор лишь цвета двоих соседей. Проигрыш то у нас лишь когда все колпаки одинаковы - а как этот случай отличить от шести выигрышных ситуаций, когда кто то видит два одинаковых? Если бы можно сигнализировать местом или временем ответа - можно посмотреть. Или сделать игру многоразовой - тогда можно учитывать предидущие расклады.

[azzo27.livejournal.com]

Это неверно. Все три шляпы могут быть одного цвета.

[lavinya.livejournal.com]

А где обсуждение задачи про сто человек? И есть ли там решение?

[avva.livejournal.com]

Соответственно http://avva.livejournal.com/1743110.html и http://avva.livejournal.com/1743110.html?thread=41189382.

[yeziz.livejournal.com]

Задачка классическая, но в условии ошибка. "Разрешается договориться об общей стратегии" как раз и означает, что они могут поступать или говорить по очереди.
Более "чистый" вариант задачи: стоят колонной несколько человек, у каждого на голове шляпа, каждый видит все шляпы впередистоящих и не видит свою и позадистоящих, каждый называет цвет своей шляпы (по очереди, от хвоста колонны). Необходимо макисмизировать количество правильных ответов.

Не Волгу, а Жигули, не выиграл, а купил, не Рабинович...

[arish.livejournal.com]

Это хорошая задача, но другая:)

[mastyukov.livejournal.com]

Противоречивое условие ? //Если хотя бы один игрок правильно угадал цвет своей шляпы, и ни один из игроков не ошибся// = все угадали и никто не ошибся?

[dmpogo.livejournal.com]

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

[andreylv.livejournal.com]

надо же, буквально вчера разговаривали с приятелем о задаче "имена в коробках", и вспоминали эту, и вот на тебе.

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

[dmpogo.livejournal.com]

За счет того что неизвестно априори кто будет угадывать.

А почему 75% ?

[stogramovich.livejournal.com]

Как уже говорили:
если игрок видит одинаковые шапки - говорит противоположный цвет,
иначе пас.

То есть, если все шапки одного цвета - 100% проигрыш.
Если разного - 100% выигрыш.

Вероятность что все шапки будут одного цвета (1/2)^3 = 0.125
Вероятность выигрыша: 1 - 0.125 = 0.875

Или я что путаю?

Re: А почему 75% ?

[stogramovich.livejournal.com]

А дошло... Цветов-то два. (1/2)^3 * 2 = 0.25
1 - 0.25 = 0.75

[mgar.livejournal.com]

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

Это скорее напоминает задачи из серии Monty Hall...

Вот похожая. Вы едете в поезде, и с Вами в одном купе едет женщина. При знакомстве она говорит, что у неё двое детей. По ходу разговора выясняется, что один из них - мальчик. Какова вероятность, что второй - тоже мальчик?

[avva.livejournal.com]

Да, эту знаю :)

87.5%

[silver-fenix.livejournal.com]

В комнате я, Вова и Леша. Сначала отвечаю я, потом Вова, потом Леша.

1) Если хотя бы на одном из них красная шапка, то я говорю "Пас".

1а) Далее, если на Леше красная шапка, то Вова тоже говорит "пас". Леша произносит "красная" и оказывается прав.

2б) В противном случае он говорит "красная" и оказывается прав.

2) Если они оба в синих шапках, то я называю наугад любой цвет. Например, красный. Вероятность, что я не угадал - одна комбинация из всех 8 возможных - 12.5%. Поясню, в данном случае эта единственная комбинация: Вова-синий, Леша-синий, я-синий.

Re: 87.5%

[azot.livejournal.com]

Любые средства передачи информации между игроками запрещены.

"После того, как они увидели шляпы других игроков, по общему сигналу они все одновременно объявляют либо догадку насчет цвета своей шляпы - красный или синий - либо "пас".

[silver-fenix.livejournal.com]

Если в задаче не 3, а n участников, то при разработанной мной стратегии вероятность угадать равна:
(1 - 1/(2^n))*100% - т.е. у нас снова одна проигрышная комбинация из всех два-в-степени-n возможных.

87,5

[vaal12.livejournal.com]

Bous uge kto-to skazal, no esli vse nazovut 1 tsvet veroyatnost budet 87,5

[http://users.livejournal.com/_bigbrother_/]

Сначала нашёл стратегию:
видишь 2 шапки разного цвета - скажи "пас". Видишь 2 одноцветные - назови ДРУГОЙ цвет. Очевидно, что это даст 75%.
А потом я пытался понять, как вообще там возможно больше 50%.
Потому что исходы явно независимы. Независимо от того, что я вижу - вероятность красной шапки у меня самого, очевидно, 1/2. И синей тоже. И ничто из того, что я вижу, не поможет мне цвет моей шапки определить.

За счёт чего же достигается бОльшая вероятность победы?
За счёт сбора вместе неверных ответов. При проведении этой игры много раз количество правильных и неправильных ответов о цвете одной шляпы будет примерно одинаковым - но каждый верный будет в окружении двух пасов, а неверные будут встречаться тройками. Иными словами, верный ответ - победа, а ошибочный - только треть поражения.

Добиться отклонения вероятности правильного ответа о цвете шляпы от 1/2 нельзя - именно в силу того, что испытания независимы. Поэтому единственным способом сдвига вероятности победы является именно такое объединение неверных ответов в группы.

Допустим, перед нами есть последовательность игр, причём часть неверных ответов сгруппирована. Больше 3 неверных ответов в одну группу не объединить никак. Если мы сумеем добиться того, чтобы верные ответы при этом не группировались (каждый был снабжён двумя пасами), то получим вероятность победы 0,75 (в среднем у нас будет поровну верных и неверных ответов, при этом на 3 игры с одним верным ответом будет приходиться 1 игра с 3 неверными - мы их как раз так и сумели сгруппировать).
Вполне очевидно, что при группировке неверных ответов по 2 процент будет хуже. Тогда на 6 побед (по 1 верному ответу) будет приходиться 3 поражения (по 2 неверных ответа) - то есть вероятность победы будет составлять 2/3. Интересно было бы придумать стратегию, реализующую такой сценарий. Понятно, чего от неё нужно: в каждой конфигурации говорит либо один (и тогда он должен попадать), либо двое (и тогда оба должны промахиваться). Но, похоже, такая стратегия невозможна.

Итак, 75% - максимум. Удалось убедить?

[(Anonymous)]

три игрока ABC,A называет цвет шапки B, B называет цвет шапки C &
C называет цвет шапки A; так возможные варианты
000, 001, 010, 011, 100, 101, 110, 111
всегда есть вариант 100%

[(Anonymous)]

три игрока ABC,A называет цвет шапки B, B называет цвет шапки C &
C называет цвет шапки A; так возможные варианты
000, 001, 010, 011, 100, 101, 110, 111
всегда есть вариант 100%

[ryjaya-lisa.livejournal.com]

1/2?