Задача з наукової статті
Анна Гал і Петер Бро Мільтерсен описали задачу в статті про структури даних на конференції ICALP 2003. У них були не в'язні, а кольорові смужки паперу. Стратегію петлі їм підказав колега з Орхуського університету Свен Скюм.
У кожного з 100 в'язнів є лише 50 спроб, щоб знайти свій номер серед 100 коробок. Якщо шукати навмання, усі знайдуть свій номер з імовірністю 7,9·10⁻³¹, тобто практично ніколи. Але є проста стратегія, з якою в'язні виграють майже в третині випадків. Перевірте це в грі, на симуляції та через чотири пояснення.
Задачу вперше розглянули інформатики Анна Гал і Петер Бро Мільтерсен у 2003 році. Вона здається нерозв'язною: кожен в'язень знаходить свій номер з імовірністю 1/2, хоч би що він робив. І все ж разом вони можуть виграти майже в третині випадків.
У в'язниці 100 в'язнів з номерами від 1 до 100. У кімнаті стоять 100 коробок з тими самими номерами на кришках.
Наглядач кладе в кожну коробку один папірець з номером в'язня. Номери перемішані випадково, кожен номер лежить рівно в одній коробці.
В'язні по одному заходять у кімнату. Кожен може відкрити 50 коробок, щоб знайти свій номер. Потім він виходить, а кімната повертається до початкового стану.
Якщо кожен із 100 в'язнів знайде свій номер, усіх звільнять. Якщо помилиться хоча б один, усі залишаться у в'язниці. Домовитися можна лише заздалегідь, після початку спілкуватися не можна.
«Кожен вгадує з шансом 1/2, отже, разом шанс (1/2)¹⁰⁰. Це нуль»
Для випадкового пошуку це правда. Але в'язні можуть погодити стратегію, за якої їхні успіхи пов'язані: або майже всі знаходять свій номер разом, або багато помиляються одночасно. Тоді загальний шанс 31,2%.
Номери розкладені випадково, а наглядач не знає про план. Що буде, якщо знає, розглянемо в раунді 5.
Уявіть, що в'язні обрали найкращу можливу стратегію. З якою ймовірністю на волю вийдуть усі 100? Зафіксуйте відповідь, перш ніж читати далі.
Зменшимо в'язницю: 20 в'язнів, 20 коробок, кожен відкриває 10. Ви один із в'язнів. Шукайте свій номер за стратегією петлі або відкривайте коробки на свій вибір. Потім запустіть усіх 20 в'язнів і подивіться, чи вийдуть вони на волю.
Комп'ютер тисячі разів розкладає 100 номерів по коробках і для кожного розміщення знаходить найдовшу петлю. В'язні виграють, коли вона не довша за 50. Стовпчики показують симуляцію, лінія показує точну формулу.
Кожен в'язень відкриває половину коробок. Що більше в'язнів, то трохи менший шанс, але він ніколи не падає нижче 1 − ln 2 ≈ 30,69%. Навіть мільйон в'язнів виграють майже в третині випадків.
Стратегія не змінює шанс окремого в'язня: він і далі 1/2. Вона змінює те, як ці шанси пов'язані між собою.
З кожної коробки виходить рівно одна стрілка, і в кожну входить рівно одна, бо кожен номер лежить рівно в одній коробці. Тому стрілки завжди замикаються в петлі. Математики називають їх циклами перестановки.
Ви починаєте з коробки зі своїм номером. Вона лежить на якійсь петлі, і ви йдете вздовж неї. Остання коробка петлі веде назад до вашої, а отже, саме в ній лежить ваш номер. Тож ви завжди знаходите свій номер, коли петля замикається. Питання лише в тому, чи вистачить 50 спроб.
Отже, в'язні виграють, якщо в розміщенні немає петлі, довшої за 50. Довгих петель може бути щонайбільше одна: дві петлі по 51 не вмістяться в 100 коробок.
З обома стратегіями в середньому помиляються 50 в'язнів. Але за стратегією петлі помилки збираються в одне розміщення: в'язні на одній довгій петлі програють усі разом. Коли в'язні програють, у середньому помиляються близько 73 з них. Зате в 31% розміщень не помиляється ніхто.
Для k від 51 до 100 імовірність, що в розміщенні є петля рівно довжини k, дорівнює 1/k. Ці події не перетинаються, бо довга петля одна. Тож шанс програшу дорівнює сумі 1/51 + 1/52 + … + 1/100 ≈ 68,8%.
Тут Hn = 1 + 1/2 + … + 1/n є гармонічним числом. Петлю довжини k можна обрати так: вибрати k коробок, з'єднати їх у коло (k − 1)! способами, а решту коробок розкласти як завгодно. Ця стратегія найкраща з можливих: жоден інший план не дає більшого шансу.
Що буде, якщо дозволити відкривати більше або менше коробок? І що робити, якщо наглядач знає план в'язнів і розкладає номери навмисно?
Наглядач дізнався про стратегію петлі. Він розкладає номери так, щоб усі 100 коробок утворили одну велику петлю. Тоді жоден в'язень не знайде свій номер за 50 спроб.
100 в'язнів. Натисніть «Перевірити»: симуляція 10 000 розміщень покаже, що точна формула не помиляється.
| Спроб у кожного | Усі на волі (точно) |
|---|
Анна Гал і Петер Бро Мільтерсен описали задачу в статті про структури даних на конференції ICALP 2003. У них були не в'язні, а кольорові смужки паперу. Стратегію петлі їм підказав колега з Орхуського університету Свен Скюм.
Юджин Кертін і Макс Воршауер довели, що стратегія петлі оптимальна: жоден інший план не дає в'язням більшого шансу. Доведення вийшло в журналі Mathematical Intelligencer у статті «The locker puzzle».
Широкій публіці задачу показав канал Veritasium. Відео назвали загадкою, яка здається неможливою, навіть коли знаєш відповідь.
100 номерів можна розкласти по 100 коробках 100! способами. Це число має 158 цифр. Приблизно в 31% із них найдовша петля не перевищує 50.
Коли стратегія петлі не спрацьовує, у середньому помиляються близько 73 в'язнів: усі, хто стоїть на довгій петлі. За випадкового пошуку помиляються близько 50, але майже ніколи не нуль.
Хоч скільки буде в'язнів, якщо кожен відкриває половину коробок, шанс усіх звільнити не падає нижче 1 − ln 2 ≈ 30,69%. Для 100 в'язнів це 31,18%, для 1 000 це 30,74%.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.