Задача о днях рождения

С какой вероятностью ни у кого из пассажиров день рождения не совпадает с днем рождения Петра?

Поскольку Петр Иванов ничего не знает про дни рождения пассажиров и в условии задачи ничего дополнительно про это не сообщено, то нужно считать, что дни рождения распределены равномерно по всему году: наугад выбранный пассажир с одинаковой вероятностью 1/365 может родиться в любой из 365 дней года (пока не берем в расчет високосные годы). Поэтому вероятность того, что дни рождения Петра и каждого отдельно взятого пассажира не совпадают, равна 364/365 (это примерно 0,9972602...). Значит, день рождения Петра не совпадает с днями рождений всех двухсот пассажиров с вероятностью (364/365)²⁰⁰, то есть примерно 0,5777....

Чтобы найти вероятность совпадения дня рождения хотя бы с одним из пассажиров, теперь надо вычесть полученное число из 1 (потому что, очевидно, события совпадения хотя бы с кем-то и несовпадения ни с кем дополняют друг друга). В результате получается вероятность ≈ 0,4223..., что, конечно, меньше, чем 1/2.

Что поменяется, если вспомнить про високосные годы? Будем считать, что 29 февраля бывает раз в 4 года (на самом деле в общепринятом сейчас григорианском календаре всё немного хитрее, об этом чуть ниже). Тогда для правильного учета этой даты нужно взять ее с весом 1/4 — потому что она встречается в 4 раза реже других дат. То есть вероятность несовпадения дней рождения Петра и случайно выбранного пассажира равняется 364,25/365,25 ≈ 0,9972621.... Отличие от первого результата только в шестом знаке после запятой. Это позволяет надеяться, что аккуратный учет «високосности» не влияет на вывод (и так и есть на самом деле — можете убедиться, проделав соответствующие вычисления).

Если быть совсем точным, то 29 февраля надо учитывать с весом 1/4 − 1/100 + 1/400 = 0,2425, потому что полностью правило учета високосных лет звучит так:

• год, номер которого делится на 400, — високосный;
• год, номер которого делится на 100, но не делится на 400, — не високосный;
• остальные годы, номера которых делятся на 4, — високосные.

Из решения видно, что двухсот пассажиров не хватает для того, чтобы вероятность совпадения дня рождения хотя бы с одним из них была больше 1/2. Это может показаться странным, потому что 200 уже ощутимо больше половины числа дней в году, а этого количества все равно не хватает. Посчитаем, скольких пассажиров хватило бы. Если искомое число пассажиров обозначить за N, то должно выполняться неравенство 1 − (364/365)^N ≥ 1/2, причем N должно быть наименьшим натуральным числом, удовлетворяющим этому неравенству. Получаем (364/365)^N ≤ 1/2, что после логарифмирования дает

Итого, N = 253 — таково должно быть наименьшее число случайно взятых людей, чтобы с вероятностью не меньше 1/2 среди них нашелся хотя бы один, родившийся в тот же день, что и Петр (или кто-нибудь другой, например, вы).

У рассмотренной задачи есть известная «парная» задача. Она тоже формулируется как вопрос про совпадение дней рождения: при каком наименьшем числе пассажиров на теплоходе вероятность того, что хотя бы два из них родились в один день, будет не меньше 1/2? Вроде, похожий вопрос. А вот ответ на него совсем другой — неожиданно маленький по сравнению с найденным выше числом 253. Забегая вперед, скажем, что это число хорошо подходит на роль числа учеников в обычном школьном классе, поэтому чаще в вопросе фигурируют не пассажиры теплохода, а ученики одного класса. Суть задачи от этого, впрочем, не меняется.

Итак, найдем ответ и на второй вопрос. Сразу оговоримся, что для простоты не будем принимать в расчет 29 февраля (то есть считаем, что никто из пассажиров не родился в этот день, — как мы уже видели выше, если учитывать этот день, то на ответ это, скорее всего, не повлияет). Пусть пассажиров было M. Найдем сначала вероятность того, что у них все дни рождения разные.

Для этого надо взять число наборов из M различных дат и разделить его на число наборов из M любых дат. Всего дней в году 365, поэтому второе число равно 365^M (если даты могут повторяться, то у первого пассажира 365 вариантов дня рождения, у второго тоже 365, у третьего тоже 365, и т. д.). Если даты должны быть разными, то у первого пассажира будет по-прежнему 365 вариантов дня рождения, а у второго будет уже 364 варианта, у третьего — 363 варианта, и т. д. У последнего пассажира, M-го по счету, будет (365 − M + 1) вариант для дня рождения. Поэтому число наборов из различных дат равно 365·364·363·...·(365 − M + 1). А искомая вероятность того, что все дни рождения разные, равна

Это выражение можно переписать в более коротком и удобном виде

Отсюда вероятность, про которую спрашивалось в вопросе, то есть вероятность того, что хотя бы у двоих дни рождения совпадут, равна

Она должна быть не меньше 1/2, что дает

Найти M из этого неравенства можно подбором, если под рукой есть достаточно мощный калькулятор вроде Wolfram|Alpha. Например, подстановка M = 50 дает значение 0,029..., что очень мало, а подстановка M = 10 дает 0,883..., что много. Это позволяет надеяться, что искомое M лежит где-то между 10 и 50. После нескольких попыток можно определить, что M = 23.

Если знать основы математического анализа, то можно обойтись без подбора, получив более «чистое» решение этой задачи. Подробности описаны, например, здесь.

У двух этих задач сложность «лобовых» решений довольно сильно отличается, хотя, казалось бы, вопросы очень похожи. Но оказывается, что эту похожесть можно использовать и получить ответ на второй вопрос, зная ответ на первый. Заметим, что на самом деле оба вопроса — это вопросы про совпадения дней рождения среди некоторых множеств пар людей. В первом случае это были пары вида «Петр Иванов и пассажир», во втором — пары вида «пассажир и пассажир». Поэтому, если подобрать такое M, что пар пассажиров будет 253 или больше, то и вероятность совпадения дней рождения хотя бы у двух из них точно будет не меньше 1/2.

Если пассажиров M, то пар будет M·(M − 1)/2. Уравнение M·(M − 1)/2 = 253 как раз имеет целочисленное решение 23 (второе решение этого уравнения, −22, не подходит по смыслу). Результат ожидаемо совпал!

А что же для других значений вероятности? Например, сколько должно быть пассажиров на теплоходе, чтобы общий день рождения нашелся с вероятностью 70%? Ответ — 30 пассажиров. Если пассажиров будет 50, то вероятность совпадения составит уже 97%, а если их будет 100, то вероятность составит 99,99996%. Это уже очень близко к 100%, но эта величина будет достигнута только если пассажиров будет 366 или больше — только при таких условиях совпадение будет гарантировано (это следует из принципа Дирихле).

В заключение отметим, что второй вопрос иногда называют «парадоксом дней рождения» как раз за то, что небольшой (по сравнению с числом дней в году) ответ противоречит интуитивному ожиданию. Любопытно, что в криптографии есть понятие «атака «дней рождения», в которой используется как раз то, что при некоторых условиях вероятность появления в серии испытаний нужного результата очень быстро растет при небольшой длине серии. У нас эти испытания — проверка совпадения дня рождения у пары пассажиров, а в криптографии это применяется для компрометации хеш-функций.