|
|
|||
| My National Review Online "Diary" column for August 2005 included the following brainteaser.
Chicken Nuggets
Problem
—————— 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?
My French pal François Charton offered the neatest solution, copied below. The answer is 43. ———————————————
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, 0, 1 or 2 boxes of 20, plus a certain amount of boxes of 6 (which I will note N). 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: 0 x 9-pack / 0 x 20-pack : 6N nuggets
1 x 9-pack / 0 x 20-pack : 6N+9 = 6(N+1)+3 nuggets
0 x 9-pack / 1 x 20-pack : 6N+20 = 6(N+3)+2 nuggets
1 x 9-pack / 1 x 20-pack : 6N+29 = 6(N+4)+5 nuggets
0 x 9-pack / 2 x 20-packs : 6N+40 = 6(N+6)+4 nuggets
1 x 9-pack / 2 x 20-packs : 6N+49 = 6(N+8)+1 nuggets where N, the number of packs of 6, is a positive number, or zero. As all the possible residuals 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 residual (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… |
||||