23 People Make a Shared Birthday a Coin Flip, and 253 Pairs Explain It

Put people in a room one at a time and stop when two of them share a birthday. How many do you need before that is more likely than not?

The number almost everyone reaches for is somewhere near 180, on the reasoning that there are 365 days and you want to cover half of them. The answer is 23. Not 23 as a curiosity: 23 people give a shared birthday probability of $0.5073$, and 22 people give $0.4757$, so 23 is exactly where the bet turns.

You are counting pairs, and pairs grow fast

The reflex answer counts people. The question counts pairs of people, because a match needs two of them, and the number of pairs grows like the square of the headcount.

Two hundred and fifty three separate chances to collide, in a room of 23. Against 365 days that no longer sounds like a long shot, and it is not.

The exact number, with no approximation

Work with the complement, which is the only sane way in. Line the people up and demand that each new birthday miss all the earlier ones. The second person has 364 days available out of 365, the third has 363, and so on:

At $k = 23$ that product is $0.4927$, so a match has probability $0.5073$. Push on and the curve gets steep fast: 57 people reach $99\%$, and by 70 the chance of everyone being distinct is under one in a thousand.

For a number you can produce without a calculator, take logs and use $\ln(1-x) \approx -x$:

At $k = 23$ the exponent is $-506/730 = -0.693$, which is $-\ln 2$ to three decimals, so the estimate lands on $1/2$ on the nose. That is the version to say out loud in an interview, because it shows where the half comes from instead of quoting it.

The threshold sits at the square root

Setting the exponent to $-\ln 2$ and solving for $k$ generalises the whole thing. With $n$ equally likely slots rather than 365:

which gives $22.49$ for $n = 365$, rounding up to the 23 the exact product produced. The useful part is the shape, not the constant. Half a set is never the threshold. The square root of it is.

Matching me is a different question, and it needs 253 people

Ask instead how many people you need before someone shares your birthday. Now you are the fixed point, and only the 22 chords touching you in the figure count. Each person misses you with probability $364/365$:

so 253 people. Eleven times the crowd, for a question that sounds like the same one.

The 253 turning up twice is not a coincidence, and spotting why is the mark of someone who understood rather than memorised. Both questions ask for the expected number of favourable pairs to reach $\ln 2$. For the open question that expectation is $\binom{k}{2}/365$, which needs $\binom{k}{2} = 253$ pairs. For the question about you it is $k/365$, which needs $k = 365 \ln 2 = 253$ people. The same 253 appears once as a count of pairs and once as a count of people, and the factor of eleven between the answers is the distance between those two sentences.

Where this stops being a party trick

The square root shows up wherever identifiers are handed out at random and assumed unique. With $N$ possible values and $k$ draws, the chance of a repeat is about $k^2/2N$, so trouble starts near $\sqrt{N}$ and not near $N$.

A 64-bit random order ID has $1.8 \times 10^{19}$ values, which sounds untouchable, and reaches an even chance of a duplicate at $5.1 \times 10^{9}$ ids. A busy venue can print five billion ids in a few years. A random UUID carries 122 random bits and holds out to $2.7 \times 10^{18}$, which is why it is the safe choice and the 64-bit shortcut is not.

The same halving is why a hash with a $b$-bit output only offers $b/2$ bits of collision resistance. A 128-bit digest falls to a birthday attack at around $2^{64}$ work, which is the reason 128-bit hashes stopped being acceptable for signatures while 128-bit keys stayed fine. The room with 23 people in it is the same calculation, wearing a hat.