# $n$ chips for 100 cookies problem — is there a counting solution?

The problem is "You are making 100 cookies. How many chips $$n$$ do you need to put into the batter to have at least 90% probability that every cookie has at least one chip?"

I tried a stars and bars combinatorics approach to this as follows:

p(every cookie has at least one chip) = $$\dfrac{\# permutations \;with \geq 1 \; chip \; per \; cookie}{\# total \; permutations}$$

Given 99 'bars' (cookie separators) amongst $$n$$ 'stars' (chips) there are $$\binom{n+99}{99}$$ possible permutations of chips across the cookies (permutations not combinations because we can imagine the bars dividing chips between 100 cookies numbered 1-100)

We can tweak the stars and bars approach for the numerator, i.e. consider 99 bars/cookie separators which can be allocated (without repetition) to the $$n-1$$ spaces between stars/chips. This yields $$\binom{n-1}{99}$$ permutations where every cookie has at least one chip, as we have left out the edges (hence $$n-1$$) and ensured that bars cannot be adjacent (which would result in 0-chip cookies) — there is at least one chip between each bar.

Giving an answer which is the solution to $$\dfrac{\binom{n-1}{99}}{\binom{n+99}{99}} = 0.9$$

This would need to be calculated numerically of course (as does the exact solution in the book), but plugging in the correct answer of $$n=683$$ yields a tiny probability, $$<10^{-6}$$.

Clearly I have gone wrong somewhere, so my question is, where?

• Stars and Bars is seldom useful for probability, as the outcomes it counts are not equally probable.
– lulu
Commented Sep 12, 2023 at 17:08
• Presumably the intended solution would have that you consider $100^n$ different scenarios, imagining that each individual chip is added separately and winds up in a particular scoop uniformly and independently in comparison to how other chips wind up. Of course, this is not perfectly reasonable in practice... we know that a thousand chips can not all be in the same one cookie, there isn't enough space for them, but the odds of this happening are low enough we might choose to ignore this. Commented Sep 12, 2023 at 17:14
• – Karl
Commented Sep 12, 2023 at 17:23

Let us consider a smaller version of the problem. You are making $$2$$ cookies. How many chips $$n$$ do you need to put in to have an at least $$50\%$$ probability that all cookies have a chip?

According to your method, $$2$$ chips is insufficient. Using stars and bars, there are $$\binom{2+2-1}{2}=3$$ ways these two chips can be distributed to the two cookies, either $$(2,0)$$, $$(1,1)$$, or $$(0,2)$$. Only one of these is successful, so the probability of success is $$1/3$$.

However, it should be obvious that $$2$$ chips is sufficient. When there are two chips, each chip lands in either the left or right cookie with with a probability $$50\%$$, independently* of the other cookie. No matter which cookie the first chip lands in, there is a $$50\%$$ chance the second cookie will land in the other cookie, which means a $$50\%$$ chance of success.

What went wrong here? With the stars-and-bars approach, you are counting the number of chip distributions where each cookie has at least one chip, and dividing by the total number of chip distributions. However, the formula $$P(E)=(\text{# outcomes in }E)/(\text{# total outcomes})$$ only works when all of the outcomes are equally likely. As we saw, the outcome $$(1,1)$$ is more likely than $$(2,0)$$ and $$(0,2)$$, because it can happen two ways; either first chip falls in the left cookie and the second in the right, or vice versa. However, $$(2,0)$$ can only happen one way, with both chips in the left cookie. The fact that all four of the outcomes $$\{LL,LR,RL,RR\}$$ are equally likely is a consequence of the fact that the chips independently land in each cookie: $$P(LL)=P(L)\cdot P(L)=(1/2)\cdot (1/2)$$, and the same for $$P(LR),P(RL),$$ and $$P(RR)$$.

* We are not explicitly told that the chips independently land in each cookie uniformly at random, but this is the only reasonable assumption I can think of. Really, the key idea in resolving your mistake is that the assumption that each numerical chip distribution is equally likely contradicts the independence of the chips.

The target probability, where $$E$$ is the event that there'a at least 1 chip in each cookie, $$P(E) = 90\%$$

Since we're baking 100 cookies ...
Best-case scenario (minimum number of chips required): 1 chip per cookie i.e. 90 cookies with 1 chip each. The number of chips required $$= 90$$

Worst-case scenario (more chips are required): Cookies with more than 1 chip in them. The number of chips required $$> 90$$

So for an at least 90% probability that each cookie has at least 1 chip, the number of chips required $$\geq 90$$