Solution
Boxes of Six, Nine and Twenty
Show the problem again
A shop sells snacks only in boxes of 6, 9 and 20. An order of $n$ snacks can be filled exactly if $n = 6a + 9b + 20c$ for some nonnegative integers $a, b, c$. What is the largest $n$ that cannot be filled exactly? Give an integer.
Worked solution
The answer is 43. Sums of 6s and 9s are exactly the multiples of 3 other than 3 itself. Using 0, 1 or 2 twenties covers the three residues mod 3: numbers $\equiv 0$ need no twenty (all multiples of 3 from 6 up), numbers $\equiv 2$ need one twenty (all from 26 up), and numbers $\equiv 1$ need two twenties (all from 46 up). So the largest impossible number $\equiv 1 \pmod 3$ is 43, the largest $\equiv 2$ is 23, and the largest $\equiv 0$ is 3. Hence 43 is the largest unfillable order: 44 = 20 + 6·4, 45 = 9·5, 46 = 20·2 + 6, 47 = 20 + 27, 48 = 6·8, 49 = 40 + 9, and adding 6s covers everything beyond.
Source: The "McNugget number" problem, a classic Frobenius-problem example in wide circulation. Statement written for AxiomIQ.