How many stickers do you have to buy to fill an album? It feels like a bit more than the number of slots. In fact a 50-sticker album takes 225 stickers on average, and most of them go on the last few empty slots. Check it with your own album, a simulation and five explanations.
In probability theory this is the coupon collector's problem. It comes in many forms: album stickers, toys in chocolate eggs, cards in packs of gum. The answer is always the same: the end of the collection costs the most.
The album has 50 numbered slots. Each slot has its own sticker.
Stickers come in sealed packs. You can't see which one you get: each of the 50 is equally likely, and every purchase is independent of the ones before.
If you already have a sticker, it becomes a duplicate and goes on a pile. For now there is nobody to swap with.
On average, how many stickers do you need to buy to fill the whole album?
"There are 50 slots, so a bit more than 50 stickers, maybe 70"
In fact it takes 225 stickers on average, 4.5 times the number of slots. The first half of the album fills fast, and every remaining empty slot costs more than the one before.
Swapping, rare stickers and buying the last ones directly are in round 5.
Lock in your answer before reading on. It shows how far intuition misses.
Your answer will be compared with the right one here.
Each pack gives a few random stickers. New ones take their slot, repeats go on the duplicates pile. Watch the chart on the right: the album grows fast at first, and near the end almost every sticker is a duplicate.
The number in a slot's corner shows how many duplicates of that sticker are on the pile.
The computer fills thousands of albums and records how many stickers each one took. The bars are the simulation; the line is the exact distribution.
The key is that the chance of a new sticker keeps falling. When only one is missing, just one purchase in 50 is the right one. Here are five ways to see it.
When one sticker is missing, each purchase gives it with chance 1/50. You wait 50 tries on average for such an event, as many as there are slots. That one sticker alone costs what the naive estimate gives for the whole album.
| n | Hₙ | ln n + 0.5772 | n·Hₙ |
|---|
Add up all the stages and you get n · (1/n + 1/(n−1) + … + 1/1) = n · Hₙ. The number Hₙ is called a harmonic number. It grows very slowly, roughly as ln n + 0.5772. So you need a little more than n · ln n stickers.
The chance that the next sticker is new equals the share of empty slots. When the album is 90% full, nine purchases out of ten are duplicates. Intuition counts as if every sticker were new, which is why it answers "about 50". Out of 225 stickers bought, 175 are duplicates on average.
Stage k starts when the album already has k−1 stickers. Each purchase is then new with probability (n−k+1)/n, so the wait for one takes n/(n−k+1) tries on average. The stage averages simply add up. The spread is wide: for 50 slots half of all albums are done within 214 stickers, while about one in twenty needs more than 340.
Real albums can have hundreds of stickers. Let's see how many packs they take and what actually helps: packs without repeats, swapping with friends, or buying the last stickers directly.
This size also applies to every block below.
Some publishers promise that no pack contains the same sticker twice. How much does that save?
| Pack type | Packs, exact | Simulated |
|---|
Publishers often let you order a few specific stickers. You buy packs until m slots are left, then order the rest.
Some stickers turn up less often than the rest. What does the album cost then?
Abraham de Moivre studied the problem in the 18th century, and Pierre-Simon Laplace later on. In the 20th century George Pólya returned to it, as did Paul Erdős and Alfréd Rényi, who described exactly how the results spread around the average.
The gap between the harmonic number Hₙ and ln n tends to the constant γ ≈ 0.5772. It has been known for centuries, yet nobody has proved whether it is irrational.
For a 50-slot album the first half of the stickers takes 34 purchases on average, and the second half 191. That's why collections stay "almost done" for so long: the last few slots eat most of the money.
In a 640-slot album the last sticker takes 640 purchases on average. That's 128 packs of 5 stickers for a single empty slot.
If two friends fill 50-slot albums together and pass each other their duplicates, the pair needs 325 stickers on average, not 450. This version is known as the double dixie cup problem.
The same estimate appears when you ask how many random tests it takes to hit each of n cases at least once, or how many random throws until each of n bins holds something. In every case the answer is about n · ln n.
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.