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

Question

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?

Answer 1

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.

Answer 2

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$