## 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 thelargestnumber 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: