В задаче о 100 узниках и шкафчиках вероятность выживания группы при случайном поиске составляет (1/2)¹⁰⁰, что практически равно нулю. Однако использование стратегии «циклов» повышает шансы на успех всей группы до 31%. Суть метода в том, что каждый узник начинает поиск со шкафчика со своим номером и следует по указателям внутри (номеру на листке), пока не найдет свой билет. Если в случайной перестановке чисел нет циклов длиннее 50, группа выживает целиком.
Представьте себе мрачные подвалы старой крепости. Сто узников, обреченных на вечное заточение. Начальник тюрьмы, адепт странных игр, предлагает пари. В отдельной комнате стоят сто шкафчиков. Внутри каждого - номер одного из заключенных. Каждому разрешено войти и открыть ровно пятьдесят шкафчиков. Если каждый найдет листок со своим именем - все свободны. Если хотя бы один ошибется - кара настигнет всех.
Между собой общаться нельзя. Входить нужно по одному. Кажется, это приговор. Математика говорит: шанс каждого - ровно половина. А шанс того, что сто человек подряд выкинут «орла» - исчезающе мал. Степенно. Торжественно. Мрачно.
Остановитесь на полминуты. Не листайте. Неужели нет способа победить в этой игре? Или здесь зарыта логическая тропа, невидимая глазу?
Магия замкнутых циклов
Яков Перельман всегда учил: хаос - это просто порядок, который мы еще не поняли. Сто шкафчиков с номерами - это «перестановка». В любой перестановке чисел неизбежно возникают циклы.
Например: в шкафу №1 лежит номер 5, в шкафу №5 лежит номер 2, а в шкафу №2 - номер 1. Круг замкнулся. Длина этого цикла - 3.
Узник номер один входит в комнату и идет к шкафчику №1. Видит там «5». Идет к шкафу №5. Видит там «2». Идет к шкафу №2 - и находит свой номер! Он нашел себя за три шага.
Секрет стратегии в том, что если каждый будет следовать по номерам, «начертанным судьбой», то успех всей группы зависит лишь от одного: есть ли в этой расстановке цикл длиной более 50? Если самого длинного цикла нет, то каждый узник найдет свой листок. Вероятность этого события - поразительные 31%.
Почему это работает?
Честно говоря, это звучит как чудо. От почти нуля (случайный поиск) до тридцати одного процента! Математика циклов связывает судьбы узников воедино. Теперь они не сто одиноких игроков, а одна команда, зависящая от структуры перемешивания чисел.
В своё время Перельман писал, что цифра, добытая своим умом, врезается в память навсегда. Допущение здесь лишь одно: узники должны договориться о стратегии заранее. Один общий алгоритм против слепой удачи. Изящное решение, достойное аристократа мысли.
«А вы знали?»: Теория групп в быту
Эта задача - яркий пример теории групп, которая сегодня управляет криптографией и безопасностью Ваших банковских карт. Алгоритмы шифрования строятся на таких же перестановках и циклах, которые невозможно предсказать, не зная ключа. То, что век назад казалось «тюремной загадкой», сегодня охраняет Ваши секреты в цифровом пространстве.
Что далее
Мы столкнемся с врагом, которого невозможно победить логикой. Парадокс Лжеца. Предложение, которое взрывает мозг: «Я лгу». Если это правда - значит, он лжет. А если он лжет - значит, это неправда? Разберем ловушку древних греков.
Подпишись. Чтобы видеть невидимое. А Вы бы додумались искать по номерам или стали бы открывать шкафчики наугад? Напишите честно, рискнули бы Вы жизнью всей группы?
Читайте также:
Канал «А вы знали?» - задачи, фокусы и наука. Каждый день - повод удивиться.