Originally Posted by

**takatok** Well I realize its probably too late for your deadline but here you go:

P(12,k) is a permutation (Note: its a different than a combination):

$\displaystyle P(n,k) = \frac{n!}{(n-k)!}$

so your equation is

$\displaystyle 1 - \frac{\frac{12!}{(12-k)!}}{12^k} >= 0.5$

$\displaystyle 12^k- \frac{12!}{(12-k)!}>=12^k*0.5$

This is gonna be a pain to solve for and one method is to just plug in values of k, starting at 2 and going on up. You don't have to try that many since, 13 people are guaranteed to have the same birthday.

There are a lot of ways to approximate this ,and the easiest is this:

There are $\displaystyle \frac{k*(k-1)}{2}$ ways we can pair everyone up. If we assume each pair is independent of each other, we can find the probability that all the pairs don't have the same month for a birthday.

The odds of any pair not having the same birthday is 11/12, and the probability that None of them have the same birthday is:

$\displaystyle P(None) = (\frac{11}{12})^{\frac{k*(k-1)}{2}}=.5$

This is a little easier to solve: Take the $\displaystyle log_{\frac{11}{12}}$ of both sides:

$\displaystyle \frac{k*(k+1)}{2} = log_{\frac{11}{12}}0.5$

Now convert the right side to $\displaystyle log_{10}$

$\displaystyle \frac{k*(k+1)}{2} = \frac{log_{10} 0.5}{log_{10}\frac{11}{12}}$

$\displaystyle k^2-k = 15.932$

Then using quadratic method you can solve:

$\displaystyle k^2-k-15.932=0$

Note this will come out to roughly k=4.5. So we know we need 5 people.

If you plug in 5 people (10 combinations = 5*4/2)

$\displaystyle (\frac{11}{12})^{10} = .419 $

So 1-.419 = 58.1%.

The actual probablity with 5 people is:

$\displaystyle 1-\frac{\frac{12!}{(12-5)!}}{12^5} = 61.8% $

I believe this is because the approximate method isn't counting all the times when more than 2 people have the same month birthday. But its a pretty low % difference. As long as k is not near an integer ( e.g k=4.4) you can be pretty safe in assuming your actual k you need is k rounded up, in this case 5. But if is very a near an integer.. say k=4.01 or k=4.98 you might need to check both number near k.. in the first case k =4 and k=5.. In the second case k =5 and 6.