Просмотр кода страницы Задача о ста узниках и ста ящиках

{{не путать|Задача о ста узниках и лампочке|задачей о ста узниках и лампочке}}
[[Файл:100 prisoners problem qtl1.svg|мини|Каждый из ста узников должен найти свой номер в одном из ста ящиков, но может открыть только 50 ящиков.]]
'''Задача о ста узниках и ста ящиках''' — задача в [[Теория вероятностей|теории вероятностей]] и [[Комбинаторика|комбинаторике]]. Суть задачи заключается в том, что каждый из ста узников должен найти свой номер в одном из ста ящиков, чтобы все они выжили; если хотя бы один не справится, умрут все. Каждый узник может открыть только 50 ящиков и не может общаться с другими узниками, за исключением предварительного обсуждения стратегии.

На первый взгляд ситуация выглядит безнадёжной, но существует стратегия, которая даёт узникам шанс на выживание примерно в 30 %. Задача была предложена датским учёным в области информатики {{видимый якорь|Питер Мильтерсен|текст='''Питером Мильтерсеном'''}} в [[2003 год в науке|2003 году]].

== Условие ==
В литературе встречаются разные условия задачи. Ниже приведена версия Филиппа Флажоле и [[Седжвик, Роберт|Роберта Седжвика]]<ref name="flajolet">{{Citation|author=Philippe Flajolet, [[Седжвик, Роберт|Robert Sedgewick]]|title=Analytic Combinatorics|publisher=Cambridge University Press|year=2009|pages=124}}</ref>.

Начальник тюрьмы предлагает ста узникам, приговорённым к смертной казни, последний шанс. Узники пронумерованы от 1 до 100, а комната содержит шкаф со 100 ящиками. Начальник случайным образом помещает в каждый ящик по одному из номеров от 1 до 100, во все ящики — разные номера. Узники по очереди входят в комнату. Каждый узник может открыть и проверить 50 ящиков в любом порядке. После каждого узника ящики снова закрываются, а все номера остаются в ящиках. Если каждый из узников найдёт в одном из ящиков свой номер, то все узники будут помилованы; если хотя бы один узник не найдёт свой номер, все узники будут казнены. Прежде чем первый узник войдёт в комнату, узники могут обсудить стратегию, но не могут общаться после этого момента. Какова лучшая для узников стратегия?

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

Если узник выбирает 50 ящиков из 100 [[Случайность|случайным образом]], [[вероятность]] того, что он найдет свой номер, составляет 50 %. Вероятность того, что все узники, открывая случайные ящики, найдут свои номера, является произведением вероятностей успеха отдельных узников, то есть
: <math>\left(\frac{1}{2}\right)^{100}</math> ≈ {{Val|0.0000000000000000000000000000008}}
— исчезающе малое число. Ситуация кажется безнадёжной.

== Решение ==

=== Стратегия ===
Существует стратегия, которая обеспечивает вероятность более, чем в 30 %, что узники выживут. Ключ к успеху заключается в том, что узникам не нужно заранее решать, какие ящики открывать: каждый может использовать информацию, полученную из содержимого уже открытых им ящиков, чтобы решить, какой из них открыть следующим. Другое важное наблюдение заключается в том, что успешность одного узника не является [[Независимость (теория вероятностей)|независимой]] от успешности других, поскольку все они зависят от раскладки номеров по ящикам<ref name="curtin">{{citation|author=Eugene Curtin, Max Warshauer|title=The locker puzzle|journal=Mathematical Intelligencer|volume=28|year=2006|pages=28–31|doi=10.1007/BF02986999}}</ref>.

Для описания стратегии предположим, что не только узники, но и ящики пронумерованы от 1 до 100 — например, строка за строкой, начиная с верхнего левого ящика. Стратегия такова<ref name="stanley">{{Citation|author=Richard P. Stanley|title=Algebraic Combinatorics: Walks, Trees, Tableaux, and More|publisher=Springer|year=2013|pages=187–189}}</ref>:

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

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

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

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

: {| class="wikitable" style="text-align: center"
|-
! номера ящиков
|  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, и не найдет свой номер:
: {| class="wikitable" style="text-align: center"
|-
! номера ящиков
|  1 ||  2 ||  3 ||  4 ||  5 ||  6 ||  7 ||  8
|-
! номера узников
| 7 || 4 || 6 || 8 || 2 || 3 || 5 || 1
|}

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

: {| class="wikitable" style="text-align: center"
|-
! номера ящиков
|  1 ||  2 ||  3 ||  4 ||  5 ||  6 ||  7 ||  8
|-
! номера узников
| 3 || 1 || 7 || 5 || 8 || 6 || 4 || 2
|}

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

=== Объяснение через перестановки ===
{{multiple image|direction=horizontal|image1=Permutation cycles qtl1.svg|image2=Permutation cycles qtl2.svg|width=110|footer=Представление перестановок (1&nbsp;7&nbsp;5)(2&nbsp;4&nbsp;8)(3&nbsp;6) и (1&nbsp;3&nbsp;7&nbsp;4&nbsp;5&nbsp;8&nbsp;2)(6) как графа.}}

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

: <math>(1 ~ 7 ~ 5) (2 ~ 4 ~ 8) (3 ~ 6)</math>

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

: <math>(1 ~ 3 ~ 7 ~ 4 ~ 5 ~ 8 ~ 2) (6)</math>

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

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

=== Вероятность успеха ===
[[Файл:Permutation longest cycle length pmf qtl2.svg|мини|Распределение вероятностей длины самого длинного цикла случайной перестановки чисел от 1 до 100. При попадании в зелёную зону узники выживают, а красную — гибнут.]]

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

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

: <math>\binom{100}{l} \cdot (l-1)! \cdot (100-l)! = \frac{100!}{l}</math>.

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

: <math>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</math>,

где <math>H_n</math> — <math>n</math>-ое [[гармоническое число]]. Поэтому, используя стратегию следования по циклу, узники выживают примерно в 31 % случаев<ref name="stanley" />. Удивительно, но это больше, чем 25 % — вероятность успеха всего двух узников, выбирающих ящики случайно и независимо.

=== Асимптотика ===
[[Файл:Integral Test.svg|мини|Гармонические числа приблизительно определяются площадью под гиперболой и поэтому могут быть аппроксимированы [[Натуральный логарифм|натуральным логарифмом]].]]
Если вместо 100 узников рассмотреть <math>2n</math> узников, где <math>n</math> — произвольное натуральное число, вероятность выживания узников при использовании стратегии следования по циклу определяется как

: <math>1 - ( H_{2n} - H_n ) = 1 - (H_{2n} - \ln 2n) + (H_n - \ln n) - \ln 2</math>.

Пусть <math>\gamma</math> — [[постоянная Эйлера — Маскерони]]. Тогда при <math>n \to \infty</math> получаем

: <math>\lim_{n \to \infty} (H_n - \ln n) = \gamma</math>,

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

: <math>\lim_{n \to \infty} ( 1 - H_{2n} + H_n ) = 1 - \gamma + \gamma - \ln 2 = 1 - \ln 2 \approx 0.30685</math>.

Поскольку последовательность вероятностей [[Монотонная функция|монотонно уменьшается]], при использовании стратегии следования по циклу узники выживают более чем в 30 % случаев независимо от количества узников<ref name="stanley" />.

=== Оптимальность ===
В 2006 году Юджин Кертин и Макс Варшавер доказали оптимальность стратегии следования по циклу. Доказательство основано на эквивалентности с похожей задачей, в которой всем узникам разрешено присутствовать в комнате и наблюдать за открытием ящиков. Математически эта эквивалентность основана на {{iw|Лемма Фоаты о переходе|лемме Фоаты о переходе|en|Permutation#Foata's transition lemma}} — взаимно-однозначном соответствии между (каноническими) циклическими обозначениями и стандартной записью перестановки{{уточнить}}. В новой задаче вероятность выживания не зависит от выбранной стратегии и равна вероятности выживания в исходной задаче при использовании стратегии следования по циклу. Поскольку произвольная стратегия для исходной задачи также может быть применена к новой задаче, но она не может достичь более высокой вероятности выживания, стратегия следования по циклу должна быть оптимальной<ref name="curtin" />.

== История ==
Задача о 100 узниках и 100 ящиках была впервые рассмотрена в 2003 году датским ученым в области информатики Питером Мильтерсеном, который опубликовал её вместе с Анной Галь в отчёте о результатах 30-го международного коллоквиума по автоматам, языкам и программированию ({{iw|ICALP}}). В их версии игрок A (начальник тюрьмы) случайным образом раскрашивает полоски бумаги с именами игроков команды B (узников) в красный или синий цвет и помещает каждую полоску в отдельный ящик, при том что некоторые из ящиков могут быть пустыми. Чтобы команда B выиграла, каждый из её членов должен правильно назвать свой цвет после того, как он открыл половину ящиков<ref name="miltersen">{{Citation|author=Anna Gál, Peter Bro Miltersen|contribution=The cell probe complexity of succinct data structures|title=Proceedings 30th International Colloquium on Automata, Languages and Programming (ICALP)|year=2003|pages=332–344}}</ref>.

Первоначально Милтерсон предполагал, что вероятность выигрыша быстро стремится к нулю с увеличением количества игроков. Однако Свен Скайум, коллега Мильтерсена из [[Орхусский университет|Орхусского университета]], придумал стратегию следования по циклу для разновидности задачи, в которой нет пустых ящиков. В итоге в статье нахождение этой стратегии было оставлено как упражнение. Статья была удостоена{{уточнить}} награды за лучшую публикацию<ref name="curtin" />.

Весной 2004 года эта задача появилась в колонке головоломок от Джо Бюлера и [[Берлекэмп, Элвин|Элвина Берлекэмпа]] в ежеквартальном издании ''The Emissary'' {{iw|Научно-исследовательский институт математических наук (Беркли)|Научно-исследовательского института математических наук||Mathematical Sciences Research Institute}}<ref name="buhler">{{Citation|author=Joe Buhler, Elwyn Berlekamp|title=Puzzles Column|year=2004|pages=3}}</ref>. В последующие годы эта задача стала использоваться в математической литературе в различных формулировках — например, с карточками на столе<ref>{{Citation|author=Richard E. Blahut|title=Cryptography and Secure Communication|publisher=Cambridge University Press|year=2014|pages=29–30}}</ref> или кошельками в шкафчиках<ref name="curtin" />.

В форме задачи о 100 узниках и 100 ящиках она была поставлена в 2006 году Кристофом Пеппе в журнале ''Spektrum der Wissenschaft'' (немецкой версии ''[[Scientific American]]'')<ref name="pöppe">{{Citation|author=Christoph Pöppe|title=Mathematische Unterhaltungen: Freiheit für die Kombinatoriker|year=2006|pages=106–108}}</ref> и [[Уинклер, Питер Манн|Питером Уинклером]] в ''{{iw|College Mathematics Journal||en|The College Mathematics Journal}}''<ref name="winkler">{{Citation|author=Peter Winkler|title=Names in Boxes Puzzle|year=2006|pages=260,285,289}}</ref>. С небольшими изменениями этот вариант был использован в учебниках комбинаторики {{iw|Флажоле, Филипп|Филиппа Флажоле|en|Philippe Flajolet}} и [[Седжвик, Роберт|Роберта Седжвика]]<ref name="flajolet" />, а также {{iw|Стэнли, Ричард Питер|Ричардом Стэнли|en|Richard P. Stanley}}<ref name="stanley" />.

== См. также ==
* [[Задача трёх узников]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор={{iw|Флажоле, Филипп|Philippe Flajolet|en|Philippe Flajolet}}, [[Седжвик, Роберт|Robert Sedgewick]] |заглавие=Analytic Combinatorics |издательство=[[Cambridge University Press]] |год=2009 |isbn=978-0-521-89806-5 |место=Cambr. |язык=en |ссылка=https://ac.cs.princeton.edu/home/AC.pdf |страниц=824}}
* {{книга |автор={{iw|Стэнли, Ричард Питер|Richard P. Stanley|en|Richard P. Stanley}} |заглавие=Algebraic Combinatorics: Walks, Trees, Tableaux, and More |язык=en |издательство=[[Springer Science+Business Media|Springer]] |ссылка=https://books.google.ru/books?id=_Tc_AAAAQBAJ |год=2013 |страниц=223 |isbn=978-1-46146-998-8}}
* {{книга |автор=[[Уинклер, Питер Манн|Peter Winkler]] |заглавие=Mathematical Mind-Benders |издательство=[[Taylor & Francis]] |язык=en |ссылка=https://books.google.ru/books?id=phIlAQAAIAAJ |год=2007 |страниц=160 |isbn=978-1-56881-336-3}}

[[Категория:Перестановки]]
[[Категория:Вероятностные парадоксы]]
[[Категория:Математические головоломки и досуг]]