# Birthday problem. What am I doing wrong here?

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$

## 2 Answers

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

$$\prod_{k=1}^n\left(1-\frac{k}{365}\right)\geq\frac{1}{2}$$

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

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