»  Solutions to puzzles in my National Review Online Diary

  August 2005

—————————

In my August diary I posed the following brain-teaser.

A famous fast-food restaurant sells chicken nuggets in boxes of various sizes. You can buy a box of 6, a box of 9, or a box of 20. You are not allowed to buy the chicken nuggets in any other quantities, however.

Using these order sizes you can order, for example, 32 chicken nuggets. You'd order a box of 20 and two boxes of 6. However, you couldn't order 37 chicken nuggets. There is no way to make 37 from combinations of 20, 9, and 6. Try it and you'll see.

What is the largest number of chicken pieces that you can't order?

—————————

Solution

Tackle it from the point of view of a restaurant waiter making up orders.

First, note that the waiter never needs to deliver more than one box of 9 nuggets: he can exchange any set of two boxes of nine for 3 boxes of six). Also, he never needs to deliver more than 2 boxes of 20 (3 boxes of 20 can be exchanged for 10 packs of 6). We can therefore assume that all orders will be delivered as 0 or 1 box of nine, plus 0, 1 or 2 boxes of 20, plus a certain number, which I will denote N, of boxes of 6. As a result, all possible deliveries of nuggets (up to an exchange of boxes of 9 or 20 for boxes of 6) fall into one of the 6 following cases:

  6-packs     9-packs     20-packs     Number of nuggets  
 N   0   0   6N 
 N   0   1   6(N + 3) + 2 
 N   0   2   6(N + 6) + 4 
 N   1   0   6(N + 1) + 3 
 N   1   1   6(N + 4) + 5 
 N   1   2   6(N + 8) + 1 

As all the possible residues modulo 6 are covered, it is clear that for any large enough order, a solution can be found (more on this later). Also, for each value of the residue (each line of the above table), the minimum possible order can be found by setting N = 0, and the largest impossible one is this number minus 6, ergo 43.