Lemma › Guides › Chicken McNugget theorem: the proof and the formula
Guide

Chicken McNugget theorem: the proof and the formula

You can buy nuggets in boxes of 99 and 2020. Some totals you can make and some you cannot. The Chicken McNugget theorem says that once the box sizes are coprime, the totals you cannot make stop at a known point, and it tells you which point and how many of them there are.

The statement

Let aa and bb be positive integers with gcd⁡(a,b)=1\gcd(a, b) = 1. Call a number makeable if it equals ax+byax + by for some integers x,y≥0x, y \ge 0. Zero is makeable, with no boxes. Then:

For boxes of 99 and 2020 the largest total you cannot buy is 9⋅20−9−20=1519 \cdot 20 - 9 - 20 = 151, and exactly 8⋅192=76\frac{8 \cdot 19}{2} = 76 non-negative totals are out of reach. Everything from 152152 upward can be made.

A second example with smaller numbers: stamps of 55 and 88. The largest total you cannot make is 40−13=2740 - 13 = 27, and 4⋅72=14\frac{4 \cdot 7}{2} = 14 totals are impossible. The impossible ones are 1,2,3,4,6,7,9,11,12,14,17,19,22,271, 2, 3, 4, 6, 7, 9, 11, 12, 14, 17, 19, 22, 27. Count them and you get 1414.

Why the largest bad number is ab - a - b

Fix aa and look at numbers by their remainder when divided by aa. The multiples b⋅0,b⋅1,…,b(a−1)b \cdot 0, b \cdot 1, \dots, b(a-1) hit every remainder modulo aa exactly once, because bb is coprime to aa. That is the key fact.

Suppose n=ax+byn = ax + by is makeable. If y≥ay \ge a, swap aa boxes of size bb for bb boxes of size aa. The total does not change, so you can always arrange y≤a−1y \le a - 1. Then n≡by(moda)n \equiv by \pmod a, and since the multiples brbr hit each remainder once, yy is forced: it is the one rr with brbr in the same class as nn. So n=ax+br≥brn = ax + br \ge br. In the other direction, if n≥brn \ge br and n≡br(moda)n \equiv br \pmod a, then n−brn - br is a non-negative multiple of aa. Putting it together, a number in the class of brbr is makeable exactly when it is at least brbr.

So in the class of brbr, the numbers that are not makeable are br−a,br−2a,…br - a, br - 2a, \dots down to the first non-negative one. The largest is br−abr - a. The worst class is r=a−1r = a - 1, which gives

b(a−1)−a=ab−a−b.b(a - 1) - a = ab - a - b.

That is the largest non-makeable number.

Why there are (a-1)(b-1)/2 of them

In the class of brbr, the non-makeable numbers are br−kabr - ka for k≥1k \ge 1 while that stays non-negative. There are ⌊br/a⌋\lfloor br/a \rfloor of them, since br/abr/a is not an integer when 1≤r≤a−11 \le r \le a - 1. Adding up over the classes:

∑r=1a−1⌊bra⌋=(a−1)(b−1)2.\sum_{r=1}^{a-1} \left\lfloor \frac{br}{a} \right\rfloor = \frac{(a-1)(b-1)}{2}.

The last step writes the sum twice, once forwards and once with rr replaced by a−ra - r. Because br/abr/a and b(a−r)/ab(a-r)/a add to bb and neither is an integer, their floors add to b−1b - 1. So twice the sum is (a−1)(b−1)(a-1)(b-1).

A pairing you can use

There is a cleaner way to say all of this. Put F=ab−a−bF = ab - a - b. For every nn from 00 to FF, exactly one of nn and F−nF - n is makeable. At most one, because if both were makeable, adding them would make FF makeable, and it is not. At least one, because the non-makeable numbers number (a−1)(b−1)2\frac{(a-1)(b-1)}{2}, which is half of the F+1F + 1 numbers from 00 to FF, and each pair {n,F−n}\{n, F - n\} holds at least one of them. So each pair holds exactly one. Also FF is the last bad number, since F−F=0F - F = 0 is makeable.

You can use this as a quick test. With a=7a = 7 and b=12b = 12, F=84−19=65F = 84 - 19 = 65. Is 5959 makeable? Check 59=7⋅5+12⋅2=35+2459 = 7 \cdot 5 + 12 \cdot 2 = 35 + 24. Yes. Then 65−59=665 - 59 = 6 must not be makeable, and it is not.

Where it applies

What changes with three sizes

The theorem is for exactly two sizes. The classic textbook version has three sizes, 66, 99 and 2020. With those, the largest total you cannot make is 4343, and there is no short formula like this one. You search. The usual contest approach is to reduce to two sizes by finding a residue pattern, or to prove that everything above some small bound works by exhibiting a run of consecutive makeable numbers as long as the smallest box.

That last trick is worth knowing: if you can make aa consecutive totals and the smallest box is aa, you can make everything after them by adding boxes.

Traps

The sizes must be coprime. With boxes of 66 and 99 only multiples of 33 can be made, so infinitely many totals are out of reach and there is no largest.

If the problem requires at least one box of each size, the answer changes. Take one box of each size out first. What remains, n−a−bn - a - b, is an ordinary makeable number under the old rule, so the largest total you cannot make is F+a+b=abF + a + b = ab. For a=5a = 5 and b=8b = 8 that is 4040.

Pick two pairs of sizes, compute FF and the count from the formulas, then list the makeable numbers by hand and check both. Sorting by remainder is an example of constructive counting, and the problem archive has more practice.

Related guides

Techniques in this guide

Competitions this guide helps with

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level