Задача о 100 узниках и 100 ящиках

Существует стратегия, которая обеспечивает вероятность более, чем в 30 %, что узники выживут. Ключ к успеху заключается в том, что узникам не нужно заранее решать, какие ящики открывать: каждый может использовать информацию, полученную из содержимого уже открытых им ящиков, чтобы решить, какой из них открыть следующим. Другое важное наблюдение заключается в том, что успешность одного узника не является независимой от успешности других, поскольку все они зависят от раскладки номеров по ящикам[2].

Для описания стратегии предположим, что не только узники, но и ящики пронумерованы от 1 до 100 — например, строка за строкой, начиная с верхнего левого ящика. Стратегия такова[3]:

1. Каждый узник сначала открывает ящик со своим номером.
2. Если этот ящик содержит его номер, узник добился успеха.
3. В противном случае ящик содержит номер другого узника, и он открывает ящик с этим номером.
4. Узник повторяет шаги 2 и 3, пока не найдет свой номер или не откроет 50 ящиков.

Начиная перебор со своего собственного номера и идя по циклу, узник гарантирует, что находится в последовательности ящиков, заканчивающейся на его номер. Успешность его действий зависит только от того, будет ли эта последовательность длиннее 50 ящиков.

В модифицированном варианте задачи, где добавлен ещё один персонаж — адвокат, которому разрешено открыть все ящики и, при необходимости, поменять местами содержимое двух из них, выживание узников становится независимым от изначальной перестановки: для этого адвокат, обнаружив цикл длиннее 50 ящиков, разбивает его на два цикла длины не более 50.

Причина успешности этой стратегии может быть проиллюстрирована на следующем примере — в нём 8 узников и ящиков, каждый узник может открыть 4 ящика. Предположим, что начальник тюрьмы распределил номера узников по ящикам следующим образом:

номера ящиков	1	2	3	4	5	6	7	8
номера узников	7	4	6	8	1	3	5	2

Согласно приведённой выше стратегии, узники действуют следующим образом:

• Узник 1 сначала открывает ящик 1 и находит номер 7. Затем он открывает ящик 7 и находит номер 5. Затем он открывает ящик 5, где находит свой номер и тем самым добивается успеха.
• Узник 2 открывает по порядку ящики 2, 4 и 8. В последнем ящике он находит свой номер.
• Узник 3 открывает ящики 3 и 6; в последнем он находит свой номер.
• Узник 4 открывает ящики 4, 8 и 2, прежде чем находит свой номер. Обратите внимание, что это тот же цикл, с которым столкнулся узник 2, хотя ни один из этих узников не знает об этом.
• Узники с 5 по 8 также найдут свои номера похожим способом.

В данном примере все узники находят свои номера, однако это не всегда так. Например, если поменять содержимое ящиков 5 и 8, то узник 1 использует все свои попытки, открыв ящики 1, 7, 5 и 2, и не найдет свой номер:

номера ящиков	1	2	3	4	5	6	7	8
номера узников	7	4	6	8	2	3	5	1

А при следующей расстановке узник 1 откроет ящики 1, 3, 7 и 4 и также не добьётся успеха:

номера ящиков	1	2	3	4	5	6	7	8
номера узников	3	1	7	5	8	6	4	2

В действительности в этом примере все узники, кроме 6, не смогут найти ящик со своим номером.

Раскладку номеров узников по ящикам можно описать математически как перестановку чисел от 1 до 100. Такая перестановка представляет собой взаимно-однозначное отображение множества натуральных чисел от 1 до 100 на себя. Последовательность чисел, такая что первое переходит во второе, второе — в третьем, и так далее, а последнее — в первое, называется циклом перестановки. Каждая перестановка может быть разложена на непересекающиеся циклы, то есть циклы, которые не имеют общих элементов. Перестановка из первого примера выше может быть записана в циклической записи как

${\displaystyle (1~7~5)(2~4~8)(3~6)}$

и, таким образом, состоит из двух циклов длины 3 и одного цикла длины 2. Перестановка из второго примера — это, соответственно,

${\displaystyle (1~3~7~4~5~8~2)(6)}$

и состоит она из одного цикла длины 7 и одного цикла длины 1.

Циклическая запись не единственна, поскольку цикл длины ${\displaystyle l}$ может быть записан ${\displaystyle l}$ разными способами в зависимости от выбора первого числа. Открывая ящики по предложенной выше стратегии, каждый узник следует по циклу, который завершается его собственный номером. В случае восьми узников эта стратегия приводит к успеху тогда и только тогда, когда длина самого длинного цикла перестановки составляет не более 4. Если перестановка содержит цикл длиной 5 или более, все узники, чьи номера лежат в таком цикле, не достигают своего номера после четырех шагов.

Распределение вероятностей длины самого длинного цикла случайной перестановки чисел от 1 до 100. При попадании в зелёную зону узники выживают, а красную — гибнут.

В первоначальной задаче 100 узников добьются успеха, если самый длинный цикл перестановки имеет длину не более 50. Следовательно, вероятность их выживания равна вероятности того, что случайная перестановка чисел от 1 до 100 не содержит цикла длиной более 50. Эта вероятность определяется следующим образом.

Перестановка чисел от 1 до 100 может содержать не более одного цикла длины ${\displaystyle l>50}$. Существует ${\displaystyle {\tbinom {100}{l}}}$ способов выбора чисел для такого цикла, где скобки обозначают сочетания. Эти числа могут быть расположены по циклу ${\displaystyle (l-1)!}$ способами, так как из-за циклической симметрии есть ${\displaystyle l}$ способов записать один и тот же цикл длины ${\displaystyle l}$. Остальные числа можно расположить ${\displaystyle (100-l)!}$ способами. Итого, число перестановок чисел от 1 до 100 с циклом длины ${\displaystyle l>50}$ равно

${\displaystyle {\binom {100}{l}}\cdot (l-1)!\cdot (100-l)!={\frac {100!}{l}}}$.

Вероятность того, что (равномерно распределённая) случайная перестановка не содержит цикла длиной более 50, рассчитывается как

${\displaystyle 1-{\frac {1}{100!}}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)=1-\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)=1-(H_{100}-H_{50})\approx 0.31183}$,

где ${\displaystyle H_{n}}$ — ${\displaystyle n}$-ое гармоническое число. Поэтому, используя стратегию следования по циклу, узники выживают примерно в 31 % случаев[3]. Удивительно, но это больше, чем 25 % — вероятность успеха всего двух узников, выбирающих ящики случайно и независимо.

Гармонические числа приблизительно определяются площадью под гиперболой и поэтому могут быть аппроксимированы натуральным логарифмом.

Если вместо 100 узников рассмотреть ${\displaystyle 2n}$ узников, где ${\displaystyle n}$ — произвольное натуральное число, вероятность выживания узников при использовании стратегии следования по циклу определяется как

${\displaystyle 1-(H_{2n}-H_{n})=1-(H_{2n}-\ln 2n)+(H_{n}-\ln n)-\ln 2}$.

Пусть ${\displaystyle \gamma }$ — постоянная Эйлера — Маскерони. Тогда при ${\displaystyle n\to \infty }$ получаем

${\displaystyle \lim _{n\to \infty }(H_{n}-\ln n)=\gamma }$,

а потому вероятность выживания стремится к

${\displaystyle \lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\approx 0.30685}$.

Поскольку последовательность вероятностей монотонно уменьшается, при использовании стратегии следования по циклу узники выживают более чем в 30 % случаев независимо от количества узников[3].

В 2006 году Юджин Кертин и Макс Варшавер доказали оптимальность стратегии следования по циклу. Доказательство основано на эквивалентности с похожей задачей, в которой всем узникам разрешено присутствовать в комнате и наблюдать за открытием ящиков. Математически эта эквивалентность основана на лемме Фоаты о переходе — взаимно-однозначном соответствии между (каноническими) циклическими обозначениями и стандартной записью перестановки^{[уточнить]}. В новой задаче вероятность выживания не зависит от выбранной стратегии и равна вероятности выживания в исходной задаче при использовании стратегии следования по циклу. Поскольку произвольная стратегия для исходной задачи также может быть применена к новой задаче, но она не может достичь более высокой вероятности выживания, стратегия следования по циклу должна быть оптимальной[2].