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

Парадокс днів народження Скільки людей потрібно для збігу?23 людини. Шанс збігу понад 50%.

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

Скільки людей має бути в кімнаті, щоб двоє з них, імовірно, народились в один день? Більшість відповідає «десь 180». Правильна відповідь: 23. А серед 70 людей збіг майже гарантований. Перевірте це в грі, на симуляції та через п'ять пояснень.

Вгадати відповідь
23людини → 50,7%
70людей → 99,9%
Умова задачі

Уявіть: ви в класі з 30 учнів

Задачу про дні народження (її ще називають парадоксом днів народження) приписують математику Річарду фон Мізесу (1939). Парадоксом її називають не через суперечність, а тому, що правильна відповідь звучить неймовірно.

  1. 1

    Кімната

    У кімнаті зібралося n людей: клас, команда, гості на весіллі. Ніхто з них не домовлявся про дати народження.

  2. 2

    Календар

    У році 365 днів. Вважаємо, що кожна людина могла народитися в будь-який із них з однаковою ймовірністю. 29 лютого ігноруємо.

  3. 3

    Збіг

    Збіг означає, що хоча б двоє людей народилися в один день і місяць. Рік не важливий. Хто саме, теж не важливо: підходить будь-яка пара.

  4. 4

    Питання

    За якого найменшого n шанс збігу перевищує 50%? І який шанс у класі з 30 учнів?

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

«Днів 365, отже, потрібна десь половина, близько 183 людей»

Насправді вистачає 23. У класі з 30 учнів збіг трапляється в 70% випадків. Помилка в тому, що ми думаємо про свій день народження, а рахувати треба всі пари людей.

Припущення моделі

  • 365 днів, без 29 лютого.
  • Кожен день однаково ймовірний.
  • Дні народження людей незалежні: немає близнюків.

У реальному житті народжуваність нерівномірна, і це лише підвищує шанс збігу. Детальніше в раунді 4.

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

Скільки людей потрібно для шансу 50%?

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

Тут з'явиться порівняння вашої відповіді з правильною.

Підказки

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

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

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

Наступні раунди показують, скільки людей потрібно для шансу 50%: кімната, яку ви збираєте, 10 000 кімнат і пояснення. Спершу відповісти в раунді 1 чи йти далі?

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

Раунд 2 · Зберіть кімнату

Запрошуйте людей, поки не станеться збіг

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

Людей у кімнаті0
Збігів0
Шанс збігу за теорією0%

На якій людині стався перший збіг

1204060+

Теорія: медіана 23, середнє ≈ 24,6. Пурпурний стовпчик містить медіану ваших кімнат.

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

10 000 кімнат за секунду

Комп'ютер створює тисячі кімнат по n людей і рахує частку кімнат зі збігом. Лінія на графіку показує точну формулу, точки показують симуляцію.

точна формула симуляція
–
Точна формула
–

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

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

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

JavaScript
// Кімнати по 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)}%`);
Python
# Кімнати по 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}%")
Раунд 4 · П'ять пояснень

Чому так мало людей

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

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

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

Рахуємо пари

23 людини утворюють 253 пари

Ви проти всіх

Чому інтуїція бреше

Хтось із 22 інших народився у ваш день5,9%для 50% потрібно ще 253 людини, крім вас
Хоча б двоє з 23 мають спільний день50,7%для 50% досить 23 людей

Коли ми уявляємо задачу, ми підставляємо себе: «хто ще народився 14 березня?». Це інша, набагато рідкісніша подія. Ваш день перевіряється лише в 22 парах, а всього пар 253.

Реальний світ

Нерівномірні дні народження лише допомагають

Насправді народжуваність коливається: у деякі місяці дітей народжується більше, у свята менше. Будь-яка нерівномірність підвищує шанс збігу, бо люди частіше потрапляють в «популярні» дні. Рівномірний календар є найгіршим випадком, тож 23 є верхньою межею.

А серед 366 людей збіг гарантований на 100% (без 29 лютого). Це : якщо голубів більше, ніж кліток, хоча б двоє опиняться в одній.

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

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

Через протилежну подію

Рахуємо шанс, що збігу немає

Перша людина може народитися будь-коли. Друга має не влучити в її день: шанс 364/365. Третя має обійти вже два дні: 363/365. Кожен множник майже дорівнює 1, але їх перемножується багато. Після 23-ї людини добуток падає нижче 50%.

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

Точна формула і зручне наближення

Шанс, що в n людей усі дні народження різні: кожна наступна людина має уникнути вже зайнятих днів.

P(немає збігу)=365365·364365·363365·…·365−n+1365

Те саме коротше, через . Збіг є, коли не виконалося «всі різні».

P(збіг)=1−365!(365−n)!·365n

Зручне наближення. У показнику кількість пар, поділена на кількість днів.

P(збіг)≈1−e−n(n−1)/(2·365) n=23:1−e−253/365≈0,500

Скільки людей потрібно для шансу 50%, якщо «днів» D.

n50%≈1,1774·D D=365:1,1774·19,1≈22,5

Наближення пояснює все: показник степеня дорівнює кількості пар, поділеній на кількість днів. Тому потрібна кількість людей зростає як квадратний корінь із кількості днів. Для 365 днів це близько 23, а не 183.

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

Інші календарі, трійки і сусідні дні

Той самий принцип працює для будь-яких «днів»: місяців, PIN-кодів, хешів. І задачу можна ускладнити: шукати трьох людей з одним днем або двох, які народилися з різницею не більше ніж в один день.

Скільки потрібно людей для збігу з імовірністю 50%

Можливих значень
Потрібно людей (точно)
≈ 1,1774 · √D

Корінь замість половини

Обидві осі логарифмічні. Інтуїція чекає лінію «половина від D», а насправді потрібно ≈ √D. Для мільйона значень це 1 178 замість 500 000.

Ускладнені варіанти

Натисніть «Перевірити»: симуляція 10 000 кімнат покаже, що за вказаної кількості людей шанс справді близько 50%.

Що шукаємоЛюдей для 50%
Реальні дані

Ваш день народження в кімнатах відомих людей

П'ять справжніх «кімнат» зі справжніми датами народження. Оберіть свій день і пройдіть кімнатами: чи є там ваш двійник за днем народження і чи збіглися дні в когось між собою.

Перевірте на собі

спільний день у кімнаті ваш день

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

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

16 / 32

Чемпіонат світу 2014

У заявці кожної збірної на чемпіонат світу з футболу 2014 року було рівно 23 гравці. BBC перевірила дати народження: спільний день народження знайшовся в 16 командах з 32, тобто рівно в половині, як і передбачає формула.

2 листопада

Президенти США

Джеймс Полк і Воррен Гардінг народилися 2 листопада. А троє з перших п'яти президентів, Джон Адамс, Томас Джефферсон і Джеймс Монро, померли 4 липня, у День незалежності.

1 / 1461

29 лютого

Шанс народитися 29 лютого становить приблизно 1 до 1 461. Ми виключили цей день з моделі, але якщо його повернути, відповідь не зміниться: 23 людини все одно дають шанс трохи понад 50%.

Вересень

Дні народження нерівномірні

У багатьох країнах найбільше дітей народжується наприкінці літа й у вересні, а найменше на свята: 25 грудня та 1 січня. Пологи з плановою датою рідко призначають на святкові дні. Така нерівномірність лише підвищує шанс збігу.

2⁶⁴

Чому хеші такі довгі

Щоб знайти колізію 64-бітного хешу, потрібно не 2⁶⁴ спроб, а лише близько 2³², тобто приблизно 4,3 мільярда. Сучасний комп'ютер робить це за хвилини. Тому в криптографії використовують хеші довжиною 256 біт: для них колізія потребує 2¹²⁸ спроб, а це недосяжно.

253

Пар більше, ніж здається

У класі з 30 учнів 435 пар, а на весіллі на 100 гостей їх 4 950. Шанс, що на такому весіллі немає жодного спільного дня народження, приблизно 1 до 3 300 000.

Innumeracy

Джон Аллен Паулос

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

The Improbability Principle

Девід Генд

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

Surprises in Probability

Генк Теймс

2019, англійською

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

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

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

Рівень «Шкільна математика» відповідає задачі?

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

Розсилка

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

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

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