Birthday problem

Example

Assume that each person has a birthday on one of $365$ days, and that each day is equally likely. Assume also that the birthdays of different people are independent. Let $p(n)$ be the probability that among $n$ people, at least two have the same birthday. By the rule for the complement, for $1 \le n \le 365$, $$p(n) = 1 - \frac{365 \cdot 364 \cdots (365 - n + 1)}{365^n}.$$ Then $p(22) \approx 0.476$ and $p(23) \approx 0.507$. So $23$ people are enough for a probability above $1/2$.

Remarks

The answer is surprising because there are many pairs: $23$ people form $\binom{23}{2} = 253$ pairs. For $n$ much smaller than $365$, $p(n) \approx 1 - e^{-n(n-1)/730}$. For $n = 70$, $p(n) > 0.999$. For $n \ge 366$, $p(n) = 1$ by the pigeonhole principle.

Explanations

L1 human

It is easier to compute the chance that all birthdays are different. The second person must avoid $1$ day, the third person must avoid $2$ days, and so on. These small losses multiply quickly.