The Frobenius Coin Problem

A shop only sells chicken nuggets in boxes of 6, 9, and 20. What's the largest number of nuggets you cannot buy exactly, using any combination of these boxes? (You can buy as many boxes of each size as you like.) This exact question is a well-known puzzle, and the general version — for coin or box denominations with no shared common factor — is the Frobenius coin problem, also called the chicken McNugget problem.

The core idea: past a certain point, every amount becomes reachable

If the denominations share a common factor greater than 1 (say, all are even), then only multiples of that factor can ever be reached, and infinitely many amounts stay permanently unreachable — no largest unreachable amount exists. But if the denominations are coprime (their greatest common divisor is 1, so together they share no common factor), a theorem guarantees that only finitely many amounts are unreachable, and there's a well-defined largest one, called the Frobenius number.

For exactly two coprime denominations $a$ and $b$, there's a clean closed-form formula for the Frobenius number:

$$g(a,b) = ab - a - b .$$

In plain English: multiply the two denominations together, then subtract each of them once — the result is the largest amount that cannot be made from any non-negative combination of $a$'s and $b$'s. No such simple closed form exists for three or more denominations (the nugget problem, with 6, 9, 20, needs a different method, shown below).

Worked example 1: two denominations, using the formula

What's the largest amount that can't be made using only 4-cent and 7-cent stamps? Since $\gcd(4,7)=1$, the formula applies directly: $g(4,7) = 4 \times 7 - 4 - 7 = 28 - 11 = 17$. Check: can you make 17 from 4s and 7s? Trying combinations — $7+7+4=18$, too big; $7+4+4=15$; $4\times4=16$; $7\times2+4\times0=14$ — none hit exactly 17, confirming it's unreachable. And 18 onward: $18=7+7+4$, $19 = 4\times3+7$, $20=4\times5$, $21=7\times3$, $22=4\times2+7\times2$, $23 = 4+4+7+4+4$... in fact once you check that 18, 19, 20, and 21 (four consecutive reachable amounts, matching the smaller denomination 4) are all achievable, every amount beyond is automatically reachable too by repeatedly adding another 4-cent stamp.

Worked example 2: three denominations (6, 9, 20), reasoning directly

With three denominations there's no simple formula, but the same "look for a run of consecutive reachable amounts as long as the smallest denomination" trick still works, using 6 as the smallest denomination — once you find 6 consecutive reachable amounts in a row, every larger amount is reachable by adding more 6s. Checking amounts: 20 (one box of 20), 26 ($20+6$), 29 ($20+9$), 32 ($20+6+6$), 38 ($20+9+9$ or $20+9+9$), 40 ($20+20$)... working carefully through the candidates near the top confirms the known answer for this puzzle: the largest unreachable amount is 43 nuggets. Every amount from 44 upward can be verified reachable (44 = 20+20+... actually $44 = 6\times4 + 20$, $45 = 9\times5$, $46 = 20+20+6$, $47=20+9+9+9$, 48=$6\times8$, and 49 = $20+20+9$ — six consecutive hits from 44–49, matching the smallest denomination 6, confirming everything beyond is reachable too).

What this means in practice

This puzzle is a clean test of whether a candidate reasons from a guarantee (a run of consecutive reachable values proves everything beyond is reachable) rather than checking amounts forever without a stopping condition — the same discipline needed to know when a numerical search or backtest sweep has covered enough ground to trust the result, versus when it's just an incomplete spot-check.