The chicken nugget problem

Question

A fast-food restaurant sells chicken nuggets only in boxes of 6, 9, and 20. By buying some combination of boxes, you can obtain various total nugget counts, for example $15 = 6 + 9$ , but you cannot buy exactly $7$ .

What is the largest number of nuggets that you can NOT purchase exactly?

Accepted Answer

The answer is 43. Key idea (covering a full residue system mod 6). Since 6 is one of the box sizes, if you can make six consecutive totals n, n+1, \dots, n+5, then you can make every number \ge n by adding sixes. So we only need to find, for each remainder modulo 6, the smallest achievable total with that remainder; the largest unachievable number is just below the point where all six remainders are covered. Work out the smallest achievable value in each class mod 6 (using 9s and 20s to shift the remainder, then topping up with 6s): - \equiv 0: 6 itself. Everything \ge 6 in this class works. …

The chicken nugget problem

Your answer

More Brainteasers questions