Введение: самое парадоксальное чудо теории вероятностей
В 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\,\%$ выживания.