Help a math teacher, please!

A question posed by one of my students, for which I cannot for the life of me come up with a solid solution:

There are p different prizes that could be in a cereal box. If you have n cereal boxes and each contains one prize, what is the probability that your set of n prizes will contain at least one of each of the different prizes?

Teaching 8th grade math for 12 years dulls the blade a little. I am sure there was a time I could have solved this... the student actually posed the question with 5 prizes and 12 boxes, but I am more interested in the general case. Any insight would be appreciated.

[wblipp]

The best method I know for tackling these problems uses matrices to find the distribution of the number of distinct prizes. Some eighth graders have already been exposed to matrices, but if not it's a lot of machinery for a single question.

The matrix approach starts with a 6x6 transition matrix and a vector of probabilities. You can set this up using row vectors or column vectors - my field traditionally used row vectors, so I'll describe it that way. With zero boxes you have zero prizes, so the vector for P₀ is (1,0,0,0,0,0) representing probability of 1 for zero prizes and 0 for 1 through 5 prizes.

T(i,j) represents the probability that if have i distinct prizes and select one more box, then I will then have j distinct prizes. This matrix is zeros except to the major diagonal and the diagonal one above that. T(i,i) = i/5 and T(i,i+1) = (5-i)/5.

The probabilities after 12 boxes are P₀ x T¹²

Using MathCad, I get

(0, 2.048x10^-8, 1.677x10^-4, .021, .301, .678)

You can use eigenvectors and eigenvalues to make interesting approximations, but that is well beyond most eighth graders.

Thanks, that will get me going in the right direction. But you are right, it is way above the level of our 8th grade curriculum. In Michigan the state mandated curriculum does not have anything about matrices until Algebra II, which most students in my district will not take until junior year.

So if there are any solutions that might involve combinations or some other counting method or formula, I would be grateful for the help.

[davieddy]

As an ex-teacher I can attempt a more 12-year-old
friendly approach.
Take 5 prizes and 12 boxes.
The probability that prize 1 isn't allocated to any box
is (4/5)^12 = 0.0687
The probability that neither prize 1 or 2 are allocated
to any box is (3/5)^12 = 0.0022
If we approximate the probability of 3 or more prizes
missing as zero, then we can say that the probability
of any 2 prizes missing is (5Choose2)*0.0022 = 0.022

The probability of some prizes missing is
5*0.0687 - 0.022 = 0.32
So the probability of no prizes missing is 0.68

Not that easy, but I seem to agree with WBlipp's answer!

David

As a father who knows how hard it is for my kids to get complete sets of happy meal prizes, these all seem to be a bit higher than I expected. So let me show you what I came up with, and see who can explain why my solution is so completely wrong.

I start out by counting the number of all possible different ways 5 prizes could be distributed among 12 boxes. 5 possibilities for the first box, 5 for the second box, etc. yields 5^12 possible different arrangements of the five prizes among the 12 boxes.

Now, I start counting the number of boxes that are MISSING one or more prizes. Suppose that none of the 12 boxes holds prize A, but all the other prizes are accounted for; this means there are 4^12 possible arrangements of boxes that are missing only prize A. Since there are 5 different prizes, this means there are 5 x 4^12 different arrangements of boxes that are missing only one of the five prizes.

Suppose that none of the boxes have prize A or prize B. This means there are 3^12 arrangements of boxes missing both prize A and prize B. There are 10 different combinations of 2 missing prizes out of the 5, so there are 10 x 3^12 different arrangements of boxes missing exactly 2 of the five prizes. Similar reasoning yields 10 x 2^12 arrangements missing 3 of the five prizes. And there are exactly 5 arrangements with 4 out of the five prizes missing, since each of these would have 12 boxes that all have the same prize.

I now assert that the probability of the 12 boxes having at least one of the prizes missing is

5 x 4^12 + 10 x 3^12 + 10 x 2^12 + 5
5^12

or about 0.3655. It follows that the probability of having at least one of every prize in 12 boxes is about .6345.

Where am I going wrong?

[wblipp]

If we stick to five prizes case this is manageable for motivated eighth graders. I assume you have taught them that P(A or B) is P(A) + P(B) - P(A and B); Venn diagrams usually make that obvious. Motivated students should be able to figure out, or take on faith, how this generalizes to sums of larger groups.

Let Event A be "Toy #1 is in none of the boxes". Likewise B through E for toys 2 through 5.

They should be able to calculate P(A) = (4/5)^12, and see that it's the same for each single letter set.

They should also be able to calculate P(A and B) = (3/5)^12
P(A and B and C) = (2^5)^12
P(A and B and C and D) = (1/5)^12
P(A and B and C and D and E) = 0

Because everything is symmetrical, they can add up similar cases and get the final result that

P(A or B or C or D or E) = 5*P(A) - 10*P(A and B) + 10*P(A and B and C) - 5*P(A and B and C and D) + P(A and B and C and D and E)

The exponents are combinatorial coefficients (5 chose n), and are there because there are that many combinations of n toys, and they all have the same probability.

This will give them that the probability that at least one toy is missing is .322. The probability that no toy is missing is 1-.322 = .678.

(Note this is davieddy's approach made more rigorous)

[Xyzzy]

...As a father who knows how hard it is for my kids to get complete sets of happy meal prizes...

We use eBay. In the end, it is a whole bunch cheaper. Remember those little dog plushes with the big noses at McDonald's?. Talk about a nightmare. We could have spent $1000 at McDonald's but the whole set on eBay was like $25 or so.

Well, my wife set up a nifty Excel spreadsheet that generates random assortments of 5 prizes among 12 boxes and tallies how many sets of boxes have at least one of each prize. At around 20,000 samples it seems to converge in the neighborhood of 68% so I guess the evidence bolsters your solutions. Thanks once again for all your help! Although I still don't understand why my solution is so wrong. . .

-OFF TOPIC: Yes, we have resorted to Ebay in desperation as well. There was no way I was going to subject my digestive tract to enough Burger King food to get a complete set of Star Wars toys.

[wblipp]

Originally Posted by Unregistered

Now, I start counting the number of boxes that are MISSING one or more prizes. Suppose that none of the 12 boxes holds prize A, but all the other prizes are accounted for; this means there are 4^12 possible arrangements of boxes that are missing only prize A.

No. There are 4^12 possible arrangements of boxes that are missing at least prize A. These arrangement include all the cases that are missing A and B, and those that are missing A and C, and even those that are missing A and B and C and D.

[davieddy]

Originally Posted by wblipp

This will give them that the probability that at least one toy is missing is .322. The probability that no toy is missing is 1-.322 = .678.

(Note this is davieddy's approach made more rigorous)

Very grateful for that.
Note
a) Working with probabilities comes to the same thing
as number of arrangements (divide by 5^12 before of after).
b) More careful counting of arrangements leads to
your expression but with a couple of sign changes,
notably subtracting the number of ways two prizes
are missing instead of adding:

5 x 4^12 - 10 x 3^12 + 10 x 2^12 - 5
5^12

David

Thanks to all for your insight. I have enjoyed my visit to your forums. Keep up the great work!