The Shared Birthday
The puzzle
People walk into a room one at a time. Birthdays are spread evenly across 365 days and nobody is a twin.
How many people are needed before it is more likely than not that two of them share a birthday?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Work out the probability that everybody is different, and subtract.
Hint 2
With n people there are n(n-1)/2 pairs. That number grows much faster than n.
Show the answer Hide the answer
Twenty-three. At 23 people the chance of a shared birthday is just over one half; at 22 it is just under.
How to get there
Count the opposite. The second person must miss the first: 364/365. The third must miss both: 363/365. Multiply those fractions together for n people.
At n = 22 the product is 0.524, so a collision has probability 0.476. At n = 23 the product drops to 0.493, so a collision has probability 0.507. Twenty three is the first n over one half.
It feels wrong because people count themselves against 364 others. The right count is pairs: 23 people make 253 pairs, and each pair is a chance to collide.
The technique worth keeping
When something must not happen to any pair, count the pairs. n(n-1)/2 grows quadratically, which is why collisions arrive far earlier than intuition expects - the same arithmetic is why short hash values collide.