Birthday Paradox
In a room of just 23 people, there is a 50% chance two share a birthday. This counter-intuitive result arises because the number of pairwise comparisons grows quadratically — 23 people means 253 pairs to check.
How it works
The birthday problem asks: how many randomly chosen people are needed before there’s a 50% chance that two share the same birthday? The answer — just 23 — surprises most people because they instinctively think about collisions with their own birthday. But the question is about any pair sharing a birthday, and the number of pairs grows as n(n−1)/2.
The exact probability follows from computing the complement: the chance that all n people have distinct birthdays is (365/365)(364/365)(363/365)…((365−n+1)/365). Subtracting from 1 gives the collision probability. At n = 23, this crosses 50%. At n = 50, it reaches 97%. At n = 70, it is 99.9%. The probability grows far faster than linear intuition suggests.
The birthday paradox has deep implications for computer science and cryptography. Birthday attacks exploit the same principle: to find a collision in a hash function with n-bit output, you need roughly 2n/2 attempts rather than 2n. This is why cryptographic hash functions need output sizes at least twice the desired security level — a 128-bit security target requires a 256-bit hash. The principle also explains why random ID collisions happen sooner than expected in databases, distributed systems, and UUID generation.