# Математика выживания: как «петлевая» стратегия спасает 100 заключенных

Источник: https://www.youtube.com/watch?v=iSNsgj1OCLA
Канал: Veritasium
Опубликовано: 30.06.2022

---

## Математика спасения: как решить «невозможную» задачу о 100 заключенных
[[JUMP:0:00]]

Эта классическая задача по теории вероятностей кажется контринтуитивной и даже невозможной на первый взгляд: 100 заключенных должны найти свои номера в 100 ящиках, чтобы получить свободу. В видео канала Veritasium ведущий разбирает, почему случайный выбор гарантирует почти неминуемую гибель, а специально разработанная математическая стратегия позволяет выжить с вероятностью более 30%.

### Суть задачи и «ловушка» случайности
[[JUMP:0:26]]

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

* Каждый из 100 заключенных заходит в комнату по очереди.
* У каждого есть право открыть только 50 ящиков.
* После поиска он обязан покинуть комнату, оставив всё как было, и не может общаться с другими.
* Если **все** 100 человек находят свой номер — все получают свободу. Если хоть один ошибается — всех казнят.

Если каждый заключенный выбирает ящики наугад, его индивидуальный шанс на успех составляет 50%. Вероятность того, что все 100 человек справятся одновременно, равна $0,5^{100}$. Это число настолько мало — примерно 0,00... (30 нулей) 8, — что шансы двух людей вытащить одну и ту же песчинку из всех пляжей Земли выше, чем шансы заключенных на спасение при такой стратегии.

### «Петлевая» стратегия: магия математики
[[JUMP:3:05]]

Компьютерный ученый Питер Милтерсон (Peter Miltersen), который популяризировал эту задачу, изначально не догадался до оптимального решения. Секрет заключается в использовании структуры перестановок и циклов.

Стратегия заключенных выглядит так:

1.  Заключенный заходит в комнату и первым делом открывает ящик с **собственным номером**.
2.  Если внутри лежит листок с его номером — он победил.
3.  Если нет — он берет число с найденного листка и идет к ящику с этим номером.
4.  Он повторяет этот процесс, пока не найдет свой номер или пока не исчерпает лимит в 50 попыток.



### Почему это работает?
[[JUMP:4:08]]

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

* Если длина цикла 50 или меньше — заключенный гарантированно найдет свой номер.
* Если длина цикла 51 или больше — заключенный не успеет найти свой номер за 50 шагов.

Успех всей группы зависит от того, содержит ли случайное распределение номеров хоть один цикл длиной более 50. Вероятность того, что в 100 ящиках не будет цикла длиннее 50, рассчитывается как $1$ минус сумма вероятностей появления циклов длиной от 51 до 100. Итоговая вероятность успеха составляет примерно **31,18%** (часто округляется до 31%).

### Масштабируемость и парадоксы
[[JUMP:13:43]]

Один из самых удивительных фактов заключается в том, что вероятность выживания почти не падает с ростом числа заключенных. Для 1000 человек шанс на успех составляет около 30,74%, а для 1 миллиона — 30,68%.

При стремлении числа заключенных к бесконечности, вероятность успеха приближается к пределу, равному $1 - \ln(2)$, что составляет примерно **30,685%**. Это означает, что даже если бы заключенных были миллиарды, они всё равно имели бы более чем 30%-ный шанс на спасение при использовании «петлевой» стратегии.

### Нюансы контроля
[[JUMP:12:26]]

* **Симпатизирующий охранник:** Если охранник может поменять местами содержимое двух ящиков, он может разбить один длинный цикл на два более коротких, гарантируя спасение всем.
* **Злой охранник:** Если охранник знает о стратегии и хочет помешать, он не может сделать ничего эффективного. Заключенные могут просто перенумеровать ящики (например, прибавив 5 к каждому), что эквивалентно новому случайному распределению, возвращая вероятность к тем же 31%.