How many people before two share a birthday?
The birthday paradox: how many people must be in a room before it is more likely than not that two share a birthday? Intuition says well over a hundred. The answer is 23, and the reason it is so small is the same reason hash tables collide sooner than you expect.
People walk into a room one at a time. Assume birthdays are equally likely on each of 365 days, ignore leap years, and assume no twins or other correlations.
How many people must be in the room before the probability that at least two of them share a birthday exceeds one half?
Most people guess somewhere between 100 and 183, reasoning that you need a good fraction of the year covered. That reasoning answers a different question: how many people before someone shares your birthday. The puzzle asks about any pair, and the number of pairs grows much faster than the number of people. Before the hints, count the pairs among 23 people and see whether the true answer still seems absurd.
This is a favourite quant and systems interview question because the second half, "why does this matter for computers", separates people who memorised 23 from people who understood it.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
Compute the complement: the probability that all n birthdays are different. The first person is free; the second must avoid one day; the third must avoid two; and so on.
Hint 2 the key move
The all-distinct probability is the product of (365 minus i) over 365 for i from 0 to n minus 1. Multiply it out, or estimate it, until it drops below one half.
Hint 3 the estimate
Each factor is about e to the power (minus i over 365), so the product is about e to the power (minus n squared over 730). Set that equal to one half and solve for n.
The solution
Reveal the full solution
Twenty-three. With 23 people the probability of a shared birthday is about 50.7 percent; with 22 it is about 47.6 percent.
Work with the complement. The probability that n people all have different birthdays is 365/365 times 364/365 times 363/365, continuing for n factors. For n equals 23 that product is about 0.493, so the chance of at least one shared pair is about 0.507. The exact computation is a short loop; the interview-grade insight is the estimate. Each factor (365 minus i)/365 equals 1 minus i/365, which is close to e to the power (minus i/365) for small i. Multiplying n such factors sums the exponents: the product is roughly e to the power (minus n(n minus 1)/730), close to e to the power (minus n squared over 730). Setting that to one half gives n squared equals 730 times ln 2, about 506, so n is about 22.5. The growth is in n squared because the number of pairs is n(n minus 1)/2, and every pair is a chance to collide.
That is why intuition fails. People imagine covering the year, which is linear in n, when the event is about pairs, which is quadratic. The general rule: with N equally likely values, you expect a collision after roughly the square root of 2N ln 2 draws, about 1.18 times the square root of N. For 365 that is 22.5; for a million it is under 1200.
What this puzzle is really testing
Whether you know the square-root law and where it bites. A hash function with N possible outputs will produce a collision after about the square root of N inputs, not after N. That is why 32-bit hashes collide after tens of thousands of keys, why cryptographic hashes need 256 bits to resist "birthday attacks" at 128-bit effort, and why a hash table's chains start to form long before it is full; the load factor and collisions deep-dive quantifies that last one. The complement trick, computing "none" to get "at least one", is a staple that also appears in the three ants puzzle.
Follow-ups to expect
How many people before someone shares a birthday with you? That is the linear question: 1 minus (364/365) to the power n exceeds one half at n equals 253. How many for a 99 percent chance of some shared pair? About 57. And the systems version: you assign random 64-bit IDs; how many before a duplicate becomes likely? About 5 billion, the square root of 2 to the power 64 scaled by 1.18, which is why 64 bits is fine for most systems and 32 is not.