Математика спасения: как решить «невозможную» задачу о 100 заключенных 0:00
Эта классическая задача по теории вероятностей кажется контринтуитивной и даже невозможной на первый взгляд: 100 заключенных должны найти свои номера в 100 ящиках, чтобы получить свободу. В видео канала Veritasium ведущий разбирает, почему случайный выбор гарантирует почти неминуемую гибель, а специально разработанная математическая стратегия позволяет выжить с вероятностью более 30%.
Суть задачи и «ловушка» случайности 0:26
Условия эксперимента выглядят как сценарий жестокого психологического триллера. В запертой комнате находятся 100 пронумерованных ящиков, внутри каждого из которых лежит листок с номером от 1 до 100 в случайном порядке.
- Каждый из 100 заключенных заходит в комнату по очереди.
- У каждого есть право открыть только 50 ящиков.
- После поиска он обязан покинуть комнату, оставив всё как было, и не может общаться с другими.
- Если все 100 человек находят свой номер — все получают свободу. Если хоть один ошибается — всех казнят.
Если каждый заключенный выбирает ящики наугад, его индивидуальный шанс на успех составляет 50%. Вероятность того, что все 100 человек справятся одновременно, равна $0,5^{100}$. Это число настолько мало — примерно 0,00... (30 нулей) 8, — что шансы двух людей вытащить одну и ту же песчинку из всех пляжей Земли выше, чем шансы заключенных на спасение при такой стратегии.
«Петлевая» стратегия: магия математики 3:05
Компьютерный ученый Питер Милтерсон (Peter Miltersen), который популяризировал эту задачу, изначально не догадался до оптимального решения. Секрет заключается в использовании структуры перестановок и циклов.
Стратегия заключенных выглядит так:
- Заключенный заходит в комнату и первым делом открывает ящик с собственным номером.
- Если внутри лежит листок с его номером — он победил.
- Если нет — он берет число с найденного листка и идет к ящику с этим номером.
- Он повторяет этот процесс, пока не найдет свой номер или пока не исчерпает лимит в 50 попыток.
Почему это работает? 4:08
Весь набор ящиков и листков внутри математически представляет собой совокупность закрытых циклов. Когда заключенный начинает поиск с ящика со своим номером, он гарантированно попадает в цикл, содержащий его листок.
- Если длина цикла 50 или меньше — заключенный гарантированно найдет свой номер.
- Если длина цикла 51 или больше — заключенный не успеет найти свой номер за 50 шагов.
Успех всей группы зависит от того, содержит ли случайное распределение номеров хоть один цикл длиной более 50. Вероятность того, что в 100 ящиках не будет цикла длиннее 50, рассчитывается как $1$ минус сумма вероятностей появления циклов длиной от 51 до 100. Итоговая вероятность успеха составляет примерно 31,18% (часто округляется до 31%).
Масштабируемость и парадоксы 13:43
Один из самых удивительных фактов заключается в том, что вероятность выживания почти не падает с ростом числа заключенных. Для 1000 человек шанс на успех составляет около 30,74%, а для 1 миллиона — 30,68%.
При стремлении числа заключенных к бесконечности, вероятность успеха приближается к пределу, равному $1 - \ln(2)$, что составляет примерно 30,685%. Это означает, что даже если бы заключенных были миллиарды, они всё равно имели бы более чем 30%-ный шанс на спасение при использовании «петлевой» стратегии.
Нюансы контроля 12:26
- Симпатизирующий охранник: Если охранник может поменять местами содержимое двух ящиков, он может разбить один длинный цикл на два более коротких, гарантируя спасение всем.
- Злой охранник: Если охранник знает о стратегии и хочет помешать, он не может сделать ничего эффективного. Заключенные могут просто перенумеровать ящики (например, прибавив 5 к каждому), что эквивалентно новому случайному распределению, возвращая вероятность к тем же 31%.
