Worked solutionOne step at a time
Count the misses, not the matches
"At least one match" has many ways to happen. "Everyone different" has one, so compute that and subtract from 1.
Seat people one at a time
The first person can have any day. The second must avoid one day, the third two days, and so on.
Why it falls so fast: pairs
n people make n(n−1)/2 pairs, and each pair matches with chance 1/365. So the miss chance is roughly e^(−pairs/365). At 23 people that is 253 pairs and about 50%.
Answer: B, 57 people
The exact product gives 98.83% at 56 people and 99.01% at 57, so 57 is the first room size past 99%. A separate simulation of 10,000 rooms of 57 found a match in 99.05% of them.
What the simulation showed10,000 rooms on a calendar
The reel drops random people onto a 365-day calendar, one room at a time, with a fixed seed.
- Rooms of 23: 5,087 of 10,000 had a shared birthday, 50.9% (the exact value is 50.73%).
- The same rooms read at other sizes: 10 people 11.5%, 20 people 40.9%, 30 people 70.9%, 40 people 89.3% (exact 89.1%).
- 23 people make 253 pairs, and each pair has a 1-in-365 chance. That is why the curve climbs so steeply.
Wrong answersWhy each one is tempting
| Pick | What went wrong |
|---|---|
| A · 30 | Saw the curve climbing fast and extended it too far: 30 people give about 71%. |
| C · 100 | Rounded up for safety. It works, but 99% arrives at 57. |
| D · 183 | Half of 365: thinking of days covered instead of pairs. |
Follow-ups an interviewer asks nextTry these before opening them
How many people before someone shares YOUR birthday with 50% chance?
Each other person misses your day with chance 364/365, so you need (364/365)^k ≤ 0.5, which gives k = 253. The same number as the pairs in a room of 23, and no coincidence.
Real birthdays are not uniform. Does that help or hurt?
It helps matching. Any unevenness makes collisions more likely, so 23 is an upper bound on the 50% room size.
What does this have to do with hashing?
Hash n keys into m buckets and the first collision is expected around √(πm/2) keys. With 2^64 hash values, collisions start near 2^32 items, which is why 64-bit hashes are not enough for some uses.
Without a calculator, roughly where is the 50% point for m days?
Set n²/(2m) ≈ ln 2, so n ≈ 1.18·√m. For 365 days that is 22.5, so 23.
