Математична задача про 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.000000000000000000000000000008


Тобто це дуже маленький шанс. При такому розкладі, швидше за все, всі ув'язнені будуть мертві.

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

Неймовірний відповідь

Якщо кожен ув'язнений буде відкривати скриньки навмання, то навряд чи вони пройдуть випробування. Існує стратегія, при якій ув'язнені можуть розраховувати на успіх більш ніж в 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%!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.