The birthday problem

Solved in 1939 by Richard von Mises (first publication).

The problem is usually credited to Harold Davenport around 1927, who did not publish it, and the first published version is by Richard von Mises in 1939. The probability that $k$ people all have different birthdays is $\frac{365\cdot 364\cdots (365-k+1)}{365^k}$. For $k=22$ this is still above 1/2, and for $k=23$ it is about 0.4927, so a shared birthday has probability about 0.507 and the answer is 23. The number seems small because what matters is the number of pairs, and 23 people form 253 pairs. The same square-root effect governs collisions in hash functions.

References

• Birthday problem (Wikipedia)