Мудрецы и колпаки

[мат-ламер]

На интересную задачу натолкнулся в журнале "Квант". Привожу её с некоторыми сокращениями.

Однажды царь Шахрияр (Персия) решил проверить, так ли уж умны его придворные мудрецы. Он вызвал во дворец троих самых мудрых и объявил им условия завтрашнего испытания. Каждому мудрецу наденут колпак на голову белого или чёрного цвета (с равной вероятностью). Видя колпаки двоих других мудрецов, каждый мудрец записывает на бумаге цвет своего колпака (которого не видит). Если два или три мудреца отгадали цвет своего колпака, то мудрецов ждёт награда, иначе наказание. Мудрецы могут заранее договориться о своей тактике (но во время испытания обмен информацией запрещён). Как мудрецам следует договориться, чтобы максимизировать свои шансы?

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

[sergey zhukov]

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

Есть похожая задача, в которой какой-то обмен информацией происходит. Там действительно есть интересное решение. А тут, по моему, нет.

[мат-ламер]

sergey zhukov в сообщении #1635850 писал(а):

Если мудрецы не видят, что кто пишет

Да, не видят. И свой колпак не видят.

sergey zhukov в сообщении #1635850 писал(а):

С тем же успехом на них можно вовсе не смотреть и называть случайный результат.

Случайный ответ не даст преимущества в среднем.

[sergey zhukov]

мат-ламер
Разве это не задача типа "Три человека кидают каждый по монетке и угадывают каждый свой результат. Если два или три угадали - все выиграли. Как нужно действовать?" Что-то, честно говоря, не вижу разницы.

[eLectric]

Мудрецы не видят, что именно кто-то пишет. Но, зато, видят, что кто-то что-то пишет.

[ozheredov]

eLectric в сообщении #1635854 писал(а):

видят, что кто-то что-то пишет

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

[manul91]

sergey zhukov в сообщении #1635853 писал(а):

Разве это не задача типа "Три человека кидают каждый по монетке и угадывают каждый свой результат. Если два или три угадали - все выиграли. Как нужно действовать?" Что-то, честно говоря, не вижу разницы.

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

Очевидно если каждый равновероятно называет либо белое либо черное - вероятность чтобы два или три из них угадали равна 50% (вероятности чтобы из трех кинутых монеток, две или все три были орлами).
С другой стороны, при следующей стратегии - если видите одинаковый цвет колпаков у других двух мудрецов записываете для своего противоположный, если разного цвета - записываете равновероятно черный или белый. Легко подсчитать, что вероятность выигрыша будет $\frac{10}{16} = \frac{5}{8}$ что более 50%.
Из соображений симметрии вроде очевидно, что это и есть оптимальная стратегия (если не рассматривать всякого вида читерства с подсказками ввиде как держать ручки, кто расчесал бороду и пр.)

[ozheredov]

manul91 в сообщении #1635857 писал(а):

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

Я тоже интуитивно подумал о такой стратегии. Считать чё-т влом, ждём оценки ТС )

[EUgeneUS]

manul91 в сообщении #1635857 писал(а):

Легко подсчитать, что вероятность выигрыша будет $\frac{10}{16} = \frac{5}{8}$ что более 50%.

Посчитал, получилось ровно 50%.
1. Из восьми равновероятных случаев, есть четыре, когда шапки у других одинаковые. Два раза угадываю, два раза не угадываю.
2. Еще в четырех случаях шапки у других разные. Во всех из них угадываю с вероятноcтью $1/2$.
Итого $4/8=0.5$

[sergey zhukov]

manul91 в сообщении #1635857 писал(а):

кто расчесал бороду и пр.

Да это самый правильный вариант. Так эти мудрецы и должны были-бы действовать, если они действительно мудрецы.

[мат-ламер]

manul91 в сообщении #1635857 писал(а):

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

ozheredov в сообщении #1635859 писал(а):

Я тоже интуитивно подумал о такой стратегии.

Это мне тоже сразу пришло в голову.

manul91 в сообщении #1635857 писал(а):

Легко подсчитать, что вероятность выигрыша будет $\frac{10}{16} = \frac{5}{8}$ что более 50%.

У меня получился чуть меньший ответ. Пересчитаю ещё раз. Но в журнале приведено более интересное и эффективное решение. Даю подсказку.

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

во время испытания обмен информацией запрещён

Что да, то да. Другое дело, что какую-то дополнительную информацию мудрецы могут получить не жульничая.

[manul91]

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

[ozheredov]

EUgeneUS в сообщении #1635861 писал(а):

угадываю

Тут видимо фишка в том, что даже если априорные вероятности угадать по 0.5, но угадывания не независимы. Поэтому вероятность выбить 2 из 3 получается больше 0.5 (наверное).

[mihaild]

sergey zhukov, это стандартное неправильное в таких задачах рассуждение. Естественно что вероятность ошибки каждого будет $\frac{1}{2}$. Но наблюдения позволяют сделать эти ошибки не независимыми.
Из этого получается оценка, что нельзя гарантировать угадывание хотя бы двоих с вероятностью больше $\frac{3}{4}$: всего $8$ ситуаций, в них суммарно $24$ называния цвета, из них $12$ неправильных. Распихать $12$ неправильных называний по $7$ ситуациям когда угадывают хотя бы двое и одной оставшейся не получится.
Получить $\frac{3}{4}$ можно так: первый всегда говорит "белая", второй и третий, если видят, что у первого белая, делают чтобы угадал ровно один из них (второй называет то же что у третьего, третий противоположное тому, что у второго); если второй и третий видят, что у первого черная, то называют то, что видят у дргого.

manul91, у меня для Вашего варианта получается, что мы выигрываем с вероятностью $\frac{9}{16}$: нужно, чтобы не все цвета были одинаковы ($\frac{3}{4}$) и после этого хотя бы один из большинства угадал (еще $\frac{3}{4}$).

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

[manul91]

EUgeneUS в сообщении #1635861 писал(а):

Посчитал, получилось ровно 50%.
1. Из восьми равновероятных случаев, есть четыре, когда шапки у других одинаковые. Два раза угадываю, два раза не угадываю.
2. Еще в четырех случаях шапки у других разные. Во всех из них угадываю с вероятноcтью $1/2$.
Итого $4/8=0.5$

mihaild EUgeneUS Да, считая в уме я ошибся.
В двух (из восьми равновероятных случаев) по этой стратегии вероятность выживания ровно 0 (все три назовут ошибочный цвет).
Зато в остальных 6 случаев (где две из шляп одинакового цвета, третья противоположного):
- Тот кто видит одноцветные шляпы, точно угадает свой цвет.
- Чтобы при этом они не выжили, необходимо чтобы оба из двух других мудрецов ошиблись, вероятность этого $\frac{1}{4}$
- Значит, вероятность выживания (для каждого из тех 6-ти случаев) $\frac{3}{4}$.
Итоговая вероятность выживания $\frac{6}{8}\frac{3}{4}=\frac{3}{4}\frac{3}{4} = \frac{9}{16}$ что больше чем 50%.

-- 09.04.2024, 21:07 --

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

Но в журнале приведено более интересное и эффективное решение.

Это и если вероятность выше $\frac{9}{16}$ будет весьма удивительным (если без читерства)

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

Другое дело, что какую-то дополнительную информацию мудрецы могут получить не жульничая.

Что значит "могут получить"? Т.е. допускается что каждый из них может действовать не только основываясь на цветов колпаков других двух мудрецов, но основываясь и на что-то еще?