Математическая задача о 100 коробках и спасении заключенных

Предлагаю читателям «Хабрахабра» перевод публикации «100 Prisoners Escape Puzzle», которую я нашел на сайте компании DataGenetics. Все ошибки по данной статье присылайте, пожалуйста, в личные сообщения.

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



Задача


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



Соревнование начинается, тюремщик отводит каждого заключенного по одному в комнату с коробками и говорит заключенным, что они должны найти коробку, в которой будет находиться табличка с номером заключенного. Заключенные пытаются найти табличку со своим номером, открывая коробки. Каждому разрешается открыть до 50-ти коробок; если каждый из заключенных найдет свой номер, то заключенных отпустят, если хотя бы один из них не найдет свой номер за 50 попыток, то все заключенные умрут.



Для того, чтобы заключенные были освобождены, ВСЕ заключенные должны пройти испытание успешно.

Так какой же шанс, что заключенных помилуют?

  • После открытия коробки заключенным и проверки им таблички она помещается обратно в коробку и крышка снова закрывается;
  • Местами таблички менять нельзя;
  • Заключенные не могут оставлять друг другу подсказки или как-то взаимодействовать друг с другом после начала испытания;
  • Заключенным разрешается обсудить стратегию до начала испытания.


Какая же оптимальная стратегия для заключенных?

Дополнительный вопрос:
Если товарищ заключенных (не участник испытания) будет иметь возможность проникнуть в секретную комнату до начала испытания, изучить все таблички во всех коробках и (по желанию, но не обязательно) поменять местами две таблички из двух коробок (при этом у товарища не будет возможности как-то сообщить заключенным о результате своих действий), то какую стратегию он должен предпринять, чтобы увеличить шансы заключенных на спасение?


Решение маловероятно?


С первого взгляда эта задача кажется почти безнадежной. Кажется, что шанс на нахождение каждым из заключенных своей таблички микроскопически мал. К тому же, заключенные не могут обмениваться информацией между собой в процессе испытания.

Шансы одного заключенного — 50:50. Всего 100 коробок и он может открыть до 50-ти коробок в поисках своей таблички. Если он будет открывать коробки наугад и откроет половину всех коробок, то найдет свою табличку в открытой половине коробок, или его табличка останется в закрытых 50-ти коробках. Его шансы на успех — ½.



Возьмем двух заключенных. Если оба выбирают коробки наугад, для каждого из них шансы будут ½, а для двоих ½x½=¼.
(для двух заключенных успех будет в одном случае из четырех).



Для трех заключенных шансы будут ½ × ½ × ½ = ⅛.



Для 100 заключенных, шансы следующие: ½ × ½ × … ½ × ½ (перемножение 100 раз).



Это равняется
Pr ≈ 0.0000000000000000000000000000008


То есть это очень маленький шанс. При таком раскладе, скорее всего, все заключенные будут мертвы.

Рекомендуется поразмыслить, прежде чем читать решение дальше.

Невероятный ответ


Если каждый заключенный будет открывать ящики наугад, то вряд ли они пройдут испытание. Существует стратегия, при которой заключенные могут рассчитывать на успех более чем в 30% случаев. Это потрясающе невероятный результат (если вы не слышали про эту математическую задачу ранее).

Больше чем 30% для всех 100 заключенных! Да это даже больше, чем шансы для двоих заключенных, при условии, что те будут открывать ящики наугад. Но как это возможно?

Понятно, что по одному у каждого заключенного шансы не могут быть выше 50% (ведь нет способа для общения между заключенными). Но не стоит забывать, что информация хранится в расположении табличек внутри коробок. Никто не перемешивает таблички между посещениями комнаты отдельными заключенными, так что мы можем использовать эту информацию.

Решение


Для начала расскажу решение, затем разъясню, почему оно работает.

Стратегия крайне легкая. Первый из заключенных открывает коробку с тем номером, который написан на его одежде. Например, заключенный номер 78 открывает коробку с номером 78. Если он находит свой номер на табличке внутри коробки, то это здорово! Если нет, то он смотрит номер на табличке в «своей» коробке и затем открывает следующую коробку с этим номером. Открыв вторую коробку, он смотрит номер таблички внутри этой коробки и открывает третью коробку с этим номером. Далее просто переносим эту стратегию на оставшиеся ящики. Для наглядности смотрим картинку:



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

Красота этой математической задачки — не только знать результат, но и понять, почему эта стратегия работает.


Так почему же стратегия работает?


В каждой коробке по одной табличке — и эта табличка уникальна. Это означает, что табличка находится в коробке с тем же номером, или она указывает на другую коробку. Так как все таблички уникальны, то для каждой коробки есть только одна табличка, указывающая на нее (и всего один путь, как добраться до этой коробки).



Если поразмыслить над этим, то коробки образуют замкнутую круглую цепочку. Одна коробка может быть частью только одной цепочки, так как внутри коробки только один указатель на следующую и, соответственно, в предыдущей коробке только один указатель на данную коробку (программисты могут увидеть аналогию со связанными списками).

Если коробка не указывает на саму себя (номер коробки равен номеру таблички в ней), то она будет в цепочке. Некоторые цепочки могут состоять из двух коробок, некоторые длиннее.



Так как все заключенные начинают с коробки с тем же номером, что и на их одежде, они, по определению, попадают на цепочку, которая содержит их табличку (есть всего одна табличка, которая указывает на эту коробку).

Исследуя коробки по этой цепочке по кругу, они гарантированно в конечном итоге найдут свою табличку.

Единственный вопрос остается в том, найдут ли они свою табличку за 50 ходов.



Длина цепочек


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

Если максимальная длина самой длинной цепочки меньше, чем 50 коробок, тогда все заключенные пройдут испытание!


Задумайтесь об этом на секунду. Выходит, что может быть только одна цепочка, которая длиннее 50-ти коробок при любом раскладе табличек (у нас всего 100 коробок, так что если одна цепочка длиннее 50-ти, то остальные будут короче, чем 50 в итоге).



Шансы на расклад с длинной цепочкой


После того, как вы убедили себя, что для достижения успеха максимальная длина цепи должна быть меньше или равна 50, и может быть только одна длинная цепочка в любом наборе, мы можем вычислить вероятность успеха прохождения испытания:



Еще немного математики


Итак, что нам нужно, чтобы выяснить вероятность существования длинной цепочки?

Для цепочки с длиной l, вероятность того, что коробки будут вне этой цепочки равна:



В этой коллекции чисел существует (l-1)! способов расположить таблички.

Оставшиеся таблички могут быть расположены (100-l)! способами (не забываем, что длина цепочки не превосходит 50).

Учитывая это, число перестановок, которые содержат цепочку точной длины l: (>50)



Выходит, есть 100(!) способов раскладок табличек, так что вероятность существования цепочки длиной l равно 1/l. Кстати, этот результат не зависит от количества коробок.

Как мы уже знаем, может быть только один вариант, при котором существует цепочка длиной > 50, так что вероятность успеха рассчитывается по данной формуле:



Результат


31.18% — вероятность того, что размер самой длинной цепочки будет меньше 50 и каждый из заключенных сможет найти свою табличку, учитывая предел в 50 попыток.

Вероятность того, что все заключенные найдут свои таблички и пройдут испытание 31.18%


Ниже приведен график, показывающий вероятности (по оси ординат) для всех цепей длины l (на оси абсцисс). Красный цвет означает все «неудачи» (данная кривая здесь — это просто график 1/l). Зеленый цвет означает «успех» (расчет немного сложнее для этой части графика, так как существует несколько способов для определения максимальной длины <50). Общая вероятность складывается из зеленых столбцов в 31.18% шанс на спасение.



Гармоническое число (эта часть статьи для гиков)


В математике n-м гармоническим числом называется сумма обратных величин первых n последовательных чисел натурального ряда.



Мы можем рассчитать вероятность побега из тюрьмы, складывая соответствующие гармонические числа.

Посчитаем предел, если вместо 100а коробок мы имеем произвольное большое количество коробок (давайте считать, что у нас есть 2n коробок в итоге).



Постоянная Эйлера—Маскерони — константа, определяемая как предел разности между частичной суммой гармонического ряда и натуральным логарифмом числа.

Так как число заключенных увеличивается, то при условии, если надсмотрщик разрешает заключенным открывать половину всех коробок, то шанс на спасение стремится к числу 30.685%


(Если вы приняли решение, при котором заключенные случайно угадывают коробки, то с увеличением количества заключенных вероятность спасения стремится к нулю!)

Дополнительный вопрос


Кто-нибудь еще помнит про дополнительный вопрос? Что может сделать наш полезный товарищ, чтобы увеличить шансы на выживание?

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

В результате этой стратегии не будет длинных цепочек и все заключенные гарантированно найдут свою табличку и спасение. Так что, поменяв местами две таблички, мы сводим вероятность спасения к 100%!
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 55
  • +22
    Можно ли доказать, что не существует лучшей стратегии?
    • 0
      Эта задача в несколько другом виде уже публиковалась на Хабре в сентябре 2014 «Две красивые задачи по алгоритмам», там было обсуждение алгоритма, правда строгого доказательства вроде не было.
      • +3
        Да, стратегия в пределе оптимальна, но результат не столь тривиален, как сама стратегия. Доказательство можно найти в Eugene Curtin and Max Warshauer, The locker puzzle, The Mathematical Intelligencer, 28.1.
      • +6
        Данная стратегия как нибудь используется в каких-либо алгоритмах? Базах данных?
        • –2
          Я не согласен с вот этой частью:
          Если цепочка длиннее, чем 50 коробок, заключенные, имеющие номера из этих цепочек провалят испытание — и все заключенные будут мертвы.


          Вполне может быть такое, что цепочка длиннее 50 коробок, но заключенный начинает не с её конца, а с какого-то положения Х, от которого до его номера может быть менее 50 коробок. Т.е. у «красных» столбиков справа на вашем графике на самом деле должна быть некоторая зелёная часть и некоторая красная.
          • +10
            Заключённый всегда начинает с конца, иначе как он попадёт на нужную цепочку?
            • –3
              Но ведь это начала цепочки только с точки наблюдателя-заключенного, когда как его номер может быть далеко не первым в цепочке.
              • +11
                Определение цепочки и способ выбора первого элемента говорит, что в цепочке с количеством узлов L заключенный найдет свой номер точно на попытке номер L.
              • +9
                Да, я уже даже успел тест написать пока это понял :)
                Даёт 31.1759% на миллионе экспериментов.
                • 0
                  Ваш пример с «тёмным» помощником: gist.github.com/h4tr3d/d79e2e7def7a907f473f

                  Забавно, что если исправить только одну длинную цепочку, то вероятность повышается до 33%
                  • 0
                    Стало интересно, та же история на Python:
                    Функционально: gist
                    Объектно: gist
                    Может дальше ещё на каких языках предложат?
                • +1
                  ВСЕ заключенные должны пройти испытание успешно
                  • 0
                    madskillz
                    image


                    Но как заметили ниже, заключенный начинает же с конца по логике вещей.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +3
                        Там же написно что вы начинаете с коробки, соответствующей вашему номеру. То есть вы придете к коробке со своим номером в последнюю очередь перед замыканием цепочки. Поэтому и шанса спастись также не будет
                      • 0
                        При правильном нахождении своего номера — коробка убирается или остается?
                        • +3
                          После открытия коробки заключенным и проверки им таблички она помещается обратно в коробку и крышка снова закрывается
                          • 0
                            В абсолютных величинах это ничего бы не изменило, т.к. первый заключенный имел бы шансы 31.18% и никак больше. Т.е. наименьший шанс успеха среди отдельно взятого заключенного определяет шанс успеха для всех. + это могло бы разрушить цепочку, что только снижает шансы на успех в перспективе, но так как я гуманитарий, то точно сказать не могу.
                            • +1
                              это могло бы разрушить цепочку, что только снижает шансы на успех в перспективе
                              Это не только гарантированно разрушит цепочку, разумеется, но и не даст многим даже начать этот алгоритм, т.к. коробки с их номером уже нету, убрали с чьим-то другим номером.
                              • 0
                                Да, это я и имел ввиду.
                              • 0
                                В абсолютных величинах это ничего бы не изменило, т.к. первый заключенный имел бы шансы 31.18% и никак больше.

                                У первого заключённого должно быть больше шансов, поскольку второе утверждение более слабое
                                1. нет ни одной последовательности, длиной больше 50
                                2. длина первой последовательности больше 50
                            • +7
                              Как, вы ещё не смотрите MinutePhysics? Тогда я просто оставлю это здесь:
                              • 0
                                Чуть более гуманная задача ))
                                • 0
                                  Большое спасибо за канал!
                                • 0
                                  >> Если максимальная длина самой длинной цепочки меньше, чем 50 коробок, тогда все заключенные пройдут испытание!
                                  А если в первой цепочке на 45 коробок не оказалось искомого номера?
                                  • +3
                                    Значит это не цепочка, раз нет таблички с номером первой коробки.
                                    • 0
                                      Значит мы никак не можем попасть в эту цепочку, следуя описанному в статье алгоритму.
                                    • +8
                                      Я долго думал, что в этой задаче мне не нравится и понял. Это даже не то, что вероятность успеха всего 31 процент, черт с ней. Это то, что эту вероятность определяют не заключенные и не случайность, а тюремщик. Если он изначально разложит коробки в цепочку длиной 100 — все умрут, нет никаких алгоритмов спасения. Т.е. это уже не такие себе «логические шахматы на выживание» получаются, а игра маньяка с жертвами.
                                      • +2
                                        все умрут, нет никаких алгоритмов спасения
                                        На каждого хитрого маньяка найдется «дополнительный вопрос» из условия.
                                        • +1
                                          Ну можно попробовать решить задачу поиска решения оптимала в этом случае.
                                          Если точно известно что тюремщик сволочь знает эту стратегию и наверняка сделает цепочку длиной больше 50.
                                          Не удивлюсь еслив этом случае вероятность спасения можно повысить.
                                          • +11
                                            Можно выбрать заранее некоторую перестановку — и применять ее каждый раз перед выбором очередной коробки. Иными словами, получаем измененный алгоритм вида «открывать коробку с номером f(x), где x — табличка из прошлой коробки либо номер самого заключенного для первой итерации». Это эквивалентно тому, как если бы перед экспериментом все коробки случайно перемешали.
                                            • 0
                                              Если тюремщик будет всегда складывать в самую длинную цепочку типа 1->2->3->....->n->1, то никакая перестановка не поможет.
                                              • +1
                                                Почему? Перестановка /k->k+1/ даст 2 цикла по n/2 коробок, а перестановка /k->k-1/ даст после композиции тривиальную.

                                                В общем случае, композиция случайной перестановки и фиксированной — полностью случайна — тюремщик не может сделать ничего (если только не подглядит перестановку, о которой договорились заключенные)
                                                • 0
                                                  Да, согласен. Сначала немного не правильно вас понял.
                                                  Получается что если заключенные выберут рандомно число m и затем будут применять перестановку (k -> (k+m)%n), то получится неплохой рандомизированный алгоритм. Теперь надо пересчитать вероятность :)
                                                  Т.е. получается вопрос такой: какая вероятность что будет цепочка длиной 50 и более если число m выбрано случайно из промежутка [1..n)?
                                                  • +1
                                                    Если изначальное распределение было равномерным, то и новое распределение будет равномерным и вероятность победы не изменится. Иначе надо считать в зависимости от распределения:)
                                                    • 0
                                                      Можно просто менять цифры местами: 39 карточка ведет к 93 коробке, 1 к 10, 10 к 1. А 100 оставляем без изменений. Не придется учить заключенных считать остатки от деления :)
                                                      • 0
                                                        А где вы видели остаток от деления? Если вы про (k+m)%n — то это примитивнейший случай, сводится к одному вычитанию.
                                                • +4
                                                  О, ура, гармония вернулась в мир. Всё снова определяется логикой и математикой, а не злым умыслом. Думаю, Ваш комментарий надо бы добавить в статью, поскольку он реально повышает вероятность выживания в случае тюремщика со злым умыслом.
                                              • 0
                                                Блин, у меня мозг взорвался, может кто то сможет подсказать, какова вероятность, что 1ый заключенный поменяв 2 коробках таблички местами гарантирует 100% вероятность свободы и с какой вероятностью он может этой заменой создать цепочку длиннее 50?

                                                Или я затупил и менять местами нужно после обнаружения цепочки длиннее 50?
                                                • +1
                                                  Вы неправильно поняли условия второй задачи. Таблички меняет не заключенный, их меняет третье лицо. Он может свободно открывать любые коробки и смотреть на их содержимое — потому что его никто не видит.
                                                • +10
                                                  Отличная задачка и действительно красивое решеньице.
                                                  Мне всегда было интересно, как выдумываются такие задачи? Сначала приходит в голову красивая стратегия, а потом подгоняют задачу?

                                                  Занудская придирка: по добру, нехорошо говорить «самая оптимальная». Оптимальный — это уже наилучший, оптимум — уже экстремум.
                                                  Не пишу в личку, потому что часто на это натыкаюсь на хабре. Обычным людям простительно, а технарям — не очень, потому как слово в обиход как раз из матана и пришло.
                                                  • 0
                                                    Местами таблички менять нельзя;
                                                    Йода магистр согласен с вами :)
                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                      • +1
                                                        Спасибо за статью. Интересная задача, интересное решение.

                                                        Для тех, кто подзабыл теорию вероятностей, как я, начинается небольшой ступор с места «Еще немного математики». Напомните, что означает (100 l) на картинке? Как получили, что 100! способов раскладок табличек вероятность существования цепочки длиной l (в нашем случае l > 50) = 1/l? То есть, допустим, если мне нужна цепочка только длинной l = 51, то вероятность её появления 1/51? Спасибо.
                                                        • +2
                                                          (100 l) — число сочетаний из 100 по l, т.е. количество способов выбора l элементов из 100 без учета порядка, также обозначается как C_100^l. (тут в статье, видимо, опечатка — вероятность события никак не может быть числом больше единицы, а C_100^l при 50 < l < 100 больше единицы)
                                                          Всего есть 100! перестановок длины 100 (единицу отправляем на одно из 100 мест, двойку на одно из оставшихся 99 свободных, тройку на одно из 98 и т.д.)
                                                          Чтобы получить цепочку длины l > 50 нужно: выбрать элементы, из которых будет строиться цепочка — это можно сделать C_100^l способами; выбрать, как расположить элементы в цепочке — (l — 1)! способов (выбираем, в какой из l — 1 элементов переходит наименьший элемент цепочки, в какой из l-2 переходит этот и т.д. — последний элемент цепочки обязан переходить в первый); выбрать, как расположить элементы вне цепочки — (100 — l)! способов. Каждую перестановку мы посчитали ровно один раз, т.к. элементы, образующие цепочку, определяются однозначно.
                                                          Итого перестановок с цепочкой длины l: C_100^l * (l — 1)! * (100 — l)!
                                                          Т.е. C_n^k = n! / k! / (n-k)!, то C_100^l * (l — 1)! * (100 — l)! = 100! / l. Всего перестановок из 100 элементов 100!, так что вероятность наличия цепочки длины l равно 1 / l (для l > 50).
                                                          • 0
                                                            Спасибо за разъяснения. Теперь понятно. Для наглядности не хватает визуализации :) В ролике выше этого не показано — именно вычисление 31 процента.
                                                        • 0
                                                          Немного не понял, как вероятность на спасение может быть больше 0 при наличии цепочки в 51 коробку? Ведь тогда 51 заключенный не дойдет до конца цепочки.
                                                          • +2
                                                            Никак. Вычисленная в статье вероятность — это вероятность отсутствия такой цепочки.
                                                          • +1
                                                            Ничего не написано про то, что нельзя двигать коробки. Можно было бы сделать, что бы заключённые по мере прохождения цепочки, выставляли коробки цепочки в отдельный ряд. И новый заключённый, который вошёл, увидел бы свой номер в отдельном ряду, взял бы предыдущую коробку с его номером, а если его коробка первая, то взял бы последнюю. Если в ней оказывался не его номер, то он бы продолжал выкладывать цепочку из коробок, которую не завершил предыдущий заключённый (особенно, на случай, если длина цепочки больше 50). В этом случае вероятность того, что заключённые спасутся будет сильно больше 50% — это вероятность, что первый заключённый, чей номер находится в цепочке длиной более 50 найдёт свой номер за 50 ходов.
                                                            • 0
                                                              По условию задачи, все заключенные должны найти свои номера. Согласно алгоритму они начинают с конца этой цепочки, выстраивание в ряд не поможет — выстраивающий её до своего номера не дойдет, т.к. цепочка длиннее 50 шагов.
                                                              Ваш способ поможет изменить время, но не вероятность прохождения для группы.
                                                              • –1
                                                                Это только первый заключённый, чей номер находится в цепочке больше 50. Если он за 50 попыток не найдёт свой номер, то все. Если найдёт, то ему лучше достроить цепочку до 50, что бы следующий заключённый из длинной цепочки достроил её менее, чем за 50 ходов, т.к. всего коробок 100, и длина самой длинной цепочки не может быть больше 100.
                                                                Хотя если длина самой большой цепочки будет равна 100, то второй заключённый тоже может не найти свой номер (в случае если его нет в уже собранной последовательности), т.к. он сможет добавить в последовательность только 49 коробок из-за того, что ему придётся открыть одну коробку из уже собранной последовательности.
                                                            • 0
                                                              А я правильно понимаю, что есть дополнительное условие, при котором описанная стратегия работает, и согласно нему коробка не может указывать сама на себя?
                                                              • +2
                                                                Насколько я понял, это не обязательно. Если коробка указывает сама на себя, то мы имеем очень короткую цепочку из одной коробки. Заключённый заходит, берёт свою табличку, уходит. В дальнейшем эта коробка не участвует в работе.
                                                                • 0
                                                                  Точно. Всё сложилось, спасибо.
                                                              • 0
                                                                Огромное спасибо за задачку. Прочитал начало статьи в момент ее публикации, и заставил себя не смотреть решение. Решал задачу неделю. Заставил жену и еще пару друзей прочитать решение, чтобы удостовериться, что нет никаких подвохов.
                                                                Если бы не жена, которая угрожала, что перестанет уважать, я бы сдался)

                                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.