The 2014 World Cup
Every squad at the 2014 football World Cup had exactly 23 players. The BBC checked their birthdays: 16 of the 32 teams had a shared birthday, exactly half, just as the formula predicts.
How many people do you need in a room before two of them probably share a birthday? Most people guess around 180. The answer is 23. With 70 people a match is almost certain. Check it with a game, a simulation and five explanations.
The birthday problem, or birthday paradox, is usually credited to the mathematician Richard von Mises in 1939. It isn't a real contradiction. It's called a paradox because the right answer sounds impossible.
There are n people in a room: a class, a team, wedding guests. Nobody arranged their birthdays.
A year has 365 days. We assume each person is equally likely to be born on any of them. We ignore 29 February.
A match means at least two people share a day and month. The year doesn't matter, and neither does who: any pair counts.
What is the smallest n for which the chance of a match exceeds 50%? And what are the odds in a class of 30?
"There are 365 days, so you need about half that, around 183 people"
In fact 23 is enough. In a class of 30 there is a match 70% of the time. The mistake is thinking about your own birthday, when what counts is every pair of people.
Real birth rates are uneven, which only raises the chance of a match. More in round 4.
Lock in your answer before reading on. It shows how far intuition misses.
Your answer will be compared with the right one here.
Each new person gets a random birthday and takes a calendar cell. When two land on the same day, the cell lights up. Fill 10 to 15 rooms: the panel on the right shows when the first match usually happens.
Theory: median 23, mean ≈ 24.6. The orange bar contains the median of your rooms.
The computer builds thousands of rooms of n people and counts how many have a match. The line is the exact formula; the dots are the simulation.
The key is that a match can happen in any pair, and there are far more pairs than people. Here are five ways to see it.
The first person can be born any day. The second must miss that day: 364/365. The third must miss two days: 363/365. Each factor is close to 1, but there are many of them. After the 23rd person the product drops below 50%.
When we picture the problem, we put ourselves in it: "who else was born on 14 March?" That is a different, much rarer event. Your day is tested in only 22 pairs, out of 253 pairs in total.
Real birth rates vary: some months see more births, holidays fewer. Any unevenness raises the chance of a match, because people crowd into the "popular" days. A uniform calendar is the worst case, so 23 is an upper bound.
With 366 people a match is 100% certain (ignoring 29 February). That's the pigeonhole principle: with more pigeons than holes, two must share.
The approximation says it all: the exponent is the number of pairs divided by the number of days. So the number of people needed grows like the square root of the number of days. For 365 days that's about 23, not 183.
The same idea works for any kind of "day": months, PIN codes, hashes. And the problem can be made harder: look for three people on one day, or people born a day apart.
Both axes are logarithmic. Intuition expects the line "half of D"; the truth is ≈ √D. For a million values that's 1,178 instead of 500,000.
Press "Check": 10,000 simulated rooms show that at the given size the chance really is about 50%.
| What we look for | People for 50% |
|---|
Every squad at the 2014 football World Cup had exactly 23 players. The BBC checked their birthdays: 16 of the 32 teams had a shared birthday, exactly half, just as the formula predicts.
James Polk and Warren Harding were both born on 2 November. And three of the first five presidents, John Adams, Thomas Jefferson and James Monroe, died on 4 July, Independence Day.
The chance of being born on 29 February is about 1 in 1,461. We left the day out of the model, and adding it back changes nothing: 23 people still give a chance just over 50%.
In many countries the most births happen in late summer and September, and the fewest on holidays such as 25 December and 1 January, since planned deliveries rarely land on them. This unevenness only raises the chance of a match.
Finding a collision in a 64-bit hash takes not 2⁶⁴ tries but about 2³², roughly 5 billion. A modern computer does that in minutes. That's why cryptography uses 256-bit hashes: even 2¹²⁸ tries are out of reach.
A class of 30 has 435 pairs; a wedding with 100 guests has 4,950. The chance that such a wedding has no shared birthday at all is about 1 in 3,300,000.
Share your own explanation, an objection or a variant of the puzzle. Commenting needs a GitHub account.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.