Physically Incorrect

This is the solution to the Cereal Box Surprise puzzle.

The answer is $57.083333…

You can solve this problem straightforwardly by using Markov Chains if you’re familiar with those. Your states will be 0, 1, 2, 3, 4 and 5, signifying the number of boxes in your possession. However, I’ll present a more elementary solution.

First we consider the following subproblem:

if an experiment has N equally probable outcomes, how many times will you have to repeat the experiment (on average) to get a particular outcome, say outcome #1? For example, how many times must you toss a fair coin, on average, until you get Heads?

Intuitively we know the answer is N. For example, to get 6 on throwing a die we’ll have to throw it, on average, 6 times. Can we prove this? Yes. Denote by M the number of throws needed to get a 6. If we get a 6 on the first throw (with probability 1/6), we’ll need just one throw, so M=1. If we don’t (with probability 5/6), we’ll need 1+M throws. The total number of throws is the average of these two options:

M = 1/6*1 + (1+M)*5/6

which yields M=6. In general, we get the following result (you can prove this in the same way we just did for the die):

If an experiment has several (independent) outcomes, and outcome X particular has probability q, the average number of trials we’ll need until we get X is 1/q.

Ok, back to the cereal box question. Let P be the total number of cereal boxes we’ll need, on average, to get all 5 parts.I’m going to write it as a sum of 5 parts:

P = P(0->1) + P(1->2) + P(2->3) + P(3->4) + P(4->5)

where, for example, P(2->3) is the number of boxes we’ll have to buy provided we have 2 parts already and would like to get a third part we don’t have (out of the remaining 5-2 = 3 parts).

• At first we have no cereal box, so whichever one we buy will give us a part. So P(0->1) = 1.
• If we have 1 part, there are 4 parts left. When we buy a new box there is probability 1/5 we’ll get the part we already have and probability 4/5 we’ll get a new part. According to the sub-problem we’ve discussed, the average number of tries we’ll need is the inverse of the probability of the event. In this case, we’ll need to buy 5/4 boxes (on average) to get a new part. So P(1->2)  = 5/4.
• Having 2 parts means there’s a 3/5 chance of getting a new part when buying a new cereal. That means P(2->3) = 5/3.
• Similarly, P(3->4) = 5/2, and P(4->5) = 5/1 = 5.

Adding up, we get:

P = 1 + 5/4 + 5/3 + 5/2 + 5 = 11.4167

meaning, on average, we’ll need to pay

$5 * P = $57.083.

That’s one expensive robot, considering the company probably spent 50 cents to make it in some Chinese sweatshop. Even if you were extremely lucky and got a new part in each box you bought, you’d still have to buy 5 boxes, meaning spending 25$, so the “best case scenario” isn’t very favorable. As the saying goes, you can’t beat the house!

Ok, back to the original cereal box surprise problem.