inverse birthday puzzle

[dennyrolling]

Most people know "birthday puzzle" (sometimes called "birthday paradox", I have no idea where "paradox" part came from): how big should be a group of people that there is 50% probability that at least two of them have the same birthday date (answer is 42 23). In my previous group people used to celebrate birthdays (with cake and candles and singing

Comments

[rezkiy]

== 50% chance that there is a day with no birthdays.

there are N people, there are M days of the year, there are M^N ways to distribute the birthdays. Now, let's pick a day and distribute the birthdays of these people among (M-1) days: you get exactly (M-1)^N ways to distribute them. Pick another day... so you got M*(M-1)^N ways... divide that by M^N.. you get

M-1
M*(---)^N == 0.5. Substitute M==365 (yes I know about leap years)
M

ln 365 + N ln (1-1/365) == ln 0.5

N ~= 365*(ln 730)

[rezkiy]

Если конечно же я нигде не облажался. Логарифмы натуральные.

[dennyrolling]

что-то многовато выходит, где-то в районе 60% вероятность для 2406 (если я правильно считаю на этот раз).

[rezkiy]

будем ждать Бобуха, он всех поправит.

[dennyrolling]

он придет и молча поправит все!

мне кажется я нашел ошибку - ты некоторые разбиения считаешь дважды (когда положим все дни рождения попались в один день ты посчитаешь это M раз, а надо только один).

[rezkiy]

я пока писал нижний коммент, ты лучше рассказал, что я натворил.

[dennyrolling]

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

[rezkiy]

Ну поправим решение тогда. Вот первый день года, вероятность что там нет ничьего ДР

M-1
(---)^N == Р
M

Для любого другого дня вероятность такая же.

Вот у нас 365 дней, какова вероятность что хоть раз за год произойдет событие, ежедневная вероятность которого Р? Такая же как один минус вероятность того, что событие с вероятность 1-Р произойдет 365 раз.

M-1
(1 - (---)^N)^M = 0.5
M

В общем с несколькими округлениями (тейлор два раза) у меня 2287. КОнсенсус.

[dennyrolling]

заскриню для интереса

[dennyrolling]

на самом деле с неправильными округлениями случайно получился правильный ответ :)

Правильное решение твоей формулы на W-A дает 2284

[rezkiy]

а как считаешь ты? Если монтекарлой то давай код.