Random Numbers With Constraints
Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.
One of ten different furbies was randomly placed into each box of some type of cereal. If a mother decided to buy this cereal for her children until she obtained at least one of each of the ten different furbies, what is the number of boxes of cereal that she is expected to purchase?
HintThe probability of selecting a different toy is 1/10.
Hide
Answer
This is a problem that uses elementary probability. We know that the probability of selecting a different toy is 1/10. But, when we purchase that first box of cereal, we have a 100% chance of getting a toy that we don't have. Applying a probability distribution, we are expected to purchase 1/1 boxes of cereal initially. Next, we have a 90% chance of getting a toy that we don't have, so total we purchase 1/1 + 1/.9 so far. The probability of getting a toy that we don't have thus decreases with each successive purchase, down to a 10% chance of getting one that we don't have once we've gotten all the others. Thus, we are expected to purchase:
1/1 + 1/.9 + 1/.8 + 1/.7 + 1/.6 + 1/.5 + 1/.4 + 1/.3 + 1/.2 + 1/.1 boxes of cereal for a total of 29.29.
She will probably need to buy 30 boxes before she gets one of each toy.
Hide
Comments
Icewolf
Sep 23, 2003
 I thought this was a great teaser !!! 
krishnan
Sep 23, 2003
 Great teaser. That is a nice way of calculating the answer. 
rose_rox
Sep 23, 2003
 This probability one is great. 
j72883
Sep 25, 2003
 Thanks guys! 
Poker
Aug 01, 2004
 30 boxes?!! I guess that's one way to sell a lot of cereal... 
tsimkin
Nov 23, 2004
 You say "She will probably need to buy 30 boxes before she gets one of each toy." That's not quite true. The mean number she will need to purchase is indeed 29.29. The median, though, which is how many she will "probably" have to purchase (i.e., has a 50% chance of having the number she needs) is actually 27. This difference comes from the fact that the distribution is rightskewed (there are times when you need 400 boxes, but never a case when you can do it in less than 10.) Interestingly, the number of boxes she will buy most often (i.e., the mode) is only about 23 (again, a byproduct of the skew in this distribution.) Great question, though. I had to run a 16000trial Monte Carlo to come up with the right answers for mean and mode. (I am sure this could be determined with calculus, but I do so love pushing Excel to its limits.) Another interesting follow up is how often she can buy just ten boxes. The answer here, of course, is 10!/10^10 = 0.0363%  not very likely! 
Jimbo
Mar 05, 2006
 I think the answer is correct according to the way the questions was worded. I know the answer was given "probably have to buy" but the question actually asked how many she "expected" to buy. So if you have a 90% chance of getting one furbie in a box, that means if you bought 10 boxes you would expect to get a furbie in 9 of them. ie you expect to get 9 furbies. So on the average you would expect to buy 10/9 = 1.1111.. boxes in order to get 1 furbie. And so on. I liked the teaser! 
brainjuice
Mar 27, 2006
 i dont understand although i've seen the solution.. 
Quax
Jul 26, 2006
 Did an Excel spreadsheet on it, came up with the same as tsimkin. At 44 boxes, you're 90% sure. At 51 boxes, you're 95% sure. 
javaguru
Dec 13, 2008
 Nice puzzle, elegant solution.
You don't need to run Monte Carlo or use calculus to exactly calculate the probabilities, although it will be useful in finding limits such as which box are you most likely to find the 10th furby in.
The probability of finding the 10th furby in the nth box (where n >= 10) is
P = (9! * S(n1, 9)) / 10^(n1)
where S(n, 9) is the Stirling number of the second kind, which in this case is the number of ways to partition n elements into 9 nonempty subsets. These subsets represent all the possible combinations of the boxes that contained each of the first 9 furbys. The 10th furby is always only in the last box.
The first four Stirling numbers in the sequence for 9 subsets are:
S(9,9) = 1 since the subset for each furby must contain a single box;
S(10,9) = 45 since each combination includes one subset with two of the 10 boxes and there are C(10,2) = 45 ways to make that subset;
S(11,9) = 1155 since each combination includes either one subset with three boxes (C(11,3) = 165) or two subsets with two boxes ((C(11,2) * C(9,2)) / 2! = 990) and there are 165 + 990 = 1155 ways to make those subsets;
S(12,9) = 22,275 since each combination includes either one subset with four boxes (C(12,4) = 495) or one subset with three boxes and one subset with two boxes (C(12,3) * C(9,2) = 7,920) or three subsets with two boxes ((C(12,2)*C(10,2)*C(8,2))/3! = 13,860) and there are 495 + 7920 + 12860 = 22275 ways to make those subsets.
Note that since the formula for S(n,9) is:
(1/9!) * Sum[i=1to9: (1)^(9i)*C(9,i)*i^n]
the 9! cancels out of (9! * S(n, 9), so the equation for the probability of finding the last furby in the nth box can be simplified to
P = Sum(i=1to9: (1)^(9i)*C(9,i)*i^n) / 9^n
The other question is "what is the probability that I will find the 10 furbies after opening n boxes?" Now the 10th furby is no longer constrained to being in the last box opened, so the probability is
P = (10! * S(n, 10)) / 10^n
This implies that
(10! * S(n, 10)) / 10^n = Sum(b=10 to n: (9! * S(b1, 9)) / 10^(b1)) 
opqpop
Sep 27, 2010
 I don't like this question because I couldn't simplify 1/1 + 1/2 + ... + 1/10. 
Back to Top
 
