How many stickers do I need to complete my FIFA Panini album?

Question

I'm playing the FIFA Panini Online Sticker Album, which is an Internet adaption of the classic Panini albums that are usually published for the soccer world cup, European championship, and possibly other tournaments.

The album has placeholders for 424 different stickers. The purpose of the game is to collect all 424. The stickers come in packs of 5, which can be obtained through codes found online (or, in case of the classic printed album, bought at your local newsstand).

I make the following assumptions:

• All stickers are published in the same quantity.
• One pack of stickers does not contain duplicates.

How can I find out how many packs of stickers I need to acquire in order to be reasonably sure (let's say 90%) that I have all 424 unique stickers?

Answer 1

That is a beautiful Coupon Collector's Problem, with a little twist introduced by the fact that stickers come in packs of 5.

If the stickers were bought individually the result are known, as you can see here.

All the estimates for a 90% upper bound for individually-bought stickers are also upper bounds for the problem with a pack of 5, but a less close upper bound.

I think that getting a better 90%-probability upper bound, using the pack of 5 dependence, would get a lot more difficult and would not give you a far better result.

So, using the tail estimate $ P[T>\beta n \log n] \leq n^{-\beta+1}$ with $n=424$ and $n^{-\beta+1} = 0.1$, you'll get to a good answer.

EDIT:

The article "The collector’s problem with group drawings" (Wolfgang Stadje), a reference of the article brought by Assuranceturix, presents an exact analytical solution for the Coupon Collector's Problem with "sticker packs".

Before writing the theorem, some notation definitions: $S$ would be the set of all possible stickers, $s = |S|$. $A \subset S$ would be the subset that interests you (in the OP, $A = S$), and $l = |A|$. We're going to draw, with replacement, $k$ random subsets of $m$ different stickers. $X_{k}(A)$ will be the number of elements of $A$ that appear in at least one of those subsets.

The theorem says that:

$$ P(X_{k}(A) = n) = {l \choose n} \sum_{j=0}^{n}(-1)^j {n \choose j}\left[\frac{s+n-l-j \choose m}{s \choose m}\right]^k $$

So, for the OP we have $ l=s=n=424$ and $m=5$. I did some tries with values of $k$ near the estimate for the classical coupon collector's problem (729 packs) and I got a probability of 90.02% for k equals to 700.

So it was not so far from the upper bound :)

Answer 2

The other day I came across a paper that addresses a closely related question:

http://www.unige.ch/math/folks/velenik/Vulg/Paninimania.pdf

If I have understood it correctly, the expected number of packs you would need to buy would be:

$\binom{424}{5}\sum_{j=1}^{424}\left(-1\right)^{j+1}\frac{\binom{424}{j}}{\binom{424}{5}-\binom{424-j}{5}}$

However, as eqperes points out in the comments, the specific question the OP asks is actually covered in detail in another paper that is not open access.

Their final conclusion suggests the following strategy (for an album of 660 stickers):

• Buy a box of 100 packs of 5 stickers (500 stickers, guaranteed to be all different)
• Buy 40 more packs of 5 stickers and swap the duplicates until you have at most 50 missing stickers.
• Purchase the remaining stickers directly from Panini (these cost approx. 1.5 times as much).

This is total of 140 packs + upto 15 extra packs worth of stickers (by cost) purchased in a targeted fashion, equivalent to at most 155 packs.