Birthday problem: What is the minimum number of people in a room such that at least two people have the same birthday has a probablity $\geq 0.5$ ( http://en.wikipedia.org/wiki/Birthday_problem )

I am trying to solve this by considering each day separately and then adding up the probabilities. This is equivalent to (birthday collision on a particular day) $\cdot \, 365$. I understand that I am doing something wrong as the probability goes more than $1$ after a few iterations. Can you please help me with identifying my mistake. Thanks in advance

$2$ persons: $A$ and $B$ $= 1/365 ( \text{prob of $A$ being born on day 1} ) \cdot 1/365 ( \text{prob of $B$ being born on day 1} ) + 1/365 ( \text{prob of $A$ being born on day 2}) \cdot 1/365 ( \text{prob of $B$ being born on day 2} ) + \dots = \frac{1}{(365 \cdot 365)} ( \text{probability on each day} ) \cdot 365 = 1/365$

$3$ persons: $A$, $B$ and $C$ $AB$ born on day 1 : $\frac{1}{(365 \cdot 365 )}$ $BC$ born on day 1 : $\frac{1}{(365 \cdot 365 )}$ $CA$ born on day 1 : $\frac{1}{(365 \cdot 365 )}$ for day 1 = $\frac{3}{(365\cdot 365)}$ for day 1 = number of pairs$/(365\cdot 365) = 3c2/(365\cdot 365)$ for all days $= 365 \cdot 3c2 / ( 365 \cdot 365 )$ $= 3c2 / 365$

4 persons: $= 4c2 / 365$


You are counting some cases more than once. Example :

For three persons, $A,B,C$ and for January 1st you have:

$A,B$ born on 1.1: $\frac{1}{365^2}$

$B,C$ born on 1.1: $\frac{1}{365^2}$

$A,C$ born on 1.1: $\frac{1}{365^2}$

Which are all true, but you counted the case that $A,B,C$ were all born on 1.1 three times.

This is called the inclusion-exclusion principle, and can indeed be employed to solve the birthday problem.

However, there is a much simpler solution if you consider the probability that all birthdays are on distinct days and take its complement.


The solution is something like 22 or 23 people, I can't remember right now.

You must calculate for what $\,n\,$ you get


Well, now just solve the above...(there's a way to simplify it using the binomial coefficient)

  • $\begingroup$ The answer is 23, but your expression doesn't seem right... (being always $0$ for $0<n<356$) $\endgroup$ – Alfonso Fernandez Dec 28 '12 at 11:35
  • $\begingroup$ Yes, it was clearly a finger mistake when typing. Don't you think you rush a little too much to downvote? $\endgroup$ – DonAntonio Dec 28 '12 at 11:48
  • $\begingroup$ I didn't downvote, just pointed it out so that you can correct it. Someone else may have. $\endgroup$ – Alfonso Fernandez Dec 28 '12 at 11:51
  • $\begingroup$ Ok, thanks for the comment. $\endgroup$ – DonAntonio Dec 28 '12 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.