Спросите 23 незнакомцев — и шанс, что у двоих из них день рождения в один и тот же день, равен 0.50729723432399; калькулятор приходит к этому как 1 − permutations(365,23)/365²³, где числитель считает число способов, при которых все 23 дня рождения оказываются разными. Половина превышена на волос, поэтому результат до сих пор звучит как парадокс. Пятьдесят семь человек загоняют его выше 0.99.
Противоречие интуиции берётся из того, что считают людей, а не сравнения: 23 человека образуют combinations(23,2) = 253 пары, и именно 253 шанса примерно по 1/365 каждый переступают половину, а не 23. Та же арифметика объясняет, почему коллизии хешей наступают гораздо раньше, чем позволяет предполагать размер таблицы: квадратный корень из пространства — точка, в которой начинаются неприятности, поэтому 128-битные хеши считаются дающими около 64 бит стойкости к коллизиям.
Ответ
0.50729723432399
Как его читать
1 − permutations(365,23)/365²³ на калькуляторе. Вторая ссылка даёт дополнение 0.49270276567601; оба значения с плавающей запятой, так что последние знаки — округление, а не арифметика.
Источник
The birthday problem, popularised by Richard von Mises in 1939; the 365-day uniform model ignores leap days and the real seasonality of births
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.