Задача о цветных шапках

Valeus · Post by **Valeus** » 08 Dec 2001 07:24

Не старая задачка, но, вроде бы, достаточно популяризированная.

Есть команда из 3х игроков. Они зажмуриваются и каждому на головы одевают шапку. Красную или синюю. После этого, игроки открывают глаза и смотрят на своих товарищей по команде (и подмечают цвета их шапок). После етого они *одновременно* должны проголосовать за цвет своей собственной шапки: Красная, Синяя, или Пас. Команда выигрывает, если *хотя бы один* из игроков правильно назовет цвет своей шапки, в то время, как никто из остальных не ошибется. Т.е. если хотя бы один ошибется, или все скажут Пас, то игра проиграна.

Предлагается придумать наилучшую стратегию для команды. С какой вероятностью она приводит к победе?

Никакого communication между игроками во время игры не дозволено.

*****Можете ли предложит оптимальную стратегию для команды из N игроков?

-ЭР- · Post by **-ЭР-** » 08 Dec 2001 07:41

<blockquote>quote:<hr>Originally posted by Valeus:
Не старая задачка, но, вроде бы, достаточно популяризированная.
<hr></blockquote>

75% - для трех.

[ 07-12-2001: Message edited by: -ЭР- ]

listen_me_now · Post by **listen_me_now** » 10 Dec 2001 21:17

Открыв глаза , я увижу , что цвета шапок у моих товарищей либо одного цвета ,
либо нет . Вероятности равнозначны .
Но фактически вероятность того , что у всех могут оказаться шапки одного цвета,
равна 25% .
Если я вижу , что цвета одинаковы , мне нужно сказать , что у меня шапка другого
цвета . Как ни странно .
В противном случае вообще не имеет значения , что говорить .

Aleut · Post by **Aleut** » 12 Dec 2001 23:04

Не так все просто.
Например, можно договориться, что двое всегда пасуют, а третий отвечает, что хочет. Тогда вероятность выиграть - 50%.
Можно это дело отмоделировать на компе.

[ 12-12-2001: Message edited by: Aleut ]

-ЭР- · Post by **-ЭР-** » 13 Dec 2001 00:11

<blockquote>quote:<hr>Originally posted by Aleut:
Не так все просто.
Например, можно договориться, что двое всегда пасуют, а третий отвечает, что хочет. Тогда вероятность выиграть - 50%.
Можно это дело отмоделировать на компе.
<hr></blockquote>

Прошу прощения за повтор, но для трех можно вероятность выигрыша сделвть .75.

CTAC_P · Post by **CTAC_P** » 13 Dec 2001 01:36

<blockquote>quote:<hr>Originally posted by listen_me_now:
Открыв глаза , я увижу , что цвета шапок у моих товарищей либо одного цвета ,
либо нет . Вероятности равнозначны .
Но фактически вероятность того , что у всех могут оказаться шапки одного цвета,
равна 25% .
Если я вижу , что цвета одинаковы , мне нужно сказать , что у меня шапка другого
цвета . Как ни странно .
В противном случае вообще не имеет значения , что говорить .<hr></blockquote>
Как раз важно! Если шапки товарищей разные - надо говорить ПАС!

Aleut · Post by **Aleut** » 13 Dec 2001 03:17

Совершенно не важно, какие шапки на соседях.
Вероятность угадать свою - 0.5
Вероятность угадать 3 раза подряд - 0,125

Откуда Вы взяли 0.75?

-ЭР- · Post by **-ЭР-** » 13 Dec 2001 19:14

<blockquote>quote:<hr>Originally posted by Aleut:
Совершенно не важно, какие шапки на соседях.
Вероятность угадать свою - 0.5
Вероятность угадать 3 раза подряд - 0,125

Откуда Вы взяли 0.75?<hr></blockquote>

Чтобы не ломать кайф тем, кто еще думает, дам лишь намек. Прозрачный, и очень "програмистский":

000
001
010
011
100
101
110
111

CTAC_P · Post by **CTAC_P** » 13 Dec 2001 22:25

В общем, правильно будет так:
1-й игрок говорит ПАС если у 2-го или 3-го
шапка синяя. В противном случае (обе красные) сам называет синю.
2-й игрок говорит ПАС если у 3-го синяя, иначе сам называет синюю.
3-й игрок называет синюю всегда.
Т.о. проигрышная комбинация только когда у всех игроков шапки красные.

-ЭР- · Post by **-ЭР-** » 14 Dec 2001 00:43

У меня несколько другой ответ получается. Покомпактней что-ли. [img:746499018e]images/smiles/icon_smile.gif[/img:746499018e]

Drom · Post by **Drom** » 14 Dec 2001 02:34

<blockquote>quote:<hr>Originally posted by CTAC_P:
В общем, правильно будет так:
...
3-й игрок называет синюю всегда.
Т.о. проигрышная комбинация только когда у всех игроков шапки красные.<hr></blockquote>

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

CTAC_P · Post by **CTAC_P** » 14 Dec 2001 02:35

Прошу прощения, поторопился. Условие не прочитал [img:475f14a963]images/smiles/icon_biggrin.gif[/img:475f14a963]

[ 13-12-2001: Message edited by: CTAC_P ]

moleg · Post by **moleg** » 14 Dec 2001 03:23

<blockquote>quote:<hr>Originally posted by -ЭР-:


Чтобы не ломать кайф тем, кто еще думает, дам лишь намек. Прозрачный, и очень "програмистский":

000
001
010
011
100
101
110
111<hr></blockquote>

Внимательно смотрим на цифры и отвечаем: поскольку вариантов, когда две шапки одинакового цвета и одна другого, 6 из 8-ми, то разумно предположить следующую стратегию. Сидишь, смотришь на шапки. Если видишь две одинаковые, то говоришь, что на тебе шапка другого цвета (ошибаешься в 2/8=0.25). Если видишь две разные шапки - пасуешь.

Я правильно намек понял?

-ЭР- · Post by **-ЭР-** » 14 Dec 2001 03:46

<blockquote>quote:<hr>Originally posted by moleg:

Я правильно намек понял?<hr></blockquote>

Йес ит ыз! [img:7ac22a0ff6]images/smiles/icon_smile.gif[/img:7ac22a0ff6]

Aleut · Post by **Aleut** » 14 Dec 2001 23:15

Действительно 0,75
Интересно, что при такой стратегии вероятность выигрыша командой равна вероятности непротиворечивого ответа одного игрока. И что общий пас невозможен в принципе.

igrok · Post by **igrok** » 27 Dec 2001 04:59

Будет работать только в том случае, если распределение шапок от игре к игре равномерное. А если нет? В задаче ведь о том, какое распределение ничего не говорится.

Aspirant · Post by **Aspirant** » 27 Dec 2001 08:23

<blockquote>quote:<hr>Originally posted by igrok:
Будет работать только в том случае, если распределение шапок от игре к игре равномерное. А если нет? В задаче ведь о том, какое распределение ничего не говорится.<hr></blockquote>

Make this interesting. The hats come from a bag, which contains R red and B blue hats. R and B are not known. After each round the hats go back in the bag. How should they play?