Парадокс дней рождения: почему в классе наверняка есть двое, родившихся в один день

Зайди завтра в свой класс, где человек тридцать, и поспорь на шоколадку: «У двоих из вас день рождения в один и тот же день». Все засмеются — в году же 365 дней, а вас всего тридцать, какой тут шанс? И отдадут шоколадку примерно в 7 случаях из 10. Не потому что тебе везёт, а потому что математика заранее на твоей стороне. Сейчас покажу, где именно прячется обман.

Где интуиция нас обманывает

Когда ты слышишь «совпадение дней рождения», мозг автоматически примеряет это на себя: «Какой шанс, что кто-то родился именно в мой день?» И вот тут интуиция права — этот шанс реально маленький. Чтобы хотя бы с вероятностью 50% встретить «двойника» именно по своей дате, нужно собрать около 253 человек. Целую школу.

Но в споре-то условие другое! Нам не важно, совпадёт ли кто-то с тобой. Нам подойдёт любая пара: Маша с Петей, Дима с Олей, кто угодно с кем угодно. А таких пар в классе оказывается неожиданно много.

В классе из 30 человек число возможных пар считается так: «30 умножить на 29 и поделить на 2», то есть 435 пар. Четыреста тридцать пять шансов на совпадение вместо одного! Вот где пряталась ошибка: мы по привычке считали себя, а считать надо было пары. Это как лотерея — если у тебя один билет, шанс выиграть крошечный, но если по классу разлетелось 435 билетов, кто-нибудь да сорвёт куш.

Хитрость: считаем наоборот

Считать «вероятность, что хоть где-то совпало» в лоб — кошмар: совпасть может одна пара, две, три, сразу несколько. Все эти варианты пришлось бы складывать и аккуратно вычитать пересечения. Поэтому математики делают красивый финт — считают противоположное событие: вероятность, что не совпало вообще ни у кого. А потом вычитают её из единицы.

Представь, что люди заходят в класс по одному и называют свой день рождения:

• Первый может родиться в любой день — ему «свободны» все 365 дней из 365.
• Второму, чтобы не совпасть с первым, остаётся 364 дня из 365.
• Третьему — 363 из 365 (два дня уже заняты).
• И так далее: каждому следующему остаётся всё меньше «свободных» дат.

Перемножаем все эти дроби — получаем вероятность, что совпадений нет совсем:

P(нет совпадений) = 365/365 · 364/365 · 363/365 · ... · 336/365

Последняя дробь — 336/365: это тридцатому человеку остаётся 336 свободных дней (365 минус 29 уже занятых). Для 30 человек всё произведение даёт примерно 0,294. Значит, вероятность, что совпадение есть, равна 1 − 0,294 ≈ 0,706. Те самые 70%.

Как быстро растёт вероятность

Самое неожиданное — насколько круто кривая взлетает вверх. Достаточно совсем небольшой компании, чтобы шансы стали серьёзными:

• 10 человек — около 12%;
• 23 человека — уже 50,7%, то есть выгоднее ставить на совпадение, чем против;
• 30 человек — около 71%;
• 50 человек — целых 97%;
• 70 человек — 99,9%, практически гарантия.

Запомни число 23 — это волшебный порог, где шанс перепрыгивает за половину. Всего двадцать три человека, а кажется, что для такого нужна толпа. Именно поэтому это называют парадоксом: ответ верный, но в голове не укладывается.

Проверим питоном

Если не веришь дробям — пусть посчитает компьютер. Вот маленький скрипт, который перемножает те самые «свободные дни» и выдаёт вероятность совпадения:

def birthday_prob(n):
    no_match = 1.0
    for i in range(n):
        no_match *= (365 - i) / 365
    return 1 - no_match

for n in [10, 23, 30, 50, 70]:
    print(n, "человек:", round(birthday_prob(n) * 100, 1), "%")

Запусти — и увидишь ровно те проценты, что выше. Можешь пойти дальше: смоделируй 100 000 случайных классов через random, посчитай, в скольких реально нашлось совпадение, и сравни с формулой. Цифры сойдутся — теория и эксперимент пожмут друг другу руки.

При чём тут хеши и программирование

А теперь самое крутое — это не просто фокус для спора. Тот же эффект больно бьёт по программистам, и называется он атака дней рождения (birthday attack).

Когда программа хочет дать большому файлу короткий «отпечаток», она прогоняет его через хеш-функцию — получается строка фиксированной длины. Разные файлы должны давать разные отпечатки. Но «дней» (возможных хешей) хоть и астрономически много, всё же конечное число. А значит, рано или поздно два разных файла дадут одинаковый хеш. Это и есть коллизия — ровно как совпадение дней рождения, только «календарь» тут чудовищно огромный.

И вот ключевой вывод из парадокса: чтобы наткнуться на коллизию, нужно перебрать не все варианты, а лишь примерно квадратный корень от их числа. Если у хеша N возможных значений, коллизия всплывёт уже около √N попыток. Сравни: чтобы угадать твой конкретный день рождения, нужны сотни людей, а чтобы нашлась хоть какая-то совпадающая пара — всего двадцать три. Хешам достаётся та же «скидка». Поэтому, например, у 256-битного хеша реальная стойкость к коллизиям — около 128 бит, то есть вдвое меньше, чем кажется по длине. Это напрямую влияет на то, насколько надёжны цифровые подписи и блокчейн, на котором держится, скажем, биткоин.

Что с этим делать

Парадокс дней рождения — отличная прививка от доверия к «очевидному». Наша интуиция считает «совпадение со мной», а реальность работает на парах — и их растёт квадратично много. Завтра можешь проверить теорию вживую на классе (шоколадка ждёт), а сегодня — запусти питон-скрипт и поиграй с числами. А когда дорастёшь до криптографии, вспомни: те же 23 человека объясняют, почему хеши приходится делать такими длинными.