Задача про збіги
П'єр Ремон де Монмор розглянув задачу в «Essay d'analyse sur les jeux de hazard» 1708 року і розв'язав її в другому виданні 1713-го. Приблизно тоді ж її розв'язав Ніколаус Бернуллі.
Гості здали капелюхи в гардероб і отримали номерки. Гардеробник упустив усі номерки, перемішав їх і тепер роздає капелюхи зовсім навмання: кожен гість отримує один капелюх, але який саме, вирішує випадок. Яка ймовірність, що жоден гість не піде додому у своєму капелюсі? І чи інакше вона для 10 гостей, ніж для 100?
Інтуїція підказує, що з ростом кількості гостей шанс має або падати до нуля, або рости до 100%. Насправді він майже одразу застигає: для 2 гостей 50%, для 3 — 33,3%, для 4 — 37,5%, а з 7 гостей і далі 36,79%, і для 100 гостей так само. Це число 1/e. Причина в тому, що свій капелюх у середньому отримує рівно один гість, хоч скільки людей у гардеробі.
Задачі понад триста років. Її розв'язували Монмор, Ніколаус Бернуллі та Ейлер, а сьогодні вона живе в листах, розкладених не в ті конверти, і в Таємному Санті, де ніхто не має витягнути сам себе. Ми розповідаємо її через гардероб.
На вечірку прийшли n гостей, у кожного свій капелюх. Кожен здає капелюх у гардероб і отримує номерок з його номером.
Гардеробник упустив номерки, і тепер не знає, де чий капелюх. Наприкінці вечора він роздає капелюхи зовсім навмання: кожен гість отримує рівно один капелюх, усі капелюхи роздано, і будь-яка розкладка капелюхів по гостях однаково ймовірна.
Якщо гість отримав саме свій капелюх, це збіг. Збігів може бути скільки завгодно, від нуля до n.
Яка ймовірність, що збігів не буде зовсім, тобто ніхто не отримає свій капелюх? І як вона змінюється, якщо гостей не 10, а 100?
«Ста гостям ніяк не вдасться всім промахнутися» або «серед ста хтось та вгадає»
Обидві думки звучать переконливо, і обидві хибні. Шанс, що ніхто не отримає свій, для 100 гостей такий самий, як для 10: 36,79%. Кожен гість має менше шансів вгадати, але й гостей більше, і в середньому свій капелюх отримує рівно один.
Порівняйте два гардероби: на 10 гостей і на 100. Зафіксуйте відповідь, перш ніж читати далі.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Почніть з малого. Для двох гостей і для трьох випишіть усі способи роздати капелюхи і порахуйте, у скількох ніхто не отримав свій.
Подивіться на одного гостя: з якою ймовірністю він отримає саме свій капелюх? А скільки таких гостей у гардеробі?
Гостей більшає, але шанс кожного вгадати меншає. Як ці два ефекти діють разом на середню кількість гостей зі своїм капелюхом?
Вісім вечірок, щоразу інша кількість гостей. Перед кожною роздачею поставте від 1 до 3 фішок на те, скільки гостей отримає свій капелюх: ніхто (виграш ×2,7), рівно один (×2,7) чи двоє й більше (×3,8). Старий гардеробник Петрович ставить на ті самі роздачі за своїм чуттям: «у малому гардеробі хтось та вгадає, а у великому — ніхто». У кожного 20 фішок. Хто закінчить з більшими?
Після кількох роздач відповідь стає помітною, тож спершу вгадайте самі.
Для кожної кількості гостей від 1 до 20 сторінка багато разів роздає капелюхи навмання (чесне перемішування, як тасування колоди) і рахує, у якій частці роздач ніхто не отримав свій. Точки — симуляція, лінія — точна ймовірність за формулою з раунду 4. Окремо сторінка рахує, скільки гостей у середньому отримують свій капелюх.
Спершу на пальцях: чому шанс не прямує ні до нуля, ні до одиниці. Потім точний підрахунок і звідки береться число e.
Шар «На пальцях» приховано на всіх задачах.
Візьміть одного гостя. Гардеробник дає йому один капелюх з n, тож свій він отримує з шансом 1/n. Чим більше гостей, тим менше шансів у кожного, але тим більше тих, хто може вгадати, і ці два ефекти точно врівноважуються: у середньому свій капелюх отримує рівно один гість, хоч у гардеробі 10 людей, хоч мільйон. Тому шанс «ніхто» не тоне до нуля й не росте до 100%: картина з великими гардеробами така сама, як з малими.
Ця картка не доводить, що відповідь саме 36,8%, а лише пояснює, чому вона не залежить від n. Грубу оцінку дає таке міркування: кожен гість промахується з шансом 1 − 1/n, і якби гості промахувалися незалежно, усі разом промахнулися б з шансом (1 − 1/n)ⁿ. Для 10 гостей це 34,9%, для 100 — 36,6%, і з ростом n це число теж прямує до 1/e. Але гості залежні (якщо ваш капелюх уже в когось, він не дістанеться сусідові), тож точна відповідь трохи інша: 36,79%. Звідки вона, у наступних шарах.
Квадратик — гість, колір і цифра на ньому — чий капелюх він отримав. Обведено гостей, які отримали свій. Для двох гостей роздач лише дві: кожен отримав свій або вони помінялися, тож шанс «ніхто» 1/2. Для трьох гостей роздач шість, і ніхто не вгадав лише у двох (обведені рамкою): 1/3. Для чотирьох 9 з 24 = 3/8 = 37,5%, для п'яти 44 зі 120 = 36,7%. Шанс то трохи вищий, то трохи нижчий, і коливання швидко згасають.
Шар «Строго» приховано на всіх задачах.
Усіх роздач n! (n факторіал: n · (n − 1) · … · 1). Відкинемо ті, де гість 1 отримав свій: решту капелюхів можна роздати (n − 1)! способами. Так для кожного з n гостей, разом n · (n − 1)! = n!. Але роздачі, де вгадали двоє, ми відкинули двічі, тож повертаємо їх: пар гостей n(n − 1)/2, для кожної (n − 2)! роздач, разом n!/2!. Тепер роздачі з трьома збігами пораховано неправильно, віднімаємо n!/3!, і так далі до n. Поділимо на n!, і вийде ймовірність, що ніхто не вгадав:
P(n) = 1 − 1 + 1/2! − 1/3! + 1/4! − … ± 1/n! → 1/e ≈ 0,367879
Це рівно початок відомого ряду для 1/e. Кожен новий гість додає один доданок ±1/n!, а факторіали ростуть шалено швидко: 11-й гість змінює шанс лише на 1/11! ≈ 0,000000025. Тому відповідь майже не залежить від n: після кількох гостей доданки вже нічого не важать.
Нехай Dn — кількість роздач n гостям, у яких ніхто не вгадав. Гість 1 отримав капелюх якогось гостя j: n − 1 варіантів. Далі два випадки. Або гість j отримав капелюх гостя 1, вони просто помінялися, і решта n − 2 гостей мусять не вгадати: Dn−2 способів. Або гість j отримав щось інше: тоді вважаймо капелюх гостя 1 «чужим своїм» для j, і n − 1 гостей мусять не вгадати: Dn−1 способів.
Кількість збігів — це сума n «лампочок»: лампочка гостя i горить, якщо він отримав свій капелюх. Кожна горить з шансом 1/n. Гості залежні, але математичне сподівання суми — це сума сподівань завжди, без жодних умов. Тож середня кількість збігів дорівнює n · 1/n = 1 точно, для будь-якого n ≥ 1. Симуляція в раунді 3 це підтверджує.
Більше того, кількість збігів для великого n розподілена майже як розподіл Пуассона із середнім 1: рівно k збігів трапляються з шансом, близьким до e−1/k!. Нуль і один збіг однаково ймовірні, по 36,8%, два — 18,4%, три — 6,1%. Подивитися, як це виглядає, можна в раунді 5.
Перестановка без жодного збігу називається безладом. Їх кількість дає включення-виключення.
Похибка після n гостей менша за перший відкинутий доданок, тому для n ≥ 1 кількість безладів — це n!/e, округлене до цілого.
Рівно k збігів: обрати, хто вгадав, і щоб решта n − k не вгадали. Середнє і дисперсія дорівнюють 1 для n ≥ 2.
Шар «Глибше» приховано на всіх задачах.
Першим задачу розглянув П'єр Ремон де Монмор у книжці «Essay d'analyse sur les jeux de hazard» (1708), однієї з перших книжок про теорію ймовірностей. Розв'язок він дав у другому виданні 1713 року; приблизно тоді ж задачу розв'язав Ніколаус Бернуллі. Відтоді її називають задачею про збіги (problème des rencontres).
Леонард Ейлер, не знаючи про роботу Монмора, розібрав ту саму задачу в статті «Calcul de la probabilité dans le jeu de rencontre» (Мемуари Берлінської академії, 1753). Двоє гравців одночасно тягнуть по карті зі своїх колод; якщо колись витягнуть однакові, виграє перший, якщо ні — другий. Ейлер склав таблицю для 1–15 карт, помітив, що з 12 карт перші дев'ять знаків уже не змінюються, і впізнав у ряді 1/e. За його словами, шанси гравців відносяться приблизно як 12 до 7, і для звичайної колоди з 52 карт це вже дуже точно.
Кількість безладів Dn часто пишуть як !n і називають субфакторіалом; цю назву дав Вільям Аллен Вітворт. Числа ростуть майже як факторіал: !4 = 9, !5 = 44, !10 = 1 334 961, і кожне дорівнює n!/e, округленому до цілого. Ланцюжок Dn = n · Dn−1 + (−1)n дає їх ще швидше, ніж рекурсія з двома попередніми.
Ейлер помітив і ще одну деталь: для парної кількості карт шанс «жодного збігу» трохи вищий за 1/e, для непарної — трохи нижчий. Це видно і в раунді 3: точна лінія погойдується навколо 1/e, і розмах коливань швидко згасає.
Математика: не лише «ніхто», а будь-яка кількість збігів, і як вона перетворюється на розподіл Пуассона. Логіка: чому новий гість майже нічого не змінює. Практика: жеребкування Таємного Санти, яке доводиться повторювати.
Математика
Щоб збігів було рівно k, треба обрати, хто з гостей вгадав, а решта n − k мусять не вгадати. Шанс виходить (1/k!) · Dn−k/(n − k)!, а другий множник для великого n — це ті самі 1/e. Тож для великих гардеробів рівно k збігів трапляються з шансом e⁻¹/k!: це розподіл Пуассона із середнім 1. Ним описують рідкісні незалежні події: дзвінки в кол-центр за хвилину, розпади атомів, листи з помилками.
Цікаво, що рівно один збіг для n гостей має той самий шанс, що «ніхто» для n − 1 гостя. Тому нуль і один збіг такі рівні вже з 6–7 гостей. А в малих гардеробах розподіл ламається: для двох гостей рівно один збіг неможливий, бо коли один отримав свій, другому лишився теж свій. Подивіться на n = 2, 3, 4 на графіку.
Логіка
Інтуїція бачить лише один ефект: або «гостей багато, хтось та вгадає», або «у кожного шанс 1%, ніхто не вгадає». Насправді діють обидва, і вони гасять один одного: середня кількість збігів завжди 1. А все, що залежить від n, — це крихітні поправки ±1/n!. Після 10 гостей новий гість може зачепити лише доданок, менший за мільйонну частку.
Цей прийом корисний далеко за межами гардероба. Коли щось росте, а щось інше меншає пропорційно, дивіться на добуток: тут n · 1/n = 1. Ви побачите його в рідкісних подіях, у страхуванні, у пошуку помилок у коді: багато можливостей, кожна малоймовірна, у середньому кілька подій, і їх кількість описує той самий Пуассон.
Практика
У Таємному Санті кожен тягне з шапки папірець з ім'ям того, кому дарує подарунок. Якщо хтось витяг себе, найпростіше все перетягнути. Вдала спроба — це безлад, тож вона вдається лише в 36,8% випадків, і в середньому знадобиться 1/(1/e) = e ≈ 2,72 спроби. Для 10 учасників перша спроба вдається в 36,8% випадків, а три спроби й більше знадобляться в 40%, чотири й більше — у 25%.
Можна обійтися без повторів: поставити всіх у випадкове коло, і кожен дарує сусідові праворуч. Ніхто не дарує собі, але такий спосіб дає лише роздачі одним великим колом: для 5 учасників це 24 з 44 можливих безладів, і двоє ніколи не дарують подарунки одне одному. Якщо хочете, щоб усі безлади були однаково ймовірні, чесно перетягуйте.
П'єр Ремон де Монмор розглянув задачу в «Essay d'analyse sur les jeux de hazard» 1708 року і розв'язав її в другому виданні 1713-го. Приблизно тоді ж її розв'язав Ніколаус Бернуллі.
Ейлер 1753 року підсумував гру в збіги так: шанс, що збіг буде, відноситься до шансу, що не буде, приблизно як 12 до 7, точніше як 1720 до 1001. Із 19 партій перший гравець виграє приблизно 12.
У таблиці Ейлера від 12 карт шанс «жодного збігу» вже не змінюється в перших дев'яти знаках після коми: 0,367879442. Більші колоди нічого не додають.
Хоч у гардеробі 3 гості, хоч 3 мільйони, у середньому свій капелюх отримує рівно один. Це точне число, а не наближення, і воно не вимагає, щоб гості були незалежні.
Якщо перетягувати, доки ніхто не витягне себе, у середньому знадобиться e ≈ 2,72 жеребкування. Для 10 учасників точне число 3 628 800 / 1 334 961 ≈ 2,71828.
Кількість безладів позначають !n і називають субфакторіалом, цю назву дав Вільям Аллен Вітворт. !10 = 1 334 961, а для будь-якого n ≥ 1 це n!/e, округлене до цілого.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Поглиблено» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.