You can buy nuggets in boxes of and . 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 and be positive integers with . Call a number makeable if it equals for some integers . Zero is makeable, with no boxes. Then:
- The largest number that is not makeable is .
- The number of non-negative integers that are not makeable is .
For boxes of and the largest total you cannot buy is , and exactly non-negative totals are out of reach. Everything from upward can be made.
A second example with smaller numbers: stamps of and . The largest total you cannot make is , and totals are impossible. The impossible ones are . Count them and you get .
Why the largest bad number is ab - a - b
Fix and look at numbers by their remainder when divided by . The multiples hit every remainder modulo exactly once, because is coprime to . That is the key fact.
Suppose is makeable. If , swap boxes of size for boxes of size . The total does not change, so you can always arrange . Then , and since the multiples hit each remainder once, is forced: it is the one with in the same class as . So . In the other direction, if and , then is a non-negative multiple of . Putting it together, a number in the class of is makeable exactly when it is at least .
So in the class of , the numbers that are not makeable are down to the first non-negative one. The largest is . The worst class is , which gives
That is the largest non-makeable number.
Why there are (a-1)(b-1)/2 of them
In the class of , the non-makeable numbers are for while that stays non-negative. There are of them, since is not an integer when . Adding up over the classes:
The last step writes the sum twice, once forwards and once with replaced by . Because and add to and neither is an integer, their floors add to . So twice the sum is .
A pairing you can use
There is a cleaner way to say all of this. Put . For every from to , exactly one of and is makeable. At most one, because if both were makeable, adding them would make makeable, and it is not. At least one, because the non-makeable numbers number , which is half of the numbers from to , and each pair holds at least one of them. So each pair holds exactly one. Also is the last bad number, since is makeable.
You can use this as a quick test. With and , . Is makeable? Check . Yes. Then must not be makeable, and it is not.
Where it applies
- Coin and stamp problems with two denominations. "What is the largest amount you cannot pay with coins of and ?" is the theorem directly.
- Problems that need a bound after which everything works. If a construction for always extends to one for and for , and it works for , then it works for every makeable . By the theorem that is every .
- Proofs about every sufficiently large number. You need the threshold, and the theorem gives it in one line.
What changes with three sizes
The theorem is for exactly two sizes. The classic textbook version has three sizes, , and . With those, the largest total you cannot make is , 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 consecutive totals and the smallest box is , you can make everything after them by adding boxes.
Traps
The sizes must be coprime. With boxes of and only multiples of 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, , is an ordinary makeable number under the old rule, so the largest total you cannot make is . For and that is .
Pick two pairs of sizes, compute 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
- Inclusion-exclusion principle in competition mathHow inclusion-exclusion counts a union, why the signs work, and four problem types it solves: divisibility, derangements, surjections and totients.
- Stars and bars: counting solutions, with the trapsStars and bars counts the ways to split n identical objects into k boxes. Both formulas, the shift for minimums, the cap trap, and worked examples.
- Constructive vs complementary counting: which one to reach forTwo ways to count the same set, and one question that tells you which is cheaper. The signals, the worked pair, and the trap where the obvious tell lies to you.
- Generating functions: turning a counting problem into a productGenerating functions explained as a method: one factor per constraint, multiply, read the coefficient. The dictionary, and how to extract by hand.
- How a double counting proof is actually builtDouble counting proofs are always the same three steps, and only one of them is hard. The skeleton, five worked examples, and where they go wrong.
Techniques in this guide
- Constructive Counting & OvercountingBuild the object step by step, then divide by what you repeated.
Competitions this guide helps with
- MATHCOUNTSfour rounds: Sprint (30 problems), Target (8 problems in four pairs), Team (10 problems) and the oral Countdown · Sprint 40 minutes; Target 6 minutes a pair; Team 20 minutes
- Australian Mathematics Competition30 questions: 25 multiple choice, then 5 with a whole-number answer · 75 minutes for the secondary divisions, 60 for primary
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