| вопрос | сколько человек нужно, чтобы P(совпадение) > 50%? |
| ответ | 23 → P ≈ 50.7% |
| при 30 | P ≈ 70.6% |
| при 57 | P ≈ 99% |
| формула | P(нет совпадений) = ∏k=0..n−1 (365−k)/365 |
| связано | комбинаторика · ! · вероятность · криптография |
Двадцать три незнакомца.
в комнате 23 человека. вероятность, что двое родились в один день — больше 50%. большинство не верит. пока не считает.
Спросите людей: сколько человек нужно собрать в комнате, чтобы с вероятностью 50% двое из них оказались ровесниками по дате? Большинство называет числа около 180 — половина от 365. Логика простая: 365 дней, нужна «половина». Правильный ответ — 23.
Считаем вероятность того, что совпадений нет вовсе. Первый человек: его день рождения — любой из 365, вероятность 365/365 = 1. Второй: любой день, кроме дня первого, 364/365. Третий: любой, кроме двух уже занятых, 363/365. И так далее. Для группы из n человек: P(нет совпадений) = (365 · 364 · 363 · … · (365 − n + 1)) / 365n.
При n = 23 это произведение даёт примерно 0.493. Значит P(хоть одно совпадение) ≈ 0.507 — больше половины1.
23 человека, 253 пары, больше шансов, чем кажется.
Почему так мало? Потому что мы считаем не людей, а пары. 23 человека — это C(23, 2) = 23·22/2 = 253 пары. Каждая пара совпадает с вероятностью 1/365 ≈ 0.0027. Ожидаемое число совпадений ≈ 253 · (1/365) ≈ 0.69. Уже близко к единице — и P(хотя бы одно совпадение) поднимается выше 50%.
Дальше всё ускоряется. При n = 30 вероятность совпадения ≈ 70.6%. При n = 50 ≈ 97%. При n = 57 ≈ 99%. При n = 70 ≈ 99.9%. При n = 100 ≈ 99.99997%. К сотне человек совпадение практически неизбежно.
Парадокс дней рождения важен в криптографии — конкретно в анализе хэш-функций2. Атака «дня рождения»: чтобы найти коллизию хэш-функции с выходом N бит, нужно не 2N попыток, а только 2N/2. Отсюда практическое требование к длине хэша: SHA-256 стоек к коллизиям именно потому, что √(2256) = 2128 — это всё ещё астрономическое число, требующее ресурсов больше, чем существует в обозримой вселенной. Но если бы хэш был длиной всего 64 бита — атака требовала бы 232 ≈ 4 миллиарда вычислений, что современный кластер делает за часы.
Парадокс дней рождения — не интуитивная неожиданность, а пример того, насколько плохо человеческий мозг считает комбинаторику. Мы интуитивно думаем линейно: «один шанс на 365» масштабируем как «n шансов на 365». На деле растут пары, а число пар растёт квадратично. Из этого квадратичного роста и появляется неожиданно низкий порог 233.