inverse birthday puzzle (solution)
First things first. I really enjoyed all solutions people posted (including anonymous critique), and I really liked an approximate one (by rezkiy) which I haven't came up with myself. With high probability correct answer is 2287
Quick recap:
rezkiy and rsokolov both found an approximation.
kuzmen found complicated recurrent formula, which was apparently correct, but not particularly ACM-ICPC-worthy.
raindog_2 found both approximation and exact solution.
_m_e_solved the problem twice with the same (correct) result.
Here is my solution.
Let's have N as a number of days and M as a number of distinct people. It is very simple to count the number of all possible ways M people can be born in N days, (more or less obvious) NM. Let's now count all the ways we can distribute birthdays in such a way that no empty days are left. Hmmmmm.
Turns out there is wide known sequence for distributing n objects into k groups, so called Stirling numbers of the second kind, let's denote them S(n, k).
The groups easily correspond to days and our objects are birthdays, so S(M, N) is total number of the ways birthdays can be distributed into (undistinguished) days. Now, the days can be shuffled around in N! ways to generate all possible situations with no day without the birthday.
So, generic answer for probability is:
PN(M)=
S(M, N) * N!
NM
Unfortunately WolframAlpha didn't want to count Stirling numbers for large arguments in the original problem, so I decided to code a little program (using BigInteger, no less) which used binary search to find whereabouts of the place where probability crosses 1/2 (obviously the function is always increasing, so I only needed to spot the location where it crossed the line). Here's the output:
Found approximate location
M=2281, P=0.494618882351313
M=2282, P=0.495579555664064
M=2283, P=0.496539425608168
M=2284, P=0.497498487775709
M=2285, P=0.498456737785259
M=2286, P=0.499414171281851
M=2287, P=0.500370783936946
M=2288, P=0.501326571448405
M=2289, P=0.502281529540454
M=2290, P=0.503235653963656
Took 6.288 seconds
Incidentally those probabilities are very close to the ones raindog_2 found with a recurrent formula.
Quick recap:
rezkiy and rsokolov both found an approximation.
kuzmen found complicated recurrent formula, which was apparently correct, but not particularly ACM-ICPC-worthy.
raindog_2 found both approximation and exact solution.
_m_e_solved the problem twice with the same (correct) result.
Here is my solution.
Let's have N as a number of days and M as a number of distinct people. It is very simple to count the number of all possible ways M people can be born in N days, (more or less obvious) NM. Let's now count all the ways we can distribute birthdays in such a way that no empty days are left. Hmmmmm.
Turns out there is wide known sequence for distributing n objects into k groups, so called Stirling numbers of the second kind, let's denote them S(n, k).
The groups easily correspond to days and our objects are birthdays, so S(M, N) is total number of the ways birthdays can be distributed into (undistinguished) days. Now, the days can be shuffled around in N! ways to generate all possible situations with no day without the birthday.
So, generic answer for probability is:
PN(M)=
S(M, N) * N!
NM
Unfortunately WolframAlpha didn't want to count Stirling numbers for large arguments in the original problem, so I decided to code a little program (using BigInteger, no less) which used binary search to find whereabouts of the place where probability crosses 1/2 (obviously the function is always increasing, so I only needed to spot the location where it crossed the line). Here's the output:
Found approximate location
M=2281, P=0.494618882351313
M=2282, P=0.495579555664064
M=2283, P=0.496539425608168
M=2284, P=0.497498487775709
M=2285, P=0.498456737785259
M=2286, P=0.499414171281851
M=2287, P=0.500370783936946
M=2288, P=0.501326571448405
M=2289, P=0.502281529540454
M=2290, P=0.503235653963656
Took 6.288 seconds
Incidentally those probabilities are very close to the ones raindog_2 found with a recurrent formula.