Chocolate Chip Probability Word Problem

Date: 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