# You are making cookies and add N chips to dough randomly, and split it into 100 equal cookies, again at random. How many chips should go into dough?

Question: You are making chocolate chip cookies. You add N chips randomly to the dough and you randomly split the dough into 100 equal cookies. How many chips should go into the dough to give a probability of at least 90% that every cookie has at least one chip?

I tried to attempt to solve this using IID random variables. I am not sure how to set the problem up. I know that there should at least be 100 chocolate chips or else the cookies will not meet the "at least 1 chip per cookie" requirement and that there is 10% chance that the cookies do not have a chip.

• Don't we need to know the volume that each chip and cookie takes up? - Otherwise all the chips could be squashed into 1 cookie. Apr 16 '15 at 22:19
• @ahorn The word "equal" is in the second sentence.
– Ian
Apr 16 '15 at 22:20
• I think this question boils down to counting the number of possible partitions of an $N$ element set into 100 disjoint (some possibly empty) subsets, and the number of possible partitions of an $N$ element set into 99 disjoint subsets. Then the probability of having a cookie with no chips is the second number divided by the first number. I'm not sure that there is an easy way to do this with the central limit theorem, because I don't think you really have independence: the number of chips in the second cookie is dependent on the number of chips in the first.
– Ian
Apr 16 '15 at 22:24
• A more straightforward way might be to count the number of partitions of an $N$ element set into $i$ disjoint non-empty subsets, for $i=1,\dots,100$, and then into $i$ disjoint non-empty subsets for $i=1,\dots,99$. Then divide.
– Ian
Apr 16 '15 at 22:29
• I think this problem is intended to be just a sweet-n-tasty hi-carb restatement of $n$ items being thrown into 100 bins, one toss per item, the tosses mutally independent and equilikely to end up in any bin. Relating this to actually scooping the cookies, we'd have to assume, besides equal volume per cookie, also the chips having volume 0. Otherwise the chips won't fall independently into the cookies; if the chips have as much volume as the dough say then no cookie will have more than 2 chips.
– Mike
Mar 23 at 21:05

There seem to be several interpretations of what you are looking for. I have revised my answer to make it clear what I am answering, and appended a comment for a different interpretation.

I'd suggest an approximate Poisson model. If there are $N$ chips in the dough, then the number of chips in a random cookie is $X \sim Pois(\lambda = N/100).$ You want a 90% probability that a random cookie has at least one chip, then solve for $N$ in $$1 - P\{X = 0\} = 1 - e^{-N/100} = .90.$$

Addendum: If you want a 90% chance that every one of the 100 cookies has at least one chip, then that's another problem, to which the Coupon Collection approach suggested in another Answer is a specific idea that may be appropriate. There are Comments with strong opinions about approaches, but no specific suggestions yet.

• You should point out that this is approximate, whereas there is obviously an analytic form of solution somewhere (even if the combinatorics are messy).
– Ian
Apr 16 '15 at 22:31
• Maybe read my comments to the OP to see what I mean instead of assuming I am thinking of something extremely naive.
– Ian
Apr 16 '15 at 22:39
• I don't know if Poisson is appropriate. The cookies are not independent; chips baked into one cookie are chips that aren't baked into the others. Apr 16 '15 at 23:56
• Can you please state the bernoulli trials , leading to the binomial?
– DRPR
May 12 '18 at 6:51

Hint: Look up the "coupon collector's" problem and use the probability estimates derived for that problem.

The general approach is as follows. This is only an approximation but it's an okay one as we see at the end.

Let's define $$P_c$$ as the probability that every cookie has at least 1 chip. Then we have the complement of this $$P_{nc} = 1-P_c$$ which is the probability that one or more cookies don't have a chip. We can now represent this event as a sum of simple events. Define $$C_i$$ as the event that the i-th cookie has no chips. We can now write

\begin{align} P_{nc} & = P(C_0 \cup C_1 \cup \cdots \cup C_{100}) \\ & = P \left( \bigcup_{i=1}^{100} C_i \right) \leq \sum_{i=1}^{100} P(C_i) \end{align}

and we use Boole's inequality to place an upper bound on this. So now what's left is to determine $$P(C_i)$$ probability of a single cookie of having no chips. Here's one way to think about it:

• each chip arrives independently and there is a $$\frac{1}{100}$$ chance it will land in this cookie $$C_i$$
• there is a $$\frac{99}{100}$$ chance it will not land in cookie $$C_i$$
• for a total of N chips this becomes $$\frac{99}{100}^N$$

Thus $$P(C_i) = \frac{99}{100}^N$$ is the probability of a single cookie having no chips when N chips are randomly distributed amongst 100 cookies. Continuing, we have

\begin{align} P_{nc} & = \sum_{i=1}^{100} P(C_i) \\ & = \sum_{i=1}^{100} \frac{99}{100}^N = 100 \frac{99}{100}^N \end{align}

Consequently $$P_c \ge 1 - 100 \frac{99}{100}^N$$, which we solve by taking the equality and obtain

\begin{align} 1 - 100 \frac{99}{100}^N & = 0.9 \\ \frac{99}{100}^N &= 1000^{-1} \\ N \ln{\frac{99}{100}} & = -\ln{1000} \\ N & = -\frac{\ln{1000}}{\ln{\frac{99}{100}}} \\ N & \approx 687.31 \end{align}

Which is the upper bound solution to the problem.

Note: that by using Boole's Inequality we are assuming $$C_i$$ events do not overlap, i.e. we will not have more than 1 chipless cookie. These higher-order terms include probabilities of more than 1 cookie having no chips. These terms range from i=1 (1 chipless cookie, which we considered here) to 99, which represents a situation where all the chips would be in a the 100th cookie, and the remainder 99 would be chipless. It can be shown that such higher-order terms contribute little to the sum above, but I am not mathematical enough to do it.

However, numerical simulations yield a value of $$N = 682-683$$, so we can see it's a great approximation.

If there is a requirement that the chocolate chips are evenly (or "equally") distributed, then you need at least 100 chips in order for there to be a non-zero probability of having at least 1 chip in every cookie. But then there will be a 100% probability that every cookie will have a chip in it because the chips are evenly distributed, so $N=100$.

On the other hand, if you believe that the chips were "randomly" distributed, you would need to know the maximum amount of chips which could fit into 1 cookie, and assume that every cookie is the same size. You would also need a function to describe the "randomness" - i.e. if some cookies will get more chips than others and by how much.