If Chicken McNuggets come in packs of 6, 9, and 20, what’s the largest number of McNuggets that you can’t buy?

Steve Omohundro and Peter Blicher posed this question in MIT Technology Review in May 2002, and Ken Rosato contributed a neat solution.

The answer is 43. To start, notice that we can use the 6-packs and 9-packs to piece together any multiple of 3 other than 3 itself. 43 itself is not divisible by 3, so 6-packs and 9-packs alone won’t get us there, and adding some 20-packs won’t help, since we’d have to add them to a quantity of either 23 or 3, neither of which can be assembled from packs of other sizes. So that shows that 43 itself can’t be reached.

But we still need to show that every larger number can be. Well, we can create all the larger even numbers by adding some quantity of 6-packs to either 36, 38, or 40, and each of those foundations can be assembled from the packs we have (36 = 9 + 9 + 9 + 9, 38 = 20 + 9 + 9, and 40 = 20 + 20). So that takes care of the even numbers. And adding 9 to any of these even numbers will give us any desired odd number above 43, starting with 36 + 9 = 45.

So 43 is the largest number of Chicken McNuggets that can’t be formed by combining 6-packs, 9-packs, and 20-packs.

(I think Henri Picciotto was the first to broach this arresting question, in Games magazine in 1987. Since then, McNuggets have found their way into Happy Meals in 4-piece servings, reducing the largest non–McNugget number to 11. In some countries, though, the 9-piece allotment has been increased to 10 — and in that case there is no largest such number, as no odd quantity can ever be assembled.)