The Shared Birthday

  • Medium
  • Probability puzzles
  • Tests: Counting pairs rather than people

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.