Введение: самое парадоксальное чудо теории вероятностей
В 2003 году датский информатик Петер Бро Милтерсен сформулировал знаменитую задачу о 100 узниках:
- \(100\) приговоренных к смерти узников имеют номера от \(1\) до \(100\). В комнате стоят \(100\) закрытых коробок, внутри которых случайно разложены карточки с номерами от \(1\) до \(100\) (подстановка \(\sigma \in S_{100}\)).
- Правило: Каждый узник по очереди входит в комнату и может открыть не более \(50\) коробок, чтобы найти свой номер. После его выхода коробки закрываются, и любое общение после начала испытания исключено (но стратегию можно обсудить заранее).
- Условие спасения: Только если все \(100\) узников найдут свои номера, всех помилуют; если хотя бы один потерпит неудачу, казнят всех \(100\).
Если каждый открывает \(50\) случайных коробок (независимая стратегия), шанс одного равен \(1/2\), но вероятность общего спасения ничтожна:
\[\mathbb{P}(\text{все спасены})_{\text{незав.}} = \left(\frac{1}{2}\right)^{100} \approx 7{,}89 \times 10^{-31}\]Однако коллега Милтерсена Свен Скайум нашел стратегию следования по указателям (Pointer-Following Strategy), которая без передачи единого бита информации поднимает шанс общего спасения до \(31{,}18\,\%\)!
Глава 1: Следование по указателям и разложение на независимые циклы
Стратегия Скайума для узника с номером \(k \in \{1, \dots, 100\}\):
- Шаг 1: Сначала открыть коробку № \(k\).
- Шаг 2: Если внутри карточка \(x_1 = k\), успех; если \(x_1 \neq k\), следующей открыть коробку № \(x_1\).
- Шаг 3: Прочитать номер \(x_2\) и открыть коробку № \(x_2\), двигаясь по цепочке \(k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots\), пока не найдется \(k\) или не исчерпаются \(50\) попыток.
flowchart TD
Start["Узник k входит в комнату (макс. 50 попыток)"]
Step1["Шаг 1: Открыть коробку k, прочитать карточку x = σ(k)"]
Check{"Карточка x == k ?"}
Win["Свой номер k найден!"]
Limit{"Открыто коробок < 50 ?"}
Next["По указателю: Открыть коробку x (x ← σ(x))"]
Lose["Не найден за 50 шагов: Общая казнь"]
Start --> Step1 --> Check
Check -- "Да" --> Win
Check -- "Нет" --> Limit
Limit -- "Да" --> Next --> Check
Limit -- "Нет (длина цикла ℓ > 50)" --> Lose
Почему это работает? Соответствие коробка \(\mapsto\) карточка есть биекция \(\sigma\) в симметрической группе \(S_{2n}\) (\(2n=100\)). Любая конечная подстановка единственным образом раскладывается в произведение независимых (непересекающихся) циклов:
\[\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100\]Так как \(\sigma\) биективна, стартуя с коробки \(k\), узник движется по единственному замкнутому циклу, содержащему \(k\), и завершает обход на \(\sigma^{-1}(k)\) (коробке с карточкой \(k\)). Следовательно:
- Узник \(k\) успешен за \(\le 50\) шагов тогда и только тогда, когда длина его цикла \(\ell \le 50\).
- Все \(100\) узников выживают тогда и только тогда, когда подстановка \(\sigma \in S_{100}\) не содержит ни одного цикла длины \(\ell > 50\)!
Глава 2: Подсчет длинных циклов и гармонические числа (\(1 - \ln 2\))
Для \(2n\) узников (\(n = 50\)) подстановка \(\sigma \in S_{2n}\) может содержать не более одного цикла длины \(\ell > n\), так как два непересекающихся цикла длины \(> n\) требовали бы минимум \(2n+2 > 2n\) элементов. Значит, события \(E_\ell := \{\sigma \text{ содержит цикл длины } \ell\}\) при \(\ell = n+1, \dots, 2n\) попарно несовместны! Число подстановок в \(E_\ell\) равно:
- Выбор \(\ell\) элементов длинного цикла: \(\binom{2n}{\ell}\);
- Число ориентированных циклов на этих \(\ell\) элементах: \((\ell - 1)!\);
- Перестановки остальных \(2n - \ell\) элементов: \((2n - \ell)!\).
При перемножении факториалы сокращаются:
\[|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}\]Деление на \(|S_{2n}| = (2n)!\) дает \(\mathbb{P}(E_\ell) = \frac{1}{\ell}\). Через гармонические числа \(H_N = \sum_{k=1}^N \frac{1}{k}\) получаем точную вероятность выживания:
\[\boxed{P_{\text{success}}(2n) = 1 - \sum_{\ell = n+1}^{2n} \frac{1}{\ell} = 1 - \left(H_{2n} - H_n\right) \xrightarrow{n \to \infty} 1 - \int_1^2 \frac{dx}{x} = 1 - \ln 2 \approx 30{,}685\,\%}\]При \(2n = 100\) имеем \(P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31{,}1828\,\%}\)!
Глава 3: Связывание рисков (Coupling) без передачи информации
flowchart TD
Pool["Суммарный риск фиксирован: Ожидание неудач E[неудач] = 50"]
Indep["Независимая стратегия: Неудачи распылены почти по всем исходам"]
Cycle["Стратегия циклов: Судьбы связаны структурой циклов σ"]
ResI["Минимум 1 провал в 99,99...92 % исходов → Выживание ≈ 7,89×10⁻³¹"]
ResC["Провалы сжаты в 68,82 % исходов (ℓ>50) → В 31,18 % исходов выживают все 100!"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| Характеристика | 1. Независимая стратегия | 2. Стратегия циклов |
|---|---|---|
| Личный успех \(\mathbb{P}(A_k)\) | \(50{,}00\,\%\) | \(50{,}00\,\%\) (одинаково) |
| Ожидание успехов \(\mathbb{E}[X]\) | \(50\) узников | \(50\) узников (одинаково) |
| Корреляция | Нулевая (независимость) | Сильная положительная связь через \(\sigma\) |
| Выживание всех \(100\) | \((1/2)^{100} \approx 7{,}89 \times 10^{-31}\) | \(1 - (H_{100} - H_{50}) \approx 31{,}18\,\%\) |
| Предел при \(n \to \infty\) | \(0\) | \(1 - \ln 2 \approx 30{,}685\,\%\) |
- Связывание (Coupling): Поскольку 1 неудача и 51 неудача одинаково ведут к казни, стратегия циклов концентрирует все неудачи в \(68{,}82\,\%\) перестановок с длинным циклом (\(\ell > 50\)), очищая \(31{,}18\,\%\) пространства элементарных исходов от единой ошибки!
- Защита от коварного начальника тюрьмы: Тайно выбрав заранее случайную биекцию \(\tau \in S_{100}\), узники сопряжением \(\tau \sigma \tau^{-1}\) гарантируют те же \(31{,}18\,\%\) выживания.