Pour la science № 465 — парадокс заключённых

[green_fr]

Пускай у нас есть 50 заключённых (правдоподобность последующей ситуации позволяет думать, что названия парадоксам придумывают исключительно для того, чтобы подчеркнуть родство разных парадоксов между собой), перед ними ставят 50 ящиков с разложенными случайным образом их именами. Подпускают по одному, каждый заключённый может открыть 25 ящиков. Мы проверяем, есть ли среди открывшихся имён его имя. Затем ящики закрываются, мы подпускаем следующего заключённого и т.д. Естественно, заключённые не передают друг другу никакой информации, всё, что они могут сделать — это заранее договориться о какой-то стратегии. Ах да, цель игры — всех заключённых отпустят тогда и только тогда, если все заключённые обнаружат своё имя в тех ящиках, которые они открывали.

Если никакой стратегии не выбирать, и каждый заключённый будет открывать 25 выбранных наугад ящиков, то у каждого заключённого будет 50% обнаружить своё имя. События независимые, значит вероятность, что все 50 заключённых обнаружат своё имя = (1/2)^50, величина пренебрежимо малая. И тем не менее, есть алгоритм, позволяющий поднять эту вероятность до 30%.

Очевидно, что с индивидуальной вероятностью 50% ничего поделать нельзя — ни у одного заключённого нет никакой информации, позволяющей ему улучшить этот результат. Зато можно поиграть с независимостью событий. Для того, чтобы заключённые чаще «выигрывали» (вытаскивали своё имя) вместе, нужно, чтобы они и «проигрывали» вместе как можно чаще.

Заменим для удобства имена порядковыми номерами. И коробки перенумеруем. Дадим каждому заключённому следующий алгоритм:
* Открой коробку со своим номером
* Если внутри лежит бумажка с твоим номером, можешь быть свободен, ты уже выиграл индивидуально
* Если внутри лежит бумажка с другим номером, открой коробку с этим номером и вернись на предыдущий этап

Очевидно, что если количество открываемых коробок неограниченно, то рано или поздно этот алгоритм приведёт к индивидуальному выигрышу — действительно, подписанные таким образом коробки явно образуют конечное число циклов конечного размера, и бумажка с номером X находится в одном цикле с коробкой номера X. Более того, она лежит в последней коробке этого цикла, если первой коробкой считать коробку номер X (чисто по построению — она замывает цикл).

То есть, если в нашем множестве из 50 коробок нет циклов длиннее 25 коробок, то все заключённые выиграют. А если такой цикл есть — то все заключённые, чьи номера находятся в этом цикле, проиграют.

Дальше немного нудный подсчёт, который показывает, что вероятность иметь цикл длиной более половины длины множества очень быстро стремится к 1 — ln(2) = 30,7%. Ещё чуть более нудное доказательство оптимальности этой стратегии.

Снова какая-то контринтуитивная фантастика!
У каждого вероятность выиграть осталась 50%, а вероятность выиграть всем вместе сгруппировалась и выросла до 30%.

Comments

[sanzoku.livejournal.com]

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

[green-fr.livejournal.com]

Отличная рецензия на задачку! :-)))

[l-sylvanas.livejournal.com]

Однажды на лекции я слышала про очень интересную задачу: если у тебя в тюрьме есть банды, можно ли выводить людей на прогулку таким образом, чтобы члены одной банды никогда не встречались друг с другом? И там как-то доказывается, что вероятность просто "выше нуля". Увы, не помню вообще деталей, то есть сколько банд, сколько в них человек в каждой по отношению ко всему населению тюрьмы, вообще ничего не помню, кроме вот того, что в конце получается P > 0.

[green-fr.livejournal.com]

Удивительно, если бы получилось P < 0 ;-)

[l-sylvanas.livejournal.com]

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

[gianthare.livejournal.com]

А 50 имеет значение, или это просто n и n/2?

[green-fr.livejournal.com]

n и n/2. То есть при n -> infty выходит 1 - ln(2), а до того это просто оценка снизу.

[sanzoku.livejournal.com]

В действительности можно n и an, где a между 1/2 и 1. Ответ выходит тогда 1+ln(a). Если a<1/2 возникает возможность двух проигрышных циклов a<1/3 трех и т.д. и ответ естественно усложняется каждый раз. Я люблю задавать эту задачку про 80 коробок из 100, почему-то мне кажется, что такой вариант больше выносит мозг :)

[green-fr.livejournal.com]

Потому что коллективный ответ получается ещё ближе к индивидуальному? 77% vs 80%.

[sanzoku.livejournal.com]

Ага, именно

[green-fr.livejournal.com]

Ты, кстати, знаешь этого товарища (https://fr.wikipedia.org/wiki/Jean-Paul_Delahaye_(math%C3%A9maticien))? Это он рубрику в журнале ведёт, вполне достойный продолжатель Мартина Гарднера. И книжки тоже публикует - вполне научно-популярные, но читать всё равно интересно.

[sanzoku.livejournal.com]

Нет, никогда вроде не встречались. Все-таки слишком разные области.

[green-fr.livejournal.com]

Не, я не про личное знакомство, скорее - читал ли ты его книжки в свободное от работы время :-)

[sanzoku.livejournal.com]

Нет, не читал.