Чемпіонат світу 2014
У заявці кожної збірної на чемпіонат світу з футболу 2014 року було рівно 23 гравці. BBC перевірила дати народження: спільний день народження знайшовся в 16 командах з 32, тобто рівно в половині, як і передбачає формула.
Скільки людей має бути в кімнаті, щоб двоє з них, імовірно, народились в один день? Більшість відповідає «десь 180». Правильна відповідь: 23. А серед 70 людей збіг майже гарантований. Перевірте це в грі, на симуляції та через п'ять пояснень.
Задачу про дні народження (її ще називають парадоксом днів народження) приписують математику Річарду фон Мізесу, 1939 рік. Парадоксом її називають не через суперечність, а тому, що правильна відповідь звучить неймовірно.
У кімнаті зібралося n людей: клас, команда, гості на весіллі. Ніхто з них не домовлявся про дати народження.
У році 365 днів. Вважаємо, що кожна людина могла народитися в будь-який із них з однаковою ймовірністю. 29 лютого ігноруємо.
Збіг означає, що хоча б двоє людей народилися в один день і місяць. Рік не важливий. Хто саме, теж не важливо: підходить будь-яка пара.
За якого найменшого n шанс збігу перевищує 50%? І який шанс у класі з 30 учнів?
«Днів 365, отже, потрібно десь половину, близько 183 людей»
Насправді вистачає 23. У класі з 30 учнів збіг трапляється в 70% випадків. Помилка в тому, що ми думаємо про свій день народження, а рахувати треба всі пари людей.
У реальному житті народжуваність нерівномірна, і це лише підвищує шанс збігу. Детальніше в раунді 4.
Зафіксуйте свою відповідь, перш ніж читати далі. Так ви побачите, наскільки сильно інтуїція промахується.
Тут з'явиться порівняння вашої відповіді з правильною.
Кожна нова людина отримує випадковий день народження й займає клітинку календаря. Коли двоє потрапляють в один день, клітинка спалахує. Зберіть 10–15 кімнат: праворуч видно, на якій людині зазвичай трапляється перший збіг.
Теорія: медіана 23, середнє ≈ 24,6. Помаранчевий стовпчик містить медіану ваших кімнат.
Комп'ютер створює тисячі кімнат по n людей і рахує частку кімнат зі збігом. Лінія на графіку показує точну формулу, точки показують симуляцію.
Ключ у тому, що збіг може статися в будь-якій парі, а пар значно більше, ніж людей. Ось п'ять способів це побачити.
Перша людина може народитися будь-коли. Друга має не влучити в її день: шанс 364/365. Третя має обійти вже два дні: 363/365. Кожен множник майже дорівнює 1, але їх перемножується багато. Після 23-ї людини добуток падає нижче 50%.
Коли ми уявляємо задачу, ми підставляємо себе: «хто ще народився 14 березня?». Це інша, набагато складніша подія. Ваш день перевіряється лише в 22 парах, а всього пар 253.
Насправді народжуваність коливається: у деякі місяці дітей народжується більше, у свята менше. Будь-яка нерівномірність підвищує шанс збігу, бо люди частіше потрапляють в «популярні» дні. Рівномірний календар є найгіршим випадком, тож 23 є верхньою межею.
А серед 366 людей збіг гарантований на 100% (без 29 лютого). Це принцип Діріхле: якщо голубів більше, ніж кліток, двоє опиняться в одній.
Наближення пояснює все: показник степеня дорівнює кількості пар, поділеній на кількість днів. Тому потрібна кількість людей зростає як корінь із кількості днів. Для 365 днів це близько 23, а не 183.
Той самий принцип працює для будь-яких «днів»: місяців, PIN-кодів, хешів. І задачу можна ускладнити: шукати трьох людей з одним днем або тих, хто народився з різницею в день.
Обидві осі логарифмічні. Інтуїція чекає лінію «половина від D», а насправді потрібно ≈ √D. Для мільйона значень це 1 178 замість 500 000.
Натисніть «Перевірити»: симуляція 10 000 кімнат покаже, що на вказаній кількості людей шанс справді близько 50%.
| Що шукаємо | Людей для 50% |
|---|
У заявці кожної збірної на чемпіонат світу з футболу 2014 року було рівно 23 гравці. BBC перевірила дати народження: спільний день народження знайшовся в 16 командах з 32, тобто рівно в половині, як і передбачає формула.
Джеймс Полк і Воррен Гардінг народилися 2 листопада. А троє з перших п'яти президентів, Джон Адамс, Томас Джефферсон і Джеймс Монро, померли 4 липня, у День незалежності.
Шанс народитися 29 лютого близько 1 до 1 461. Ми виключили цей день з моделі, але якщо його повернути, відповідь не зміниться: 23 людини все одно дають шанс трохи понад 50%.
У багатьох країнах найбільше дітей народжується наприкінці літа й у вересні, а найменше на свята: 25 грудня та 1 січня. Пологи з плановою датою рідко призначають на святкові дні. Така нерівномірність лише підвищує шанс збігу.
Для 64-бітного хешу потрібно не 2⁶⁴ спроб, щоб знайти колізію, а лише близько 2³², тобто приблизно 5 мільярдів. Сучасний комп'ютер робить це за хвилини. Тому в криптографії використовують хеші довжиною 256 біт: навіть 2¹²⁸ спроб недосяжні.
У класі з 30 учнів 435 пар, а на весіллі на 100 гостей їх 4 950. Шанс, що на такому весіллі немає жодного спільного дня народження, приблизно 1 до 3 300 000.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.