Interview war story: the birthday paradox

The question: How many people in a room for a 50% chance of two sharing a birthday?

The candidate — strong resume, MIT math — answered 183. Half of 365.

Wrong. The answer is 23.

What went wrong

The candidate thought linearly: "1/2 chance of a match → half the days → 183." But matches are about pairs, not days. With 23 people there are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ pairs, each with $1/365$ chance of matching. $253/365\approx 0.69\approx \ln 2$ — the threshold.

The lesson

The birthday paradox is the canonical example of "intuition fails on combinatorial problems." Whenever you see "how many X until Y", ask:

1. Is the growth linear, quadratic, exponential?
2. Are you counting items, pairs, triples, subsets?
3. Is there an approximation (Poisson, CLT, union bound)?

For interviews: when in doubt, write out small cases. With $n=1,2,3$ people, the answer is obviously 0, 0, ~0.008. Not 183.

What the candidate should have said

"Let me think about pairs. With $n$ people, $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. Each pair shares a birthday with prob $1/365$. Approximate as Poisson with mean $\left(\genfrac{}{}{0ex}{}{n}{2}\right)/365$. Set $1-e^{-\left(\genfrac{}{}{0ex}{}{n}{2}\right)/365}=1/2$: $\left(\genfrac{}{}{0ex}{}{n}{2}\right)/365=\ln 2$, so $n(n-1)/2\approx 253$, $n\approx 23$."

That's 30 seconds of thinking. Worth $200k+. Don't waste it.