How many people must be in a room before two of them probably share a birthday? Most people guess about 180. The answer is 23. The calculation uses the complement rule and the counting from probability with counting, and it shows why "at least one" questions are usually answered through their complement.
Key idea
If each of $n$ people independently gets one of $d$ equally likely values, then $$P(\text{all different}) = \frac{d}{d}\cdot\frac{d - 1}{d}\cdots\frac{d - n + 1}{d},$$ and $$P(\text{at least two match}) = 1 - P(\text{all different})$$
Why it works
There are $d^{n}$ equally likely lists of values. A list with all values different is built one person at a time: $d$ choices for the first, $d - 1$ for the second, and so on, so there are $d(d - 1)\cdots(d - n + 1)$ of them. Dividing gives the product above. "At least two match" covers many cases (one pair, two pairs, a triple, …), but its complement is a single clean case, so we compute the complement.
Why 23 is enough: matches can happen between any two people, and 23 people form $\binom{23}{2} = 253$ pairs. Each pair matches with chance $\frac{1}{365}$. Using $1 - \frac{i}{365} \approx e^{-i/365}$, the product is about $$e^{-(0 + 1 + \cdots + 22)/365} = e^{-253/365} \approx 0.50$$
Why 23 is enough: matches can happen between any two people, and 23 people form $\binom{23}{2} = 253$ pairs. Each pair matches with chance $\frac{1}{365}$. Using $1 - \frac{i}{365} \approx e^{-i/365}$, the product is about $$e^{-(0 + 1 + \cdots + 22)/365} = e^{-253/365} \approx 0.50$$
| People $n$ | 5 | 10 | 20 | 23 | 30 | 40 | 50 | 57 |
|---|---|---|---|---|---|---|---|---|
| $P(\text{a shared birthday})$ | 0.027 | 0.117 | 0.411 | 0.507 | 0.706 | 0.891 | 0.970 | 0.990 |
Worked examples
Worked example: Birth months
Four people each have a birth month, all 12 equally likely and independent. Find the probability that at least two share a month.
- All different: $$\frac{12}{12} \cdot \frac{11}{12} \cdot \frac{10}{12} \cdot \frac{9}{12} = \frac{11880}{20736} = \frac{55}{96}$$
- At least two match: $1 - \frac{55}{96} = \frac{41}{96} \approx 0.427$.
Answer: $\frac{41}{96}$
Worked example: Matching you, or matching anyone
You are in a room with 22 other people. Compare the chance that someone shares your birthday with the chance that some two people share a birthday.
- Someone matches you: each of the 22 misses your birthday with probability $\frac{364}{365}$, independently, so $1 - \left(\frac{364}{365}\right)^{22} \approx 0.059$.
- Any match among the 23 people: from the table, about $0.507$.
- The second is much larger because it counts all 253 pairs, not only the 22 pairs that include you.
Answer: About $0.059$ against about $0.507$.
Worked example: How many people for a digit match?
People each pick a random digit from 0 to 9. What is the smallest group in which a repeated digit is more likely than not?
- $n = 4$: all different with probability $\frac{10 \cdot 9 \cdot 8 \cdot 7}{10^{4}} = 0.504$, so a match has chance $0.496$.
- $n = 5$: all different with probability $0.504 \cdot \frac{6}{10} = 0.3024$, so a match has chance $0.6976$.
Answer: 5 people.
Common mistake
Two shortcuts give badly wrong answers. Multiplying $\frac{1}{365}$ by the number of people ($\frac{23}{365} \approx 0.06$) treats the matches as if they could not overlap and grows past 1 for large groups. Comparing everyone with one chosen person misses most of the pairs. Check: a correct method gives a probability that rises toward 1 but never passes it.