The Chocolate Box ProblemDate: 11/11/2002 at 05:13:47 From: Brian Mitchell Subject: The chocolate box problem Given twelve types of chocolates, what is the probability that a box of fifty (randomly selected from an infinite supply with equal probability) does not contain one or more of the types? I can see that the probability of any given type being missing is (11/12)^50. I reason that the probability I'm trying to find is equal to 1-(the number of unique groups containing all types / total number of unique groups) It is the numerator that gives the trouble... Ah, but I was wrong... The denominator gives equal difficulty :) I see now that the question may be posed: How many ways of adding k positive numbers to equal n? (And what if zero is not allowed?) Still can't do it though. Thanks, Brian Date: 11/11/2002 at 18:41:08 From: Doctor Anthony Subject: Re: The chocolate box problem We start by first finding an expression for T(n,m) where this represents the number of ways of placing n distinguishable objects at random into m distinguishable boxes so that no box is empty. So we can model our problem as placing 50 distinguishable balls at random into 12 boxes and find the probability that no box is empty. Subtracting this probability from 1 will give the probability that one or more boxes are empty - or one or more types of chocolate are missing. Consider a problem of finding the number of arrangements of 10 letters that can be made from unlimited supplies of 4 letters A, B, C, and D such that each letter appears at least once. We require the coefficient of x^10/10! in the expansion of = [x + x^2/2! + x^3/3! + ..]^4 = [e^x - 1]^4 The -1 ensures that we MUST have an A, B, C and D somewhere in each arrangement. [e^x-1]^4 = e^(4x) - 4e^(3x) + 6e^(2x) - 4e^x + 1 from which we pick out term in x^10. = (4x)^10/10! - 4.(3x)^10/10! + 6.(2x)^10/10! - 4.x^10/10! = [4^10 - 4.(3^10) + 6.(2^10) - 4].(x^10/10!) and the term in square brackets is the coefficient of x^10/10! So T(10,4) = [4^10 - 4.(3^10) + 6.(2^10) - 4] = 818520 which corresponds to the formula m T(n,m) = SUM[(-1)^k.C(m,k).(m-k)^n] with n=10 and m=4 k=0 In the problem with the chocolates we have n=50 and m=12 so we require T(50,12) = 12^50 -12(11^50) +66(10^50) -220(9^50) +495(8^50) - 792(7^50) + 924(6^50) - 792(5^50) + 495(4^50) - 220(3^50) + 66(2^50) - 12(1^50) = 7.756621135 x 10^53 The total number of ways of distributing the 50 balls is 12^50, so 7.756621135 x 10^53 Probability no box is empty = ------------------- 12^50 = 0.852335 Probability that one or more box is empty = 1 - 0.852335 = 0.147665 So the probability that some types of chocolate are missing = 0.1477 - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 11/11/2002 at 22:08:42 From: Brian Mitchell Subject: Thank you (The chocolate box problem) Wow, cool! Thanks for your speedy reply. Now I know what I'm looking for, I found quite a few other answers by you in the archives using the T(n,m) function. Is there a common name for such problems? Thanks, Brian. Date: 11/12/2002 at 11:11:39 From: Doctor Anthony Subject: Re: Thank you (The chocolate box problem) These questions come under the general title of 'combinatorics'. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/