# Thread: enumeration problem solving question

1. ## enumeration problem solving question

enumeration question...

a breakfast cereal company is putting a free plastic toy in each box of cereal. so as not to disappoint their customers, they would like to ensure that there is a better than 90% chance that a person will not get the same toy twice unless they buy more than 5 boxes of cereal. what is the minimum number of different toys that will be required?

2. Originally Posted by wik_chick88
enumeration question...

a breakfast cereal company is putting a free plastic toy in each box of cereal. so as not to disappoint their customers, they would like to ensure that there is a better than 90% chance that a person will not get the same toy twice unless they buy more than 5 boxes of cereal. what is the minimum number of different toys that will be required?

Let the minimum number of toys be m. The probability of getting a particular toy in a cereal box is 1/m.

Let X be the random variable number of times a particular toy is got in five boxes.

X ~ Binomial(n = 5, p = 1/m).

Require the smallest value of m that satisfies

$\displaystyle \Pr(X > 1) \leq 0.1 \Rightarrow 1 - \Pr(X \leq 1) \leq 0.1 \Rightarrow \Pr(X \leq 1) \geq 0.9$ $\displaystyle \Rightarrow \Pr(X = 0) + \Pr(X = 1) \geq 0.9$.

Therefore require the smallest value of m that satisfies

$\displaystyle \left(1 - \frac{1}{m}\right)^5 + 5 \left( \frac{1}{m} \right) \left(1 - \frac{1}{m}\right)^4 \geq 0.9$

$\displaystyle \Rightarrow \left(1 - \frac{1}{m}\right)^4 \left(1 + \frac{4}{m}\right) \geq 0.9$.

Using my TI-89 I get m = 9.

3. thanks heaps for your speedy reply. the only problem is that im getting confused where u change Pr(X=0) = Pr(X=1) ≥ 0.9 into the next expresion which involves m. is there a way to solve this problem using discrete maths and enumeration not statistical methods? or is this the only way?

4. Originally Posted by wik_chick88
thanks heaps for your speedy reply. the only problem is that im getting confused where u change Pr(X=0) = Pr(X=1) ≥ 0.9 into the next expresion which involves m. is there a way to solve this problem using discrete maths and enumeration not statistical methods? or is this the only way?
$\displaystyle \Pr(X = 0) = {5 \choose 0} p^0 (1 - p)^5$.

$\displaystyle \Pr(X = 1) = {5 \choose 1} p^1 (1 - p)^4$.

Note that p = 1/m.

There probably is a way of doing it using only counting methods and not statistics but I can't think of one right now. Perhaps someone else will have an idea.

5. Originally Posted by mr fantastic
Let the minimum number of toys be m. The probability of getting a particular toy in a cereal box is 1/m.

Let X be the random variable number of times a particular toy is got in five boxes.

X ~ Binomial(n = 5, p = 1/m).

Require the smallest value of m that satisfies

$\displaystyle \Pr(X > 1) \leq 0.1 \Rightarrow 1 - \Pr(X \leq 1) \leq 0.1 \Rightarrow \Pr(X \leq 1) \geq 0.9$ $\displaystyle \Rightarrow \Pr(X = 0) + \Pr(X = 1) \geq 0.9$.

Therefore require the smallest value of m that satisfies

$\displaystyle \left(1 - \frac{1}{m}\right)^5 + 5 \left( \frac{1}{m} \right) \left(1 - \frac{1}{m}\right)^4 \geq 0.9$

$\displaystyle \Rightarrow \left(1 - \frac{1}{m}\right)^4 \left(1 + \frac{4}{m}\right) \geq 0.9$.

Using my TI-89 I get m = 9.
I'm going to disagree with Mr. F here; X is the number of toys of a particular type, say toy #1, so he has computed the probability that toy #1 will not be found more than once in a group of 5, whereas the original problem asks that all the toys be distinct.

To that end, let m be the number of available toys, as before. The probability that the first toy taken is distinct, i.e. not a duplicate, is 1. The probability that the second toy is distinct is (m-1)/m because there are m-1 choices left. The probability that the third toy is distinct is (m-2)/m. ... Finally, the probability that the fifth toy is distinct is (m-4)/m.

So the probability that all toys are distinct is
$\displaystyle f(m) = 1 \cdot \frac{m-1}{m} \cdot \frac{m-2}{m} \cdot \frac{m-3}{m} \cdot \frac{m-4}{m}$.

We want the least m such that f(m) > 0.9. I get f(97) = 0.9006.

6. Originally Posted by awkward
I'm going to disagree with Mr. F here; X is the number of toys of a particular type, say toy #1, so he has computed the probability that toy #1 will not be found more than once in a group of 5, whereas the original problem asks that all the toys be distinct.

To that end, let m be the number of available toys, as before. The probability that the first toy taken is distinct, i.e. not a duplicate, is 1. The probability that the second toy is distinct is (m-1)/m because there are m-1 choices left. The probability that the third toy is distinct is (m-2)/m. ... Finally, the probability that the fifth toy is distinct is (m-4)/m.

So the probability that all toys are distinct is
$\displaystyle f(m) = 1 \cdot \frac{m-1}{m} \cdot \frac{m-2}{m} \cdot \frac{m-3}{m} \cdot \frac{m-4}{m}$.

We want the least m such that f(m) > 0.9. I get f(97) = 0.9006.

7. i must admit, awkward's way of working out this problem seems to make a lot more sense to me. BUT 97 toys?? does that not seem a lot?? 9 sounds a lot more reasonable...and is there any way i can get the 97 without graphing the function? like mathematically? thankssss

8. Originally Posted by wik_chick88
i must admit, awkward's way of working out this problem seems to make a lot more sense to me. BUT 97 toys?? does that not seem a lot?? 9 sounds a lot more reasonable...and is there any way i can get the 97 without graphing the function? like mathematically? thankssss
I have to admit that 97 does not seem reasonable in the real-world sense-- who is going to manufacture 97 different toys? (Of course, I guess they might be something really simple, like baseball cards.)

As for finding the least value of m such that f(m) > 0.9, probably the best way to proceed is some form of binary search. First find a value of m sufficiently large that that f(m) > 0.9 (for example, you could try m = 10, 20, 40, 80, 160, or something like that), then try m/2, etc. It shouldn't take many tries to zero in on the best value.