Команда знатоков в шляпах пытается угадать их цвет

[worm2]

Вычислительный эксперимент (если я не наврал при кодировании) показывает, что для $n=4$ и $n=5$ имеются стратегии, обеспечивающие одинаковую вероятность $11/16$. Правда, то, что я нашёл — несимметрично и некрасиво. И я рассматривал только одну стратегию на всех игроков.

[Shadow]

worm2, с увеличением $n$ вероятность должна увеличиватся. Если с 3-мя знатоками имеем вероятность $3/4>11/16$, то с 4-мя уменьшать ее не будем - Иван не играет и все. Он молчит, никто на него не смотрит - играют только трое. Его участие в игре должно увеличивать вероятность...думаю

[TOTAL]

Shadow в сообщении #709552 писал(а):

[b]Он молчит, никто на него не смотрит - играют только трое.

А вот здесь надо уточнить условие. Откуда я знаю, на кого не смотреть? Игроки отличаются по виду друг от друга? Например, игроки пронумерованы и каждый видит цвет каждого из номеров?

[worm2]

Shadow, Вы правы! Я рассматривал только одинаковые стратегии, т.е. у каждого был шанс рискнуть и сообщить цвет своей шляпы. Получается, одинаковая стратегия для всех неоптимальна.

TOTAL писал(а):

Например, игроки пронумерованы и каждый видит цвет каждого из номеров?

Я именно так понимаю условие. И что до игры можно собраться и наметить стратегию для каждого.

[мат-ламер]

TOTAL в сообщении #709574 писал(а):

вот здесь надо уточнить условие. Откуда я знаю, на кого не смотреть? Игроки отличаются по виду друг от друга? Например, игроки пронумерованы и каждый видит цвет каждого из номеров?

Конечно, всё как на настоящей игре типа "Что, где, когда". Игроки конкретны. Более того, они заранее могут договориться о тактике, которой будут придерживаться конкретные игроки. Допустим ($n=4$), один игрок (Вася) может по договорённости всегда пасовать. Остальные три могут на него не смотреть и использовать оптимальную тактику для трёх игроков. Таким образом, мы для $n=4$ получим вероятность выигрыша $3/4$. Это даже чуть лучше, чем стратегия worm2. Вот только будет ли это стратегия оптимальной, большой вопрос.

[Shadow]

TOTAL,я так поминаю что они заранее обдумывают стратегию (первый говорит, остальные молчат). Потому и вероятность $1/2$ сомнений не вызывала. (иначе при 2-х игроков ее не достичь). Но Вы правы, надо уточнить.

[TOTAL]

Допускается ли вообще не отвечать? (Не претендуя при этом на выигрыш, конечно.)

[мат-ламер]

TOTAL в сообщении #709648 писал(а):

Допускается ли вообще не отвечать? (Не претендуя при этом на выигрыш, конечно.)

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

[nikvic]

мат-ламер в сообщении #709640 писал(а):

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

Стал быть, стратегия каждому игроку приписывает функцию от видимого состояния остальных игроков, принимающую значения 0/ не скажу, 1/ белая, 2/ чёрная.
Уже для 4-х ооочень много стратегий

[lena7]

(Для одинаковой стратегии всех игроков)

1:      w       -> 1/2                                                                                                                       
2:      w b     -> 2/4                                                                                                                       
3:      w - b   -> 6/8                                                                                                                       
4:      w - b w         -> 11/16                                                                                                             
5:      b w - b w       -> 22/32                                                                                                             
6:      w b w - b w     -> 42/64                                                                                                             
7:      w - b w - b w   -> 85/128                                                                                                            
8:      w b w - b w - b         -> 170/256                                                                                                   
9:      w - b w - b w - b       -> 342/512                                                                                                   
10:     w - b w - b w - b w     -> 683/1024                                                                                                  
11:     b w - b w - b w - b w   -> 1366/2048                                                                                                 
12:     w b w - b w - b w - b w         -> 2730/4096                                                                                         
13:     w - b w - b w - b w - b w       -> 5461/8192                                                                                         
14:     w b w - b w - b w - b w - b     -> 10922/16384                                                                                       
15:     w - b w - b w - b w - b w - b   -> 21846/32768
...

Первый столбец -- число знатоков $n$. Во втором столбце стратегия: символ указывает, что должен ответить участник (w = белый, b = черный, - = ничего) в зависимости от числа $k$ белых шапок, которые он видит ($0\le k\le n$). Например, для $n=4$: если видим все чёрные или все белые, то отвечаем "белый"; если видим одну белую, воздерживаемся от ответа; если видим две белых, отвечаем "черный". Третий столбец -- шансы выиграть. Программа.

Числители образуют A083322, а вся дробь с ростом $n$, кажется, стремится к $2/3$.

[TOTAL]

Пусть лучшая стратегия для $n$ человек дает выигрыш с вероятностью $P_n.$
Для $n+1$ человек можно выиграть с вероятностью $P_{n+1}=(P_n + 1)/2.$ Для этого первые $n$ игроков применяют стратегию для $n,$ если у последнего $0$ на голове, и пасуют, если у последнего $1$ на голове. Первый пасует, если видит, что у первых $n$ выигрышный расклад, и называет $1,$ если видит, что у них проигрышный расклад.

Фигню написал.

[sup]

К слову. До сих пор рассматривались только чистые стратегии. А как насчет смешанных? Можно ли утверждать/показать, что среди оптимальных стратегий обязательно найдется чистая (если их несколько)?
Для "небольших" n можно зарядить задачу линейного программирования и таки точно найти вероятности. Может там будет какая-нибудь "простая" закономерность.

[Shadow]

Я все больше убеждаюсь, что 3/4 невезможно улучшить. Для стратегий с рекурсией, по моему, даже можно строго доказать.

[worm2]

sup писал(а):

А как насчет смешанных?

Я искал смешанные стратегии для $n=3,4$.
0.75 побить не удалось

P.S. Целевая функция нелинейная (многочлен степени $n$).

[sup]

(Оффтоп)

worm2 в сообщении #709921 писал(а):

P.S. Целевая функция нелинейная (многочлен степени $n$).

Да уж, насчет линейного программирования это я знатно отметился