Misc: Advent calendar motifs

A company that produces chocolate advent calendars has \(m>1\) different motifs for the pieces of chocolate present in the calendars. Each motif is equally common in the overall production, but each company calendar is randomly compiled. So it can happen that within a calendar motifs can be found multiple times. How many different advent calendars of the same company do you have to buy according to expectations in a pre-Christmas period, so that you have found each motif at least once?

Solution

Since each motif is equally likely, we have a chance of \(\frac{1}{m}\) for each motif. We first focus on calendar doors. Let \(X_i\) be the number of doors that need to be opened to see a new unknown motif after the \((i-1)\)th motif.

We know that the probability of seeing a new unknown motif behind the first door is \(P(X_1=1)=1\), seeing a new unknown motif behind the second door has a reduced probability of \(P(X_2=1)=\frac{m-1}{m}\), seeing a new motif behind the third door is \(P(X_3=1)=\frac{m-2}{m}\) and so on until \(P(X_j=1)=\frac{m-j+1}{m}\). As this process follows a geometrical distribution, the expected value is \(E[X_j]=\frac{1}{p_j}\) with \(p_j=\frac{m-j+1}{m}\). The number of doors that need to be opened is thus \(X:=\sum\limits_{i=1}^mX_i\). It follows that the expected value of the number of doors is

\[\begin{array}{rl} E[X] &= E\left[\sum\limits_{i=1}^mX_i\right]\\ &= \sum\limits_{i=1}^mE[X_i]\\ &= \sum\limits_{i=1}^m\frac{m}{m-i+1}\\ &= m\sum\limits_{i=1}^m\frac{1}{i}\\ \end{array} \]

We want the number of calendars \(C(m)\), so we need to average over the 24 doors a calendar has and ceil the result for full calendars:

\[C(m)=\left\lceil\frac{m}{24}\sum\limits_{i=1}^m\frac{1}{i}\right\rceil\]

So how many calendars do we expect to need to see all \(m=\) different motifs of a production line? 5!

« Back to problem overview