Сто человек, приговорённых к неминуемой гибели, получают единственный шанс на спасение. В изощрённой математической задаче, которая стала испытанием для самых острых умов.
Эта задача — «100 узников и 100 ящиков» — это захватывающая история о коллективном разуме, парадоксах вероятности и озарении.
Приговор без надежды? Классическая ловушка вероятности
Итак, вот наши сто узников. Перед ними – сто закрытых ящиков, пронумерованных от 1 до 100.
В каждом ящике лежит один жетон с уникальным числом – от 1 до 100, причём эти числа распределены совершенно случайно.
Главное правило: каждый узник знает свой номер.
Условия:
- Каждый узник заходит в комнату по очереди.
- Он может открыть не более 50 ящиков.
- Он должен найти жетон со своим собственным номером.
- После того, как узник покидает комнату, все ящики возвращаются в исходное состояние (закрываются, содержимое не меняется).
- Самое важное: Узники не могут общаться между собой ни до, ни во время, ни после своей попытки. Единственное, о чём они могут договориться, – это общая стратегия до того, как первый из них войдёт в комнату.
- Исход: Все 100 узников выживают, только если каждый из них найдёт свой номер. Если хотя бы один ошибётся, все погибают.
На первый взгляд, ситуация кажется абсолютно безвыходной. Если каждый узник будет выбирать ящики случайным образом, его шансы найти свой номер составляют 50 из 100, то есть 1/2.
«Отлично, – подумаете вы, – каждый второй найдёт!» Но дьявол кроется в деталях: выжить должны все.
Вероятность того, что 100 человек подряд сделают это наугад, равна (1/2)^100. Это число настолько мало, что практически равно нулю. Если записать его, получится 0,0000000000000000000000000000008.
Гениальная идея: что, если система подсказывает сама себе?
Ключ к решению лежит в том единственном, что узники могут сделать: договориться о стратегии заранее. Без возможности передавать информацию во время испытания, их стратегия должна быть универсальной и работать для каждого, независимо от того, какие числа им выпадут.
Обычный подход не работает, потому что каждый узник начинает "с чистого листа".
Представьте, что числа в ящиках – это не просто случайные метки, а своего рода "указатели", которые могут направлять нас по лабиринту. Это и есть та самая «Эврика!» идея, которая выводит нас из тупика.
Открываем ящики по-новому: алгоритм, меняющий игру
Спасительная стратегия, о которой договариваются узники:
- Начало пути: каждый узник, скажем, Узник №X, начинает с того, что открывает ящик, соответствующий его собственному номеру. То есть Узник №1 открывает Ящик №1, Узник №42 – Ящик №42 и так далее.
- Следующий шаг: если внутри Ящика №X находится жетон с числом X (номер узника), то Узник №X находит свой номер, и его миссия успешно завершена. Он покидает комнату.
Если же внутри Ящика №X находится жетон с числом Y (где Y ≠ X), то Узник №X не закрывает этот ящик и не выбирает следующий случайный. Вместо этого, он использует число Y как указатель: он открывает Ящик №Y. - Продолжение цепочки: Узник №X повторяет этот процесс: если в Ящике №Y он снова находит не свой номер, а число Z, он открывает Ящик №Z. Он продолжает следовать этой "цепочке" до тех пор, пока не найдёт свой собственный номер или не исчерпает свои 50 попыток.
Давайте рассмотрим пример. Допустим, Узник №15 входит в комнату.
- Он открывает Ящик №15. Допустим, внутри жетон с числом 73.
- Теперь он открывает Ящик №73. Допустим, там число 5.
- Теперь он открывает Ящик №5. И вот чудо – там жетон с числом 15!
- Узник №15 успешно находит свой номер, использовав всего 3 попытки.
Что, если бы он не нашёл свой номер после 50 попыток? Тогда, увы, все узники были бы обречены. Но эта стратегия радикально меняет шансы!
Магия перестановок и циклов: почему это работает?
В чём гениальность этого подхода? Она кроется в математике перестановок. Распределение 100 чисел по 100 ящикам – это, по сути, одна из возможных перестановок чисел от 1 до 100. Любая такая перестановка может быть разложена на так называемые "циклы".
Представим наши ящики и числа в них как связи: Ящик i содержит число j. Это можно изобразить как стрелку i -> j.
Например:
Ящик 1 содержит 7
Ящик 7 содержит 3
Ящик 3 содержит 1
Это цикл: 1 -> 7 -> 3 -> 1.
Если Узник №1 начинает с Ящика №1, он попадёт в Ящик №7, затем в Ящик №3, а затем обратно в Ящик №1. Он найдёт свой номер! Если Узник №7 начнёт с Ящика №7, он попадёт в Ящик №3, потом в Ящик №1, потом в Ящик №7. Тоже найдёт!
Ключевой момент: Если узник начинает с ящика, соответствующего его номеру, он неизбежно будет двигаться по одному из таких циклов, пока не вернётся к своему начальному номеру. Он найдёт свой номер, если длина этого цикла не превышает 50 попыток.
Вот где кроется спасение: Если все циклы, которые образуются в распределении чисел, имеют длину 50 или меньше, то каждый узник найдёт свой номер! Почему? Потому что каждый узник принадлежит только к одному циклу. Если длина этого цикла <= 50, он найдёт свой номер в рамках 50 попыток.
Единственный случай, когда эта стратегия не сработает – это если в распределении чисел в ящиках есть хотя бы один цикл, длина которого больше 50.
Если существует цикл длиной 51, то любой узник, чей номер является частью этого цикла, не сможет найти свой номер за 50 попыток. Он просто не успеет пройти весь цикл до своего жетона.
Шанс на спасение: от нуля до 30%
Мы начали с почти нулевых шансов, помните? А теперь, благодаря этой стратегии, мы можем рассчитать вероятность успеха.
Какова вероятность того, что в случайной перестановке 100 элементов не будет ни одного цикла длиной более 50?
Математика показывает, что эта вероятность довольно высока! Она равна:
1 - (1/51 + 1/52 + ... + 1/100) ≈ 1 - ln(100/50) = 1 - ln(2).
Значение натурального логарифма ln(2) ≈ 0.693.
Таким образом, вероятность успеха составляет примерно 1 - 0.693 = 0.307, или около 30.7%.
Заключение: Вдохновение в каждом цикле
Задача о 100 узниках и 100 ящиках – это не просто головоломка. Это метафора нашей жизни. Как часто мы сталкиваемся с проблемами, которые кажутся неразрешимыми?
Какие циклы вы замечаете в своих задачах? Готовы ли вы найти свой путь, следуя указателям, чтобы их обнаружить?
Поделитесь своими мыслями в комментариях!