Problem 73 Solution

First I'll show that if the probability of an event happening is p then the mean number of trials to obtain a sucess is 1/p.

Number   Probability
  of         of
Trials     Success
------   -----------
  1           p
  2           pq
  3           pq2
  4           pq3
  .           .
  .           .
  .           .
Since there must eventually be a sucess the sum of probabilities is:
p + pq + pq2 + pq3 + ... = 1.

The mean number of trials (m) is: m = p + 2pq + 3pq2 + 4pq3 + ...

mq = pq + 2pq2 + 3pq3 + ...

m-qm= p + pq + pq2 + pq3 + ...

m(1-q) = 1.

m = 1/(1-q) = 1/p.

Second, the answer to the problem can be express as the sum of the following:

The number of trials to get one toy is obviously one.

Once you have one the probability of getting a different toy in the next box is 3/4, thus the expected number of trials is 1/(3/4) = 4/3 to get the second toy.

By the same logic the number of trials to get the third is 1/(1/2)=2 and 1/(1/4)=4 for the final toy.

Summing these yields 1 + 4/3 + 2 + 4 = 25/3.

I'd like to thank Michael Brasher for providing this solution. Below is my old solution which is much less elegant, I recommend you ignore it.

The probability of it taking i boxes to get all four prizes is the probability that the first (i-1) will contain three different kinds of the toy, times (1/4).

The probability that in j boxes there will be three or less kinds of toys is 4*(3/4)j where j>3.

The probability that in j boxes there will be exactly three kinds of toys is 4*(3/4)j - 12*(1/2)j + 12*(1/4)j. This is rather hard to explain why but basically there are 4 different sets of 3 toys, 6 different sets of 2 toys, and 4 different sets of 1 toy, use this information to not double count combinations of 2 prizes or 1 prize.

Thus the answer is 1/4*sum for j=3 to infinity of j*(4*(3/4)j - 12*(1/2)j + 12*(1/4)j).

Theorem: The sum for j=1 to infinity of i*(1/n)i = n/(n-1)2.

From there is is just simple math to find that the answer is 25/3.

Michael Shackleford, A.S.A.