Если никакой стратегии не выбирать, и каждый заключённый будет открывать 25 выбранных наугад ящиков, то у каждого заключённого будет 50% обнаружить своё имя. События независимые, значит вероятность, что все 50 заключённых обнаружат своё имя = (1/2)^50, величина пренебрежимо малая. И тем не менее, есть алгоритм, позволяющий поднять эту вероятность до 30%.
Очевидно, что с индивидуальной вероятностью 50% ничего поделать нельзя — ни у одного заключённого нет никакой информации, позволяющей ему улучшить этот результат. Зато можно поиграть с независимостью событий. Для того, чтобы заключённые чаще «выигрывали» (вытаскивали своё имя) вместе, нужно, чтобы они и «проигрывали» вместе как можно чаще.
Заменим для удобства имена порядковыми номерами. И коробки перенумеруем. Дадим каждому заключённому следующий алгоритм:
* Открой коробку со своим номером
* Если внутри лежит бумажка с твоим номером, можешь быть свободен, ты уже выиграл индивидуально
* Если внутри лежит бумажка с другим номером, открой коробку с этим номером и вернись на предыдущий этап
Очевидно, что если количество открываемых коробок неограниченно, то рано или поздно этот алгоритм приведёт к индивидуальному выигрышу — действительно, подписанные таким образом коробки явно образуют конечное число циклов конечного размера, и бумажка с номером X находится в одном цикле с коробкой номера X. Более того, она лежит в последней коробке этого цикла, если первой коробкой считать коробку номер X (чисто по построению — она замывает цикл).
То есть, если в нашем множестве из 50 коробок нет циклов длиннее 25 коробок, то все заключённые выиграют. А если такой цикл есть — то все заключённые, чьи номера находятся в этом цикле, проиграют.
Дальше немного нудный подсчёт, который показывает, что вероятность иметь цикл длиной более половины длины множества очень быстро стремится к 1 — ln(2) = 30,7%. Ещё чуть более нудное доказательство оптимальности этой стратегии.
Снова какая-то контринтуитивная фантастика!
У каждого вероятность выиграть осталась 50%, а вероятность выиграть всем вместе сгруппировалась и выросла до 30%.
