Nuggets

You can go to a fast food restaurant to buy chicken nuggets in 6-pack, 9-pack or 20-packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets?

Solution

Here’s another way of looking at it:

 1  2  3
 4  5  6
 7  8  9
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24
25 26 27
28 29 30
31 32 33
34 35 36
37 38 39
40 41 42
43 44 45
(and so on, to infinity)

You can get any number in the right column except 3 by adding 6s and 9s. So cross out the entire right column except 3. You can also add 20 to any crossed-out number and cross that number out. So cross out everything in column two below and including 26. Finally, by the same logic you can add 20 to the crossed-out numbers in column 2 and thereby cross out everything in column one below and including 46.

The largest number that’s left over is 43. Incidentally, cross out 20 and 40 and your map is complete.

2026 Update: The Frobenius / Chicken McNugget Theorem

The Nuggets puzzle (given package sizes of 6, 9, 20, what numbers of nuggets can you NOT order?) is a real combinatorics problem. The largest number you cannot represent as a non-negative integer linear combination of coprime integers a and b is (ab – a – b) — the Frobenius number or “coin problem.”

For the classic {6, 9, 20} case: The answer is 43 — you cannot buy exactly 43 nuggets, but you can buy any amount 44 or above. (Note: 6 and 9 share a factor of 3, so any number not divisible by 3 that is also not expressible using multiples of 20 and sums with 6/9 is unreachable.)

def representable_numbers(denominations, max_val):
    """Find all numbers representable as non-negative combinations of denominations."""
    reachable = {0}
    for num in range(1, max_val + 1):
        if any(num - d in reachable for d in denominations if num >= d):
            reachable.add(num)
    return reachable

denoms = [6, 9, 20]
reachable = representable_numbers(denoms, 100)
unreachable = [n for n in range(1, 100) if n not in reachable]
print(f"Largest unreachable: {max(unreachable)}")  # 43
print(f"Unreachable: {unreachable}")

Engineering applications: The Frobenius/coin problem appears in: memory allocator design (what block sizes to support), network packet fragmentation (what payload sizes fit within MTU constraints), and cryptographic padding schemes.