In each piece of gum, one of $n$ inserts is included, with each insert occurring with a probability of $1 / n$.

How many pieces of gum do you need to buy on average to collect the entire set of inserts?

#
In the situation where $k$ inserts have already been collected, calculate the average number of gums that need to be bought so that the last gum adds a new insert.

## Solution

Let's assume we have already collected $k$ inserts. We will calculate how long we need to wait for the next insert. We will call a gum new if the insert inside it has not been encountered among the $k$ already collected inserts. Let $M_{k}$ denote the average number of gums that need to be bought so that the last bought gum is new. Consider the next bought gum. It is new with probability ${ }^{n-k} / n$ (and in this case, the expectation of the $(k+1)$-th gum in the collection ends), and with probability $k / n$ it is not new (in this case, by buying one gum, we return to the state where the average number of gums that need to be bought until a new one is $\left.M_{k}\right)$. Therefore, $M_{k}=$
$n-k / n \cdot 1+k / n \cdot\left(M_{k}+1\right)$, from which $M_{k}=n / n-k \cdot$ Thus, the average number of gums that need to be bought for a complete

collection of inserts is $M_{0}+M_{1}+\ldots+M_{n-1}=n / n+n / n-1+\ldots+n / 1=n(1+1 / 2+1 / 3+\ldots+1 / n)$.

## Answer

$n\left(1+\frac{1}{2}+1 / 3+\ldots+1 / n\right)$.

Submit a comment