How Many Cereal Boxes to Buy for a Complete Set of Pens?

[musicgold]

Hi,

I am stuck with the following problem and not sure where I am going wrong. I know that I can solve this problem by simulation, but I want to find a more elegant way of solving it.

Problem : Suppose a cereal company is running a promotion on its cereal by including one of six different colored pens in each box. Assume that you have an equal chance of getting any of the six colored pens when you buy a box. How many boxes should one buy to be 50% sure that he will have at least one complete set of the six colored pens?

My approach: The minimum number of boxes one needs to buy to get the full set = 6.
Then I tried to calculate the chance of getting a full set on purchasing only six boxes.

6 boxes

Permutations = 6 x 6 x 6 x 6 x 6 x 6 = 46,656

Chance of getting a full set = 6 P 6 x (1 / 46,656) = 720 x (1 / 46,656) =0.01543


I extended the same logic further, however I am not sure about the results. For example, see the following calculations for 7 and 11 boxes. I am not sure why the chance of getting a full set declines in the case of 11 boxes.

7 boxes

Permutations = 6 x 6 x 6 x 6 x 6 x 6 x 6 = 279,936

Chance of getting a full set = 7 P 6 x (1 / 279936) = 5040 x (1 / 279936) = 0.0180


11 boxes

Permutations = 362,797,056

Chance of getting a full set =11 P 6 x (1 / 362797056) = 332640 x (1 / 362797056) = 0.0009



Thanks,

MG.

 

[musicgold]

csprof2000,

Thanks. Unfortunately I am not able to follow your solution. It is still a bit complicated to me.
I don't understand what you mean by first, second ...picks. I am not even able to get your numbers, for example, 120, 7776, and 32.4. Can you please elaborate?

Also notice that my calculation for the chance of getting a full set in six boxes gives the same number as your answer, i.e. 0.01543 =120 / 7776( note that I have corrected my post.)

I also know that I am under counting the cases in the cases with more than 6 boxes, but not sure how to avoid that.

Thanks,

MG.

 

[feynomite]

I think the problem here is 11 P 6 is not counting what you think it is. Rather, it's counting the number of ways to pick 6 of the 11 boxes, where the order picked matters. Like this, where 1,2,3,4,5,6 means the order it was chosen and - means it was not chosen:
{1,2,3,4,5,6,-,-,-,-,-}
{1,2,3,4,5,-,6,-,-,-,-}
{3,2,5,6,4,-,-,1,-,-,-}
... 362797056 other examples.

You are correct for the special case of 6... where all the possible orders of picking the 6 boxes is the same number as all the arrangements of 6 boxes where they each have a unique pen. But it's only correct for this case.

It 11 P 6 is *not* counting the number of unique arrangements of 11 boxes where that arrangement has {1,2,3,4,5,6}. It's counting the number of ways to pick 6 from 11 boxes, where order matters. In other words, you aren't counting the case where several boxes have the same type of pen, but out of the 11 they have the unique set of 6.

I'm not sure how to solve your problem, but you might want to start with the easy case: how many boxes do you need to choose in order to get a 50% chance for that *one* pen that you really want?

 

[musicgold]

Hi,

The following is my solution to the problem. Please let me know if my approach is correct. Also, if anybody needs it, I will be happy to share the Excel file in which I did this work.
I solved this problem in two steps. First I took on a simpler case where there are only three types of pens (A, B, C) in the cereal boxes. I worked on three scenarios: picking 4 boxes, 5 boxes, and 6 boxes.

After thinking over the problem, I realized that instead of worrying about all possible permutations that may be generated when I pick up 4 boxes, I should worry about only the permutations that will have a full set of 3 pens. Total permutations = 3^4 =81. There are only three permutations (and their variations) of interest.

Sample Permutation and Total permutations
ABC A =permut(4,4) / 2! = 24 / 2 = 12
ABC B =permut(4,4) / 2! = 24 / 2 = 12
ABC C =permut(4,4) / 2! = 24 / 2 = 12

Thus 36 of 81 permutations will have a full pen set or a 44% chance.


Now drawing 5 boxes. 243 possible permutations. Note a permutation of interest consist of the required set, i.e. ABC and a combination of two other pens. The main thing here is figuring these combinations.

ABC AA =permut(5,5) / 3! = 120 / 6 = 20
ABC AB =permut(5,5) / 3! 2! = 120 / 4 = 30
ABC AC =permut(5,5) / 3! 2! = 120 / 4 = 30
ABC BB =permut(5,5) / 3! = 120 / 6 = 20
ABC BC =permut(5,5) / 3! 2! = 120 / 4 = 30
ABC CC =permut(5,5) / 3! = 120 / 6 = 20

150 of 243 will have a full pen set or a 62% chance.

Now drawing 6 boxes. 729 permutations. To find the unique combinations, I used the typical circles-separators method (I don’t know its official name). In this case there are three circles and two separators ( ООО││), resulting in 10 unique combinations.

ABC AAA =permut(6,6) / 4! = 720 / 24 = 30
ABC BBB =permut(6,6) / 4! = 720 / 24 = 30
ABC CCC =permut(6,6) / 4! = 720 / 24 = 30
ABC ABB =permut(6,6) / 3! 2! = 720 / 12 = 60
ABC ACC =permut(6,6) / 3! 2! = 720 / 12 = 60
ABC BCC =permut(6,6) / 3! 2! = 720 / 12 = 60
ABC BAA =permut(6,6) / 3! 2! = 720 / 12 = 60
ABC CAA =permut(6,6) / 3! 2! = 720 / 12 = 60
ABC CBB =permut(6,6) / 3! 2! = 720 / 12 = 60
ABC ABC =permut(6,6) / 2! 2! 2! = 720 / 8 = 90

540 of 729 will have a full pen set or a 74% chance. I also cross checked my answer for this case with by a simulation model in Excel, and got 73.5% as the answer for a 10000 iteration simulation.

Then I extended the above logic to the original problem with 6 color pens in the cereal boxes. I worked on two cases: picking 9 boxes, and 12 boxes.

In the 9 boxes case, I had 56 unique combinations representing a total of 1.9 million out of 10.1 million possible permutations. Thus the chance of getting a full set (all six pens) was only 18.9%. A simulation using 10,000 iterations sets the chance at 14%. I think the simulation is not precise because of the relatively smaller sample as compared to the population.

In the 12 boxes case, I only used simulation to figure the chance of getting a full set. According to a 10,000 iteration simulation, the chance is only 40.3%. Again I think the answer is not precise because of the smaller sample.


Thanks,

MG.

 

[Adeimantus]

Your solution looks correct to me. And very clever too. Starting with a simplified problem was an excellent idea. I would run a longer simulation if possible just to confirm your work. I don't know how long that takes in Excel. If I had a C compiler I would try it myself, because this is a neat problem.

I think there is another way to do the problem if you are interested. It involves an extension of the formula for the probability that event A or event B happens:

P(A v B) = P(A) + P(B) - P(AB) where 'v' means 'or' and 'AB' means 'A and B'.

For three events it looks like this:

P(A v B v C) = P(A) + P(B) + P(C) - [P(AB) + P(AC) + P(BC)] + P(ABC)

You can extend this formula to six events. Let me know if you want to know more. I got the same answer you did for 9 boxes: 18.9%. So I'm guessing we're both right.


Edit: Also, what happened to csprof2000's solution? I don't see it.

 

[musicgold]

Adeimantus,

Thanks. I would love to find another way to solve this problem. I tried to understand your approach, but could not go very far for the following reasons.

1. P(A v B v C) - I don't understand why you are using the OR rule when it seems we need to use the AND rule. We want to figure the chance of getting all the pens in a sample. Could you show me your calculation to get the 18.9% answer?

2. Moreover, I found it difficult to get a formula for the OR rule with more than 3 variables. I found only one page http://library.thinkquest.org/C006087/english/basic.shtml" which discusses the OR rule with 4 variables, but I am still trying to wrap my head around it. I wonder if you could point me to a site.

 

[Adeimantus]

Adeimantus,

Thanks. I would love to find another way to solve this problem. I tried to understand your approach, but could not go very far for the following reasons.

1. P(A v B v C) - I don't understand why you are using the OR rule when it seems we need to use the AND rule. We want to figure the chance of getting all the pens in a sample. Could you show me your calculation to get the 18.9% answer?

2. Moreover, I found it difficult to get a formula for the OR rule with more than 3 variables. I found only one page http://library.thinkquest.org/C006087/english/basic.shtml" which discusses the OR rule with 4 variables, but I am still trying to wrap my head around it. I wonder if you could point me to a site.

Sure thing. I didn't give nearly enough information for you to actually know how I did it...I was just hinting that there might be another way if you have the time to work on it. Here is a wikipedia page on the formula in question, known as the inclusion-exclusion principle:

http://en.wikipedia.org/wiki/Inclusion-exclusion

You can visualize it with Venn-diagrams. For three events , draw three overlapping circles labeled a, b, c. You can think of an 'event A' as a point being inside the circle a, an 'event A and B' as a point inside the region where circles a and b overlap, and so on. The area of the figure formed by the three overlapping circles represents the probability P(A v B v C). You can see by inspection that this area is equal to the sum of the areas of the three circles, minus the areas of the three regions where pairs of circles overlap, plus the area in the middle where all three overlap. That is the geometric interpretation of

P(A v B v C) = P(A) + P(B) + P(C) - P(AB) - P(AC) - P(BC) + P(ABC)

To generalize it to more events, you could draw more and more circles, but that gets complicated fast. You can obtain the formula for four events from the one for three by letting event C be a disjuction of two other events D and E: C = D v E. If you substitute D v E in for C in the above formula and then apply the logical rule

X and (Y or Z) = (X and Y) or (X and Z)

and the formula for two events P(X v Y) = P(X) + P(Y) - P(XY) and do some simplifying, you should get

P(A v B v D v E) = P(A) + P(B) + P(D) + P(E) - P(AB) - P(AD) - P(AE) - P(BD) - P(BE) - P(DE)
+ P(ABD) + P(ABE) + P(ADE) + P(BDE) - P(ABDE)

You can repeat this to obtain the formula for five events, six events, and so on, but you can probably guess the formula for six events now. You always get that alternating pattern: add the individual events, subtract the pairs, add the triples, subtract the quadruples, etc. For N events, there are 2^N - 1 terms.

So now, my approach to getting that answer of 18.9% for 9 boxes: I went about it indirectly, which is why I needed the 'or' formula instead of 'and'. For n boxes, instead of calculating the probability Q that all six colors appear, calculate the probability that at least one color does not appear, which is just 1 - Q. So if you have six colors a, b, c, d, e, f, define the event A that color a does not appear in the n boxes, event B that color b does not appear in the n boxes, etc. You are now looking for the probability that at least one of the events A, B, C, D, E, F occurs, or

1 - Q = P(A v B v C v D v E v F)

For any particular color, the probability that it does not occur in n boxes is (5/6)^n. Since there are 6 colors, the first set of terms in the expansion of the above formula sum to 6*(5/6)^n. For any pair of colors, the probability that neither of them occurs in n boxes is (4/6)^n. Since there are 6 C 2 = 15 pairs, the second set of terms sum to -15*(4/6)^n. Continuing in this way gets

$$1 - Q = 6(5/6)^n - 15(4/6)^n + 20(3/6)^n - 15(2/6)^n + 6(1/6)^n$$

Note that the last term in the inclusion-exclusion formula for six events, -P(ABCDEF), is zero here since at least one color must appear. Substituting n = 9 gives 1 - Q = .811, or Q = .189. You can then substitute larger values of n to find the first one that gives you Q > 0.5. I get n = 13.

 

[musicgold]

Adeimantus,

Thanks. I really appreciate your detailed response. Let me digest it and I will come back with my doubts, if any.

MG.