Чемпіонат світу 2014
У заявці кожної збірної на чемпіонат світу з футболу 2014 року було рівно 23 гравці. BBC перевірила дати народження: спільний день народження знайшовся в 16 командах з 32, тобто рівно в половині, як і передбачає формула.
Скільки людей має бути в кімнаті, щоб двоє з них, імовірно, народились в один день? Зафіксуйте свою відповідь, а потім перевірте її в грі, на симуляції та через п'ять пояснень.
Скільки людей має бути в кімнаті, щоб двоє з них, імовірно, народились в один день? Більшість відповідає «десь 180». Правильна відповідь: 23. А серед 70 людей збіг майже гарантований. Перевірте це в грі, на симуляції та через п'ять пояснень.
Задачу про дні народження (її ще називають парадоксом днів народження) приписують математику Річарду фон Мізесу (1939). Парадоксом її називають не через суперечність, а тому, що правильна відповідь звучить неймовірно.
У кімнаті зібралося n людей: клас, команда, гості на весіллі. Ніхто з них не домовлявся про дати народження.
У році 365 днів. Вважаємо, що кожна людина могла народитися в будь-який із них з однаковою ймовірністю. 29 лютого ігноруємо.
Збіг означає, що хоча б двоє людей народилися в один день і місяць. Рік не важливий. Хто саме, теж не важливо: підходить будь-яка пара.
За якого найменшого n шанс збігу перевищує 50%? І який шанс у класі з 30 учнів?
«Днів 365, отже, потрібна десь половина, близько 183 людей»
Насправді вистачає 23. У класі з 30 учнів збіг трапляється в 70% випадків. Помилка в тому, що ми думаємо про свій день народження, а рахувати треба всі пари людей.
У реальному житті народжуваність нерівномірна, і це лише підвищує шанс збігу. Детальніше в раунді 4.
Зафіксуйте свою відповідь, перш ніж читати далі. Так ви побачите, наскільки сильно промахується інтуїція.
Тут з'явиться порівняння вашої відповіді з правильною.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Не думайте про власний день народження. Збіг може статися в будь-якій парі людей у кімнаті, а не лише в парі з вами.
Рахуйте пари, а не людей: кожен новий гість утворює пару з усіма, хто вже є. А шанс зручніше рахувати через протилежну подію: усі дні різні.
10 людей утворюють 45 пар, і шанс збігу вже близько 12%. Кожна пара збігається з шансом 1/365. Скільки пар треба, щоб шанс дійшов до половини, і скільки людей дають стільки пар?
Наступні раунди показують, скільки людей потрібно для шансу 50%: кімната, яку ви збираєте, 10 000 кімнат і пояснення. Спершу відповісти в раунді 1 чи йти далі?
Ви обрали завжди показувати всі раунди.
Кожна нова людина отримує випадковий день народження й займає клітинку календаря. Коли двоє потрапляють в один день, клітинка спалахує. Зберіть 10–15 кімнат: праворуч видно, на якій людині зазвичай трапляється перший збіг.
Теорія: медіана 23, середнє ≈ 24,6. Пурпурний стовпчик містить медіану ваших кімнат.
Комп'ютер створює тисячі кімнат по n людей і рахує частку кімнат зі збігом. Лінія на графіку показує точну формулу, точки показують симуляцію.
Після вашої відповіді тут з'явиться код симуляції, який можна запустити в себе.
Та сама симуляція коротко і без бібліотек. JavaScript запускається в консолі браузера (F12) або в Node, Python потребує лише стандартної бібліотеки.
// Кімнати по 23 людини з випадковими днями народження (365 днів, усі однаково ймовірні).
const N = 23, DAYS = 365, ROOMS = 100000;
let hits = 0;
for (let r = 0; r < ROOMS; r++) {
const seen = new Set(); // дні, які вже зайняті в цій кімнаті
for (let i = 0; i < N; i++) {
const d = Math.floor(Math.random() * DAYS);
if (seen.has(d)) { hits++; break; } // збіг: двоє в один день
seen.add(d);
}
}
let allDiff = 1; // точно: усі N днів різні
for (let i = 0; i < N; i++) allDiff *= (DAYS - i) / DAYS;
console.log(`Кімнат зі збігом (симуляція): ${(100 * hits / ROOMS).toFixed(1)}%`);
console.log(`Точна формула 1 − 365·364·…·343 / 365²³: ${(100 * (1 - allDiff)).toFixed(1)}%`);
# Кімнати по 23 людини з випадковими днями народження (365 днів, усі однаково ймовірні).
import random
N, DAYS, ROOMS = 23, 365, 100_000
hits = 0
for _ in range(ROOMS):
days = [random.randrange(DAYS) for _ in range(N)]
if len(set(days)) < N: # збіг: двоє в один день
hits += 1
all_diff = 1.0 # точно: усі N днів різні
for i in range(N):
all_diff *= (DAYS - i) / DAYS
print(f"Кімнат зі збігом (симуляція): {100 * hits / ROOMS:.1f}%")
print(f"Точна формула 1 − 365·364·…·343 / 365²³: {100 * (1 - all_diff):.1f}%")
Ключ у тому, що збіг може статися в будь-якій парі, а пар значно більше, ніж людей. Ось п'ять способів це побачити.
Шар «На пальцях» приховано на всіх задачах.
Коли ми уявляємо задачу, ми підставляємо себе: «хто ще народився 14 березня?». Це інша, набагато рідкісніша подія. Ваш день перевіряється лише в 22 парах, а всього пар 253.
Насправді народжуваність коливається: у деякі місяці дітей народжується більше, у свята менше. Будь-яка нерівномірність підвищує шанс збігу, бо люди частіше потрапляють в «популярні» дні. Рівномірний календар є найгіршим випадком, тож 23 є верхньою межею.
А серед 366 людей збіг гарантований на 100% (без 29 лютого). Це принцип Діріхле: якщо голубів більше, ніж кліток, хоча б двоє опиняться в одній.
Шар «Строго» приховано на всіх задачах.
Перша людина може народитися будь-коли. Друга має не влучити в її день: шанс 364/365. Третя має обійти вже два дні: 363/365. Кожен множник майже дорівнює 1, але їх перемножується багато. Після 23-ї людини добуток падає нижче 50%.
Шанс, що в n людей усі дні народження різні: кожна наступна людина має уникнути вже зайнятих днів.
Те саме коротше, через факторіали. Збіг є, коли не виконалося «всі різні».
Зручне наближення. У показнику кількість пар, поділена на кількість днів.
Скільки людей потрібно для шансу 50%, якщо «днів» D.
Наближення пояснює все: показник степеня дорівнює кількості пар, поділеній на кількість днів. Тому потрібна кількість людей зростає як квадратний корінь із кількості днів. Для 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³², тобто приблизно 4,3 мільярда. Сучасний комп'ютер робить це за хвилини. Тому в криптографії використовують хеші довжиною 256 біт: для них колізія потребує 2¹²⁸ спроб, а це недосяжно.
У класі з 30 учнів 435 пар, а на весіллі на 100 гостей їх 4 950. Шанс, що на такому весіллі немає жодного спільного дня народження, приблизно 1 до 3 300 000.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Шкільна математика» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.