Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
add comment

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.

share|improve this answer
add comment

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)

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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