Математичні парадокси
Курс «Як проходити співбесіди із задачами» · розділ 3 з 18 →

100 в'язнів і 100 коробок У кожного шанс 50%. А в усіх разом?В усіх разом 31%.

У кожного з 100 в'язнів є лише 50 спроб, щоб знайти свій номер серед 100 коробок. Усіх звільнять, лише якщо свій номер знайде кожен. Який шанс у в'язнів із найкращою стратегією? Зафіксуйте свою відповідь, а потім перевірте її: у грі, на симуляції та в чотирьох поясненнях.

У кожного з 100 в'язнів є лише 50 спроб, щоб знайти свій номер серед 100 коробок. Якщо шукати навмання, усі знайдуть свої номери з імовірністю 7,9·10⁻³¹, тобто практично ніколи. Але є проста стратегія, з якою в'язні виграють майже в третині випадків. Перевірте це в грі, на симуляції та в чотирьох поясненнях.

Вгадати відповідь
7,9·10⁻³¹шанс, якщо шукати навмання

Умова задачі

Сто в'язнів, сто коробок, одна спроба

Задачу вперше розглянули інформатики Анна Гал і Петер Бро Мільтерсен у 2003 році. Вона здається нерозв'язною: кожен в'язень знаходить свій номер з імовірністю 1/2, хоч би що він робив. І все ж разом вони можуть виграти майже в третині випадків.

  1. 1

    В'язні й коробки

    У в'язниці 100 в'язнів з номерами від 1 до 100. У кімнаті стоять 100 коробок з тими самими номерами на кришках.

  2. 2

    Номери всередині

    Наглядач кладе в кожну коробку один папірець з номером в'язня. Номери перемішані випадково, кожен номер лежить рівно в одній коробці.

  3. 3

    Пошук

    В'язні по одному заходять у кімнату. Кожен може відкрити 50 коробок, щоб знайти свій номер. Потім він виходить, а кімната повертається до початкового стану.

  4. 4

    Умова виграшу

    Якщо кожен із 100 в'язнів знайде свій номер, усіх звільнять. Якщо помилиться хоча б один, усі залишаться у в'язниці. Домовитися можна лише заздалегідь, після початку спілкуватися не можна.

Інтуїція підказує

«Кожен знаходить свій номер із шансом 1/2, тож для всіх разом шанс (1/2)¹⁰⁰. Це нуль»

Для випадкового пошуку це правда. Але в'язні можуть погодити стратегію, за якої їхні успіхи пов'язані: або всі знаходять свої номери, або багато помиляються одночасно. Тоді загальний шанс 31,2%.

Чи є план?

Шукати навмання означає, що кожен в'язень вгадує незалежно від інших. Чи можна домовитися про план, кращий за пошук навмання? Подумайте, перш ніж вгадувати.

Номери розкладені випадково, а наглядач не знає про план в'язнів.

Стратегія петлі

  • Відкрийте коробку зі своїм номером.
  • Подивіться, який номер лежить усередині.
  • Відкрийте коробку з цим номером і повторюйте.

Чому «петля». Нехай ви в'язень №7. У коробці 7 лежить 12, у коробці 12 лежить 3, у коробці 3 лежить 7. Ви знайшли свій номер на третій спробі, а наступним кроком ланцюжок 7 → 12 → 3 повернувся б до коробки 7, з якої ви почали: він замкнувся в петлю. Так буває завжди: коробка перед поверненням містить ваш номер. Тож ви точно знайдете свій номер, якщо ваша петля не довша за 50 коробок.

Чому це допомагає. Усі в'язні, чиї коробки лежать на одній петлі, проходять ту саму петлю. Вони виграють або програють разом. Тому всі вийдуть на волю, якщо в розміщенні немає жодної петлі, довшої за 50. Ваш особистий шанс і далі 1/2, але невдачі в'язнів більше не незалежні. Детальніше в раунді 4.

Номери розкладені випадково, а наглядач не знає про план. Що буде, якщо знає, розглянемо в раунді 5.

Раунд 1 · Вгадайте

Який найкращий шанс у в'язнів?

Уявіть, що в'язні обрали найкращу можливу стратегію. З якою ймовірністю на волю вийдуть усі 100? Зафіксуйте відповідь, перш ніж читати далі.

Підказки

Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.

Далі розв'язок

Далі пояснення, і в ньому спойлери

Наступні раунди розкривають стратегію, яка рятує в'язнів: гра, симуляція і пояснення. Спершу відповісти в раунді 1 чи йти далі?

Ви обрали завжди показувати всі раунди.

Раунд 2 · Зіграйте в'язнем

20 коробок, 10 спроб

Зменшимо в'язницю: 20 в'язнів, 20 коробок, кожен відкриває 10. Ви один із в'язнів. Спробуйте стратегію петлі:

  1. відкрийте коробку зі своїм номером;
  2. подивіться, який номер лежить усередині;
  3. відкрийте коробку з цим номером і так далі.

Чому «петля». Коли ви знайдете свій номер, він вкаже на першу коробку, яку ви відкрили: ланцюжок замкнувся в петлю. Звідси й назва.

Порівняйте з пошуком навмання або відкривайте коробки на свій вибір. Потім запустіть усіх 20 в'язнів і подивіться, чи вийдуть вони на волю.

Ваш номер7
Спроб залишилось10
Ваші ігри–

Усі 20 в'язнів

Кружок — коробка з її номером. Стрілка веде від коробки до коробки з тим номером, що лежить усередині. З кожної коробки виходить одна стрілка і в кожну одна входить, тож 20 коробок завжди розпадаються на кілька замкнених петель. В'язень, що йде за петлею, обходить петлю, на якій лежить його коробка. Петлі, довші за 10, рожеві: на них спроб не вистачить.

    Раунд 3 · Симуляція

    10 000 випадкових розміщень

    Комп'ютер тисячі разів розкладає 100 номерів по коробках і для кожного розміщення знаходить найдовшу петлю. В'язні виграють, коли вона не довша за 50. Стовпчики показують симуляцію, лінія показує точну формулу.

    Довжина найдовшої петлі

    ≤ 50: усі на волі ≥ 51: в'язні програють точна формула
    Симуляція · усі на волі
    –
    Точна формула
    –

    Що буде з 1 000 чи мільйоном в'язнів?

    точна формула симуляція, 2 000 розміщень на точку межа 1 − ln 2

    Кожен в'язень відкриває половину коробок. Що більше в'язнів, то трохи менший шанс, але він ніколи не падає нижче 1 − ln 2 ≈ 30,69%. Навіть мільйон в'язнів виграє майже в третині випадків.

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

    Перевірте самі в коді

    Та сама симуляція коротко і без бібліотек. JavaScript запускається в консолі браузера (F12) або в Node, Python потребує лише стандартної бібліотеки.

    JavaScript
    // 100 в'язнів, стратегія петлі: кожен відкриває свою коробку, потім коробку з номером, який знайшов, і так 50 разів.
    const N = 100, TRIES = 50, TRIALS = 100000;
    
    function allFree() {
      const box = [...Array(N).keys()];               // box[i] — номер у коробці i
      for (let i = N - 1; i > 0; i--) {               // випадково перемішуємо
        const j = Math.floor(Math.random() * (i + 1));
        [box[i], box[j]] = [box[j], box[i]];
      }
      for (let p = 0; p < N; p++) {                   // в'язень p
        let b = p, found = false;
        for (let t = 0; t < TRIES && !found; t++) {
          found = box[b] === p;
          b = box[b];                                 // далі коробка з номером, що всередині
        }
        if (!found) return false;
      }
      return true;
    }
    
    let wins = 0;
    for (let i = 0; i < TRIALS; i++) if (allFree()) wins++;
    let exact = 1;                                    // 1 − (1/51 + … + 1/100)
    for (let k = TRIES + 1; k <= N; k++) exact -= 1 / k;
    console.log(`усі на волі: симуляція ${(100 * wins / TRIALS).toFixed(2)}%, точно ${(100 * exact).toFixed(2)}%`);
    
    Python
    # 100 в'язнів, стратегія петлі: кожен відкриває свою коробку, потім коробку з номером, який знайшов, і так 50 разів.
    import random
    
    N, TRIES, TRIALS = 100, 50, 100_000
    
    
    def all_free():
        box = list(range(N))                  # box[i] — номер у коробці i
        random.shuffle(box)
        for p in range(N):                    # в'язень p
            b = p
            for _ in range(TRIES):
                if box[b] == p:
                    break
                b = box[b]                    # далі коробка з номером, що всередині
            else:
                return False                  # 50 спроб, а свого номера немає
        return True
    
    
    wins = sum(all_free() for _ in range(TRIALS))
    exact = 1 - sum(1 / k for k in range(TRIES + 1, N + 1))
    print(f"усі на волі: симуляція {100 * wins / TRIALS:.2f}%, точно {100 * exact:.2f}%")
    
    Раунд 4 · Чотири пояснення

    Чому петля працює

    Стратегія не змінює шанс окремого в'язня: він і далі 1/2. Вона змінює те, як ці шанси пов'язані між собою.

    На пальцяхкартинки, аналогії, маленькі числа

    Шар «На пальцях» приховано на всіх задачах.

    Розміщення складається з петель

    Стрілка від коробки до номера всередині

    Згадайте Таємного Санту. Кожен дарує один подарунок і отримує один. Почніть із себе й питайте «кому ти даруєш?»: від вас до того, кому даруєте ви, від нього до того, кому дарує він, і так далі. Рано чи пізно ви прийдете до людини, яка дарує вам, а від неї назад до себе. Коло замкнулося.

    З коробками так само. Папірець повідомляє лише номер, а номер називає коробку. Тож єдине, що можна зробити з папірцем, це піти до коробки з цим номером. Намалюймо стрілку від кожної коробки до коробки, номер якої лежить усередині.

    З кожної коробки виходить рівно одна стрілка, бо в ній один папірець. І в кожну входить рівно одна, бо кожен номер лежить рівно в одній коробці. Тож коли ви йдете за стрілками, глухого кута не буває: у кожній коробці є номер, отже, завжди є наступна коробка. А врізатися в середину власного шляху не можна: у кожну коробку входить лише одна стрілка, і її ви вже пройшли. Коробок скінченна кількість, тож шлях колись повернеться до коробки, де вже був, і це може бути лише та, з якої ви почали. Тому стрілки завжди складаються в петлі. Математики називають їх циклами .

    Ваша петля

    Ви знайдете свій номер, якщо ваша петля не довша за 50

    Ви починаєте з коробки зі своїм номером і йдете за стрілками. Ваш номер лежить рівно в одній коробці, назвімо її X. Стрілка з X веде до коробки з вашим номером, тобто туди, звідки ви почали. Чи можна кружляти вічно й не повернутися до своєї коробки? Лише якби в якусь коробку входили дві стрілки, а такої немає. Тож шлях повертається до вашої коробки, і остання коробка, яку ви відкриєте перед цим, це X, та, де лежить ваш номер. Ви завжди знаходите свій номер, коли петля замикається. Питання лише в тому, чи вистачить 50 спроб.

    Отже, в'язні виграють, якщо в розміщенні немає петлі, довшої за 50. Довгих петель може бути щонайбільше одна: дві петлі по 51 не вмістяться в 100 коробок.

    Успіхи пов'язані

    Усі виграють разом або багато програють разом

    Навмання: кожен незалежно7,9·10⁻³¹шанс, що всі 100 знайдуть свої номери
    Петля: долі пов'язані31,2%шанс, що всі 100 знайдуть свої номери

    За обох стратегій у помиляються 50 в'язнів. Але за стратегією петлі помилки зосереджуються в тих самих розміщеннях: в'язні на одній довгій петлі програють усі разом. Коли в'язні програють, у середньому помиляються близько 73 з них. Зате в 31% розміщень не помиляється ніхто.

    Чому ж шанс кожного окремого в'язня так і залишається 1/2? Петля через вашу коробку з однаковою ймовірністю має будь-яку довжину від 1 до 100. Рівно половина цих довжин не більша за 50, тож ви знаходите свій номер з імовірністю 1/2, як і навмання. План не підвищує нічий особистий шанс. Він збирає невдачі в ті самі розміщення. Для порівняння, поганий план «усі відкривають коробки 1–50» щоразу провалює рівно 50 в'язнів: тих, чиї номери лежать у коробках 51–100.

    Усі випадки на долоні

    4 в'язні, по 2 спроби: усі 24 розміщення

    Чотири номери можна розкласти по чотирьох коробках 24 способами. Кожна картка нижче це одне розміщення: номери в коробках 1, 2, 3, 4 і петлі, з яких воно складається. За петлею в'язні виграють, коли жодна петля не довша за 2.

    Навмання: кожен незалежно1/16(1/2)⁴, тобто 6,25%
    Петля: виграшних розміщень10/24тобто 41,7%

    У кожному розміщенні кожен в'язень окремо знаходить свій номер у половині випадків, і за петлею, і навмання. Різниця в тому, як ці успіхи розподілені: за петлею в 10 розміщеннях виграють усі четверо, а в решті 14 програють одразу кілька в'язнів, ті, що на довгій петлі.

    Строготаблиці, графіки, формули

    Шар «Строго» приховано на всіх задачах.

    Рахуємо довгі петлі

    Шанс петлі довжини k дорівнює 1/k

    Для k від 51 до 100 імовірність, що в розміщенні є петля довжиною рівно k, дорівнює 1/k. Ці події не перетинаються, бо довга петля одна. Тож шанс програшу дорівнює сумі 1/51 + 1/52 + … + 1/100 ≈ 68,8%.

    Для тих, хто любить формули

    Точна відповідь і її межа

    Скільки перестановок мають петлю довжини k, більшу за половину. Рахуємо в три кроки:

    • обираємо k коробок для петлі: C(n, k) способів;
    • з'єднуємо їх у коло: (k − 1)! способів;
    • решту n − k коробок розкладаємо як завгодно: (n − k)! способів.
    Перестановок з петлею довжиниk>n/2 =C(n,k)·(k−1)!·(n−k)!=n!k

    Шанс програти: довга петля довжини k від 51 до 100 трапляється з шансом 1/k. Hn = 1 + 1/2 + … + 1/n, .

    P(програш)=151+152+…+1100 =H100−H50≈0,6882

    Шанс, що всі вийдуть на волю: довгої петлі немає.

    P(усі на волі)=1−(H100−H50)≈0,3118

    Що буде, коли в'язнів дуже багато: різниця гармонічних чисел прямує до ln 2.

    n→∞:Hn−Hn/2→ln2 ⇒P→1−ln2≈0,3069

    Для порівняння: якщо кожен в'язень відчиняє коробки навмання.

    P(навмання)=(12)100≈7,9·10−31

    Тут Hn = 1 + 1/2 + … + 1/n, гармонічне число. Щоб побудувати петлю довжини k, оберіть k коробок, з'єднайте їх у коло (k − 1)! способами, а решту коробок розкладіть як завгодно. Ця стратегія найкраща з можливих: жоден інший план не дає більшого шансу.

    Раунд 5 · Ускладнюємо

    Інша кількість спроб і підступний наглядач

    Що буде, якщо дозволити відкривати більше або менше коробок? І що робити, якщо наглядач знає план в'язнів і розкладає номери навмисно? А наприкінці кілька інших домовленостей, які програють петлі.

    n в'язнів, кожен відкриває k коробок

    Зі стратегією петлі
    Навмання

    Шанс залежно від кількості спроб

    стратегія петлі навмання

    Підступний наглядач

    Наглядач дізнався про стратегію петлі. Він розкладає номери так, щоб усі 100 коробок утворили одну велику петлю. Тоді жоден в'язень не знайде свій номер за 50 спроб.

    Усі на волі, 10 000 запусків
    Найдовша петля, яку бачать в'язні

    Станьте наглядачем самі

    10 коробок, кожен в'язень відкриває 5. Зараз в'язні виграють. Торкніться однієї коробки, потім іншої: папірці в них поміняються місцями. Зламайте стратегію петлі якомога меншою кількістю обмінів.

    Петлі ваших 10 коробок

    Обмін папірців двох коробок з різних петель зливає ці петлі в одну. Обмін усередині однієї петлі розрізає її на дві.

    А якщо дозволити 60 спроб?

    100 в'язнів. Натисніть «Перевірити»: симуляція 10 000 розміщень покаже, що точна формула не помиляється.

    Спроб у кожногоУсі на волі (точно)

    А інші домовленості?

    Кожен план нижче теж треба узгодити заздалегідь, і кожен програє петлі. 100 в'язнів, 50 спроб. «Перевірити» проганяє кожен план на 10 000 розміщень.

    ПланКожен знаходить свійУсі на волі

    Майже в кожному плані кожен в'язень окремо знаходить свій номер у половині випадків. Плани відрізняються тим, чи програють в'язні разом. Коробки 1–50 гарантують, що половина програє завжди. Дві половини трохи пов'язують долі в'язнів, і це вже в 12,6 раза краще, ніж навмання, але все одно безнадійно. Петля зі своєї коробки збирає всі невдачі на одній довгій петлі. А якщо почати з чужої коробки, ви йдете чужою петлею: падає навіть особистий шанс.

    Реальні дані · Перевірте на собі

    Перемішайте справжню колоду

    Комп'ютерним перемішуванням можна не довіряти. Перевірте на власних руках: 10 карт стануть 10 коробками, і ви побачите, чи вийшли б ваші в'язні на волю.

    1. Візьміть з колоди туз, двійку, трійку і так далі до десятки однієї масті. Туз означає 1.
    2. Добре перемішайте ці 10 карт і розкладіть їх у ряд сорочкою догори. Це коробки 1–10, зліва направо.
    3. Переверніть карти й введіть їхні значення по порядку, через пробіл.

    Петлі вашої колоди

    Карта в позиції 1 показує, яку позицію відкрити далі, і так по колу. Кожен із 10 в'язнів відкриває 5 карт. Петлі, довші за 5, виділено кольором: на них в'язні програють.

    Бонус · Цікаві факти

    Що розповісти друзям

    2003

    Задача з наукової статті

    Анна Гал і Петер Бро Мільтерсен описали задачу в статті про структури даних на конференції ICALP 2003. У них були не в'язні, а кольорові смужки паперу. Стратегію петлі їм підказав колега з Орхуського університету Свен Скюм.

    2006

    Краще не буває

    Юджин Кертін і Макс Воршауер довели, що стратегія петлі оптимальна: жоден інший план не дає в'язням більшого шансу. Доведення вийшло в журналі Mathematical Intelligencer у статті «The locker puzzle».

    YouTube

    Задача, яка підкорила інтернет

    Широкій публіці задачу показав канал Veritasium. У назві відео її названо загадкою, яка здається неможливою, навіть коли знаєш відповідь.

    9,33·10¹⁵⁷

    Стільки існує розміщень

    100 номерів можна розкласти по 100 коробках 100! способами. Це число має 158 цифр. Приблизно в 31% із них найдовша петля не перевищує 50.

    ≈ 73

    Програють гуртом

    Коли стратегія петлі не спрацьовує, у середньому помиляються близько 73 в'язнів: усі, хто стоїть на довгій петлі. За випадкового пошуку в середньому помиляються близько 50, а так, щоб не помилився ніхто, майже не буває.

    30,69%

    Мільйон в'язнів не страшний

    Хоч скільки буде в'язнів, якщо кожен відкриває половину коробок, шанс, що всіх звільнять, не падає нижче 1 − ln 2 ≈ 30,69%. Для 100 в'язнів це 31,18%, для 1 000 це 30,74%.

    Surprises in Probability

    Генк Теймс

    2019, англійською · розділ 8

    Algebraic Combinatorics

    Річард Стенлі

    2013, англійською · с. 187–189

    Усі книжки →
    Обговорення

    Що ви думаєте?

    Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.

    Рівень «Поглиблено» відповідає задачі?

    Дякуємо! Це допоможе точніше ставити рівні.

    Розсилка

    Нові задачі, пояснення й обговорення

    Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.

    Форма підписки з'явиться тут найближчим часом.