683 Chocolate Chips for 100 Cookies, and Why 500 Is a Coin Flip

Chocolate chips are dropped into a batch of dough, each one landing at a uniformly random spot, independently of all the others. The dough is then cut into $100$ equal cookies. How many chips do you need before you can promise, with probability $0.90$, that not one cookie comes out bare?

Most people answer a few hundred and feel safe doing it. The answer is $683$, and the reason the estimate misses is not that people are bad at arithmetic. It is that they answer a different question: how many chips make the average cookie comfortable. That question has a much smaller answer, and it is the wrong question.

Where a few hundred comes from

With $N$ chips and $100$ cookies, each cookie gets $N/100$ chips on average. Set that to something reassuring like three or five and you land on $300$ or $500$. Both feel generous. Neither is close.

At $N = 500$, so five chips per cookie on average, the exact probability that every single cookie is served is

which is a coin flip. Five chips per cookie on average, and you fail one batch in two. The average was never the constraint. The worst cookie is the constraint, and averages tell you very little about a minimum over a hundred cells.

The sharpest version of this is to take the average all the way down. Drop exactly $100$ chips, so exactly one per cookie on average, and every cookie is served only in the case where the chips happen to land one per cookie:

A perfect average, and the event has essentially probability zero. That is the whole lesson of the problem compressed into one fraction.

Start with one cookie

A single named cookie occupies a hundredth of the dough, so each chip misses it with probability $99/100$, and all $N$ chips miss it with probability $(99/100)^N$. That is the only elementary fact in the problem.

Now flip the requirement around. You want a hundred cookies to succeed at once, which means you have a hundred separate ways to fail. To hold the total failure probability near $0.10$, each individual cookie needs to fail about a hundred times less often, which is roughly once in a thousand. Solve for that and you get the right order of magnitude immediately:

One chance in a thousand per cookie, a hundred cookies, and the batch survives about nine times in ten. The reason $683$ is so much larger than $500$ is that the last few cookies are expensive. Cutting a per-cookie failure rate from one in a hundred to one in a thousand costs another $230$ chips, because you are paying for it exponentially.

The exact model

Equation (3) is a per-cookie statement, and turning it into a statement about all hundred cookies at once needs care, because the hundred failure events are not independent. If one cookie is bare, the chips that missed it landed somewhere, which makes the other cookies slightly better off. The events are negatively correlated.

Inclusion-exclusion over the set of empty cookies handles the correlation exactly. There are $\binom{m}{j}$ ways to choose $j$ cookies to be empty, and the probability that all $N$ chips avoid a given set of $j$ cookies is $(1 - j/m)^N$, so

Evaluate (4) at $m = 100$ in exact rational arithmetic and the threshold is pinned from both sides:

So $683$ is not merely sufficient, it is the smallest integer that works. The same evaluation at the higher target gives $P(915) = 0.989902$ and $P(916) = 0.990003$, so $916$ chips buy you $99$ percent.

The shape of that curve is the reason the reflex answer feels reasonable. The interesting action all happens between $400$ and $800$, which is exactly the range a guess lands in, and inside that range the probability moves faster than intuition expects.

A closed form you can solve on a whiteboard

Nobody sums equation (4) under interview conditions. The version you can actually do treats the hundred cookies as independent, which is the reasoning of the previous section written down honestly:

This is not exact, and because the empty-cookie events are negatively correlated it sits slightly above the truth. At $N = 683$ it reports $0.900786$ against the true $0.900456$, an error of $0.00033$. Small enough that it returns the same integer at both targets, which is the only thing that matters here.

And (6) inverts in one line. Asking for $\tilde P(N) \ge q$ gives

At $m = 100$ and $q = 0.90$ the right-hand side is $682.17$, so $683$. At $q = 0.99$ it is $915.93$, so $916$. Both correct, from a formula you can write down in fifteen seconds and evaluate with logarithms.

For the asymptotic behaviour, the classical coupon-collector tail says that with $N = m\ln m + cm$ chips the probability of full coverage tends to $e^{-e^{-c}}$, which inverts to

At $m = 100$ this gives $685.6$ for $q = 0.90$ and $920.5$ for $q = 0.99$, so it overshoots by three and five chips respectively. Fine for a sanity check, not good enough to name an integer, which is why the exact model is the one that owns the published number.

The average is a trap twice over

There is a second, more sophisticated wrong answer, and it is worth naming because it looks like the right kind of answer. The expected number of chips needed to cover all $100$cookies is the coupon collector's mean,

That number is correct and it answers nothing that was asked. It is a mean, not a quantile. Stopping at $519$ chips leaves you at about $58$ percent. The coverage time is skewed to the right, so its mean of $518.7$ sits above its median of $497$ and a long way below its ninetieth percentile of $683$. Reaching for (9) when the question says $90$ percent repeats the mistake that made $500$ look safe, one level up.

Fig. 2 also carries the number that makes the threshold intuitive. At $683$ chips the expected count of bare cookies is $100 \times (0.99)^{683} \approx 0.10$, which is very nearly the failure probability itself. When bare cookies are rare, they essentially never arrive in pairs, so "expected number of failures" and "probability of at least one failure" converge. That is a Poisson approximation doing quiet work, and it is why the crude reasoning of equation (3) lands so close to the exact answer.

The same question in other clothes

Fix the target at $q$ and let the number of cells $m$ grow. Equation (8) says the chip count grows like $m \ln m$, so it beats the naive $m$ by a logarithmic factor that never stops growing. Scaling the answer linearly would predict $6{,}830$ chips for a thousand cookies; equation (7) at $m = 1000$ returns $9{,}154$.

The mirror image of this question is the birthday problem, which asks when cells start colliding rather than when they finish filling. Collisions begin around $\sqrt{m}$ draws and coverage finishes around $m\ln m$, so between ten chips and seven hundred chips you pass from "two chips have probably shared a cookie" to "every cookie has probably been served". The same uniform draws, two thresholds, a factor of seventy apart.

Sources and further reading

• The occupancy problem in its general form — Balls into bins
• The identity behind equation (4) — Inclusion-exclusion principle
• Equations (8) and (9), and the tail that makes the mean misleading — Coupon collector's problem
• The mirror question — Birthday problem

Every number above was checked three ways before publication: exact rational evaluation of equation (4), the closed form (6) as an independent second model, and a seeded simulation of the actual experiment at $120{,}000$ trials per point, which returned $0.90090$ at $N = 683$ against the exact $0.900456$.