In a room filled with different dates, a single match is enough. The question is how many people are needed before a match becomes more likely than no match at all.
The Shared Birthday
Riddle statement
There are \(n\) people in a room.
Assume that:
- each birthday is equally likely to fall on any of the 365 days of the year;
- different people's birthdays are independent;
- leap years are ignored.
What is the smallest value of \(n\) for which the probability that at least two people share a birthday is greater than 50%?
Show solution
Solution
Answer: exactly 23 people are required.
The cleanest approach is to calculate the complementary probability first.
1. The complementary event
Let \(D_n\) be the event:
All \(n\) people have different birthdays.
The event we want — at least two people sharing a birthday — is the complement of \(D_n\). Therefore:
2. Probability that all birthdays are different
The first person's birthday may fall on any day:
For the second person not to match, their birthday must fall on one of the other 364 days:
If the first two birthdays are different, the third person must avoid both of them:
Continuing in the same way, for \(n\le365\):
Equivalently:
Hence:
3. The case of 22 people
For \(n=22\):
Therefore:
This is approximately 47.57%, still below 50%.
4. The case of 23 people
For \(n=23\):
Therefore:
This is approximately 50.73%, now above 50%.
5. Why 23 is the minimum
It is not enough to show that 23 works; we must also show that no smaller number works.
When one more person is added, the probability that all birthdays remain different is multiplied by:
which is less than 1.
Thus \(\Pr(D_n)\) decreases as \(n\) increases, while its complement:
increases.
Since the probability is still below 50% for 22 people but exceeds 50% for 23, the first value to cross the threshold is:
Key idea: directly counting every possible birthday match is awkward because matches can overlap. The complementary event — everyone having a different birthday — is captured by a single product.