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

  • La Vague и L'Odyssée des Gènes

    Практически одновременно купил два нон-фикшена. La Vague — книга французского эпидемиолога о первой волне ковида. Мы с Анютой — она тоже прочитала…

  • Разные книжки

    Был период, когда читать хотелось совсем какую-то ерунду, лишь бы попроще. Похоже, период прошёл, но за это время успел прочитать: «Nymphéas noirs»…

  • Weapons of Math Destruction

    Прочитал (спасибо wildest_honey!) книжку про риски применения математических алгоритмов в разных областях. Автор вводит вынесенный…

  • 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

  • La Vague и L'Odyssée des Gènes

    Практически одновременно купил два нон-фикшена. La Vague — книга французского эпидемиолога о первой волне ковида. Мы с Анютой — она тоже прочитала…

  • Разные книжки

    Был период, когда читать хотелось совсем какую-то ерунду, лишь бы попроще. Похоже, период прошёл, но за это время успел прочитать: «Nymphéas noirs»…

  • Weapons of Math Destruction

    Прочитал (спасибо wildest_honey!) книжку про риски применения математических алгоритмов в разных областях. Автор вводит вынесенный…