Chocolate Chip Probability Word ProblemDate: 9/14/95 at 10:32:39 From: Anonymous Subject: Combinatorics This is a puzzle that was given to me about two years ago. Given 12 chocolate cookies there are 7 chocolate chips that are randomly placed into the cookies. What is the probability that at least one cookie has at least two chips? We've not found a way to calculate this, but have simulated it using the Monte Carlo method. Thanks for your help!! Date: 9/17/95 at 15:42:0 From: Doctor Robin Subject: Re: Combinatorics My interpretation of the problem is that each of the 7 chips is equally likely to be in each of the 12 cookies, independently of the others. For an exact answer in this case, simply drop in the chips one at a time and see whether each chip goes into a different cookie. The probability that the second chip goes somewhere other than the first is 11/12; then the third chip goes somewhere different from either of the first two with probability 10/12, and so on. This shows that the probability of all seven landing in different cookies is (1) (11 * 10 * 9 * 8 * 7 * 6) / 12^6 = .1114... and thus that the probability you want is 1 - .1114... = .8886. In general, if the number of chips is k and the number of cookies is n, you can get a reasonable approximation as follows. There are k*(k-1)/2 pairs of chips; each pair will fall in the same cookie with probability 1/n; thus the probability no two chips fall in the same cookie would be (2) (1 - 1/n)^[k*(k+1)/2] = approx exp ( - k(k+1)/(n2n)) if all the pairs acted independently. While they don't, you still get a good approximation. In the above example, for example, (2) yields .1609 = approx .1738 instead of .1114. The approximation gets better as n and k grow. One could also interpret the problem under the assumption that the chips are inherently indistinguishable, so that every distribution of 7 chips into cookies 1 thru 12 is equally likely. There are 18 choose 7 such arrangements, and 12 choose 7 of these have no two chips in a cookie, so this gives 11 * 10 * 9 * 8 * 7 * 6 / (18*17*16*15*14*13) = approx .0249, so here the probability you're looking for is .9751. This is a reasonable interpretation only if the chips behave like protons or other bosons being partitioned into quantum mechanical states, which is a dubious assumption. Finally, if both cookies and chips are indistinguishable, one gets only 1 arrangement with no double chips out of a total of 15 arrangements, giving a chance of 14/15 or .9333. --- Dr. Robin |
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/