The birthday paradox
What is the smallest group of people for which the chance that at least two share a birthday is more than 50%? Assume 365 equally likely birthdays and ignore 29 February.
Show hint
It is easier to work out the chance that everyone's birthday is different, then subtract from 1.
Show solution
23 people (about 50.7%).
The chance that all k birthdays differ is (365/365) × (364/365) × ... × ((365 − k + 1)/365). It drops below 0.5 at k = 23. It feels too small because 23 people form 253 pairs.
The same maths explains hash collisions: with 2n possible hash values, you expect a collision after only about 2n/2 items.
Want a problem like this every day? See today's problem and keep a streak going.