The problem of matches
Pierre Rémond de Montmort took up the problem in "Essay d'analyse sur les jeux de hazard" in 1708 and solved it in the second edition of 1713. Nicolaus Bernoulli solved it at about the same time.
Guests have left their hats in a cloakroom and received numbered tickets. The attendant has dropped all the tickets, shuffled them and now hands the hats back completely at random: every guest gets one hat, but which one is down to chance. What is the probability that not a single guest goes home in their own hat? And is it different for 10 guests than for 100?
Intuition says that as the number of guests grows, the chance should either fall to zero or climb to 100%. In fact it freezes almost at once: 50% for 2 guests, 33.3% for 3, 37.5% for 4, and from 7 guests on it is 36.79%, the same for 100 guests. This number is 1/e. The reason is that on average exactly one guest gets their own hat, however many people are in the cloakroom.
The puzzle is more than three hundred years old. Montmort, Nicolaus Bernoulli and Euler worked on it, and today it lives on in letters stuffed into the wrong envelopes and in Secret Santa, where nobody may draw themselves. We tell it through a cloakroom.
n guests come to a party, each with their own hat. Each one checks the hat in and gets a ticket with its number.
The attendant has dropped the tickets and no longer knows whose hat is whose. At the end of the evening he hands the hats out completely at random: each guest gets exactly one hat, all hats are handed out, and every way of matching hats to guests is equally likely.
If a guest gets exactly their own hat, that is a match. There can be any number of matches, from zero to n.
What is the probability that there are no matches at all, that is, nobody gets their own hat? And how does it change with 100 guests instead of 10?
"A hundred guests can't all miss" or "out of a hundred, surely someone gets lucky"
Both sound convincing, and both are wrong. The chance that nobody gets their own is the same for 100 guests as for 10: 36.79%. Each guest is less likely to get lucky, but there are more guests, and on average exactly one gets their own hat.
Compare two cloakrooms: one with 10 guests and one with 100. Lock in your answer before reading on.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
Start small. For two guests and for three, list every way to hand out the hats and count how many leave nobody with their own.
Look at a single guest: how likely is he to get exactly his own hat? And how many such guests are there?
More guests, but a smaller chance for each one. How do the two effects combine in the average number of guests who get their own hat?
Eight parties, each with a different number of guests. Before each hand-out bet 1 to 3 chips on how many guests get their own hat: nobody (pays ×2.7), exactly one (×2.7) or two or more (×3.8). Pete, the old cloakroom attendant, bets on the same hand-outs by gut feeling: "in a small cloakroom someone gets lucky, in a big one nobody does". You each start with 20 chips. Who ends up with more?
After a few hand-outs the answer starts to show, so make your own guess first.
For every number of guests from 1 to 20 the page hands out the hats at random many times (a fair shuffle, like shuffling a deck) and counts the share of hand-outs where nobody got their own. Dots are the simulation, the line is the exact probability from the formula in round 4. Separately, the page counts how many guests get their own hat on average.
First the simple picture: why the chance heads neither to zero nor to one. Then the exact count and where the number e comes from.
“In plain words” is hidden on all puzzles.
Take one guest. The attendant gives them one hat out of n, so they get their own with chance 1/n. The more guests, the smaller each one's chance, but the more people who might get lucky, and the two effects balance exactly: on average exactly one guest gets their own hat, whether the cloakroom holds 10 people or a million. That is why the chance of "nobody" neither sinks to zero nor climbs to 100%: the picture for big cloakrooms is the same as for small ones.
This card does not prove that the answer is exactly 36.8%; it only explains why it does not depend on n. A rough estimate goes like this: each guest misses with chance 1 − 1/n, and if the guests missed independently, they would all miss together with chance (1 − 1/n)ⁿ. For 10 guests that is 34.9%, for 100 it is 36.6%, and as n grows this number also tends to 1/e. But the guests are not independent (if your hat is already with someone, it cannot go to your neighbour), so the exact answer is slightly different: 36.79%. Where it comes from is in the next layers.
A square is a guest; the colour and number on it show whose hat they got. Guests who got their own are outlined. With two guests there are only two hand-outs: each gets their own, or they swap, so the chance of "nobody" is 1/2. With three guests there are six hand-outs, and nobody matched in just two (framed): 1/3. With four, 9 out of 24 = 3/8 = 37.5%, with five, 44 out of 120 = 36.7%. The chance goes a little up, a little down, and the swings die out fast.
“Rigorous” is hidden on all puzzles.
There are n! hand-outs in all (n factorial: n · (n − 1) · … · 1). Throw out those where guest 1 got their own: the rest of the hats can go out in (n − 1)! ways. Do this for each of the n guests, n · (n − 1)! = n! in total. But hand-outs where two guests matched were thrown out twice, so we put them back: there are n(n − 1)/2 pairs of guests, (n − 2)! hand-outs for each, n!/2! in total. Now hand-outs with three matches are miscounted, so subtract n!/3!, and so on up to n. Divide by n!, and you get the probability that nobody matched:
P(n) = 1 − 1 + 1/2! − 1/3! + 1/4! − … ± 1/n! → 1/e ≈ 0.367879
This is exactly the start of the well-known series for 1/e. Each new guest adds one term ±1/n!, and factorials grow insanely fast: the 11th guest changes the chance by only 1/11! ≈ 0.000000025. That is why the answer barely depends on n: after a few guests the terms no longer matter.
Let Dn be the number of hand-outs to n guests where nobody matches. Guest 1 gets the hat of some guest j: n − 1 choices. Then there are two cases. Either guest j got guest 1's hat, the two simply swapped, and the other n − 2 guests must all miss: Dn−2 ways. Or guest j got something else: then treat guest 1's hat as the "wrong own hat" for j, and n − 1 guests must all miss: Dn−1 ways.
The number of matches is a sum of n "light bulbs": guest i's bulb is on if they got their own hat. Each is on with chance 1/n. The guests are dependent, but the expected value of a sum is the sum of the expected values, always, with no conditions. So the average number of matches is n · 1/n = 1 exactly, for any n ≥ 1. The simulation in round 3 confirms it.
What is more, for large n the number of matches follows almost exactly a Poisson distribution with mean 1: exactly k matches happen with a chance close to e−1/k!. Zero and one match are equally likely, 36.8% each, two is 18.4%, three is 6.1%. You can see what it looks like in round 5.
A permutation with no matches at all is called a derangement. Inclusion–exclusion gives their number.
The error after n guests is smaller than the first dropped term, so for n ≥ 1 the number of derangements is n!/e rounded to the nearest integer.
Exactly k matches: choose who matched, and the other n − k must all miss. The mean and the variance are both 1 for n ≥ 2.
“Deeper” is hidden on all puzzles.
The first to study the problem was Pierre Rémond de Montmort, in "Essay d'analyse sur les jeux de hazard" (1708), one of the first books on probability. He gave the solution in the second edition of 1713; Nicolaus Bernoulli solved it at about the same time. Since then it has been called the problem of matches (problème des rencontres).
Leonhard Euler, unaware of Montmort's work, took up the same problem in "Calcul de la probabilité dans le jeu de rencontre" (Memoirs of the Berlin Academy, 1753). Two players draw a card at the same time from their own decks; if they ever draw the same card, the first one wins, otherwise the second. Euler tabulated 1 to 15 cards, noticed that from 12 cards on the first nine decimals no longer change, and recognised 1/e in the series. In his words, the players' chances stand roughly as 12 to 7, and for an ordinary deck of 52 cards this is already very exact.
The number of derangements Dn is often written !n and called the subfactorial, a name coined by William Allen Whitworth. The numbers grow almost like the factorial: !4 = 9, !5 = 44, !10 = 1,334,961, and each one equals n!/e rounded to the nearest integer. The chain Dn = n · Dn−1 + (−1)n produces them even faster than the recursion on the two previous values.
Euler noticed one more detail: for an even number of cards the chance of "no match" is slightly above 1/e, for an odd number slightly below. You can see it in round 3 too: the exact line swings around 1/e, and the swings die out fast.
Mathematics: not just "nobody" but any number of matches, and how it turns into a Poisson distribution. Logic: why a new guest changes almost nothing. Practice: a Secret Santa draw that has to be repeated.
Mathematics
For exactly k matches, choose which guests matched, and the other n − k must all miss. The chance comes out as (1/k!) · Dn−k/(n − k)!, and for large n the second factor is the same 1/e. So in big cloakrooms exactly k matches happen with chance e⁻¹/k!: that is the Poisson distribution with mean 1. It describes rare independent events: calls to a call centre per minute, atoms decaying, letters with typos.
Curiously, exactly one match for n guests has the same chance as "nobody" for n − 1 guests. That is why zero and one match are level from 6–7 guests on. In small cloakrooms the distribution breaks: with two guests exactly one match is impossible, because once one gets their own, the other is left with their own too. Look at n = 2, 3, 4 on the chart.
Logic
Intuition sees only one effect: either "lots of guests, someone will get lucky" or "each has a 1% chance, nobody will". In fact both act, and they cancel: the average number of matches is always 1. All that depends on n are tiny corrections ±1/n!. After 10 guests a new guest can only touch a term below one in a million.
This move pays off far beyond the cloakroom. When one thing grows and another shrinks in proportion, look at the product: here n · 1/n = 1. You will meet it in rare events, insurance, hunting bugs in code: many opportunities, each unlikely, a few events on average, and their count follows the same Poisson.
Practice
In Secret Santa everyone draws a slip from a hat with the name of the person they give a present to. If someone draws themselves, the simplest fix is to redraw everything. A good draw is a derangement, so it succeeds only 36.8% of the time, and on average it takes 1/(1/e) = e ≈ 2.72 tries. With 10 people the first try works 36.8% of the time, three tries or more are needed 40% of the time, four or more 25%.
You can skip the redraws: put everyone in a random circle, and each gives to their neighbour on the right. Nobody gives to themselves, but this only produces hand-outs that form one big circle: for 5 people that is 24 of the 44 possible derangements, and two people never give presents to each other. If you want every derangement to be equally likely, redraw honestly.
Pierre Rémond de Montmort took up the problem in "Essay d'analyse sur les jeux de hazard" in 1708 and solved it in the second edition of 1713. Nicolaus Bernoulli solved it at about the same time.
Euler summed up the game of matches in 1753 like this: the chance of a match stands to the chance of none roughly as 12 to 7, more precisely as 1720 to 1001. Out of 19 games, the first player wins about 12.
In Euler's table, from 12 cards on the chance of "no match" no longer changes in the first nine decimals: 0.367879442. Bigger decks add nothing.
Whether the cloakroom holds 3 guests or 3 million, on average exactly one gets their own hat. It is an exact number, not an approximation, and it does not need the guests to be independent.
If you redraw until nobody draws themselves, it takes e ≈ 2.72 draws on average. For 10 people the exact number is 3,628,800 / 1,334,961 ≈ 2.71828.
The number of derangements is written !n and called the subfactorial, a name coined by William Allen Whitworth. !10 = 1,334,961, and for any n ≥ 1 it is n!/e rounded to the nearest integer.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
Is “Advanced” the right level for this puzzle?
Thank you! This helps set the levels right.
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.