green_fr (green_fr) wrote,
green_fr
green_fr

Category:

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

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

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

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

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

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

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

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

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

  • Клаус Барби, Лионский палач

    Ехали мимо Лиона, у дороги стоит очередной туристический указатель: Les enfants d’Izieu. Нам это словосочетание ни о чём не говорило, полезли…

  • Подсчёт голосов на выборах

    Вчера у нас были выборы, сразу на уровне департамента и региона. Я сходил проголосовать (Анюта в Германии, доверенностью мы не занялись), на месте…

  • Pour la science №522

    Я наконец-то понял / смог представить себе проекцию 4-мерного куба (то, что получилось на  Большой арке Дефанс) и развёртку 4-мерного куба (то, что…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 14 comments

  • Клаус Барби, Лионский палач

    Ехали мимо Лиона, у дороги стоит очередной туристический указатель: Les enfants d’Izieu. Нам это словосочетание ни о чём не говорило, полезли…

  • Подсчёт голосов на выборах

    Вчера у нас были выборы, сразу на уровне департамента и региона. Я сходил проголосовать (Анюта в Германии, доверенностью мы не занялись), на месте…

  • Pour la science №522

    Я наконец-то понял / смог представить себе проекцию 4-мерного куба (то, что получилось на  Большой арке Дефанс) и развёртку 4-мерного куба (то, что…