The Birthday Paradox: Why 23 People Are Enough

The Surprising Math of Birthdays

How many people do you need in a room before there's a good chance two share the same birthday?

Most people guess around 183. But the real answer is just 23!

Why Is It So Low?

We're not looking for someone with YOUR birthday — we're looking for ANY two people who share ANY birthday.

With 23 people, there are 253 possible pairs to check.

Try It Yourself

Next time you're in a group of 30+ people, ask everyone their birthday. There's a 70% chance you'll find a match!

The Birthday Problem

The birthday paradox demonstrates how human intuition fails with probability.

The Math

P(no match) = 365/365 × 364/365 × 363/365 × ... × (365-n+1)/365

Why Our Intuition Fails

The number of pairs grows quadratically: C(n,2) = n(n-1)/2. With 23 people, that's 253 pairs.

Key Points

• This principle is used in cryptography (birthday attacks on hash functions)
• Real birthdays aren't uniformly distributed, which actually makes matches MORE likely
• The generalized formula works for any number of possible values

The Birthday Problem: Analysis and Applications

The probability of at least one collision among n items drawn uniformly from d values:

P(n,d) = 1 - d!/(d^n · (d-n)!)

Using approximation: P(n,d) ≈ 1 - e^(-n(n-1)/(2d))

Solving for 50%: n ≈ 1.177√d. For d = 365: n ≈ 22.5.

Birthday Attacks in Cryptography

SHA-256 provides 128-bit collision resistance (not 256-bit) due to the birthday bound.

Wagner's algorithm solves the k-list birthday problem in time O(2^(n/(1+⌊log₂k⌋))).

Key Points

• The birthday bound O(√d) appears throughout computer science
• Non-uniform distributions increase collision probability
• Post-quantum cryptography must account for Grover's algorithm