At a certain nation-wide fast food chain, you can get chicken nuggets in boxes of 6, 9, and 20. What is the maximum number of nuggets you could ask for such that no combination of the 3 sizes will give you exactly what you wanted?

First, once we find a run of 6 numbers that can be done, we can do all higher numbers by adding the appropriate number of six-pacs to one of those six.

Second, 6 and 9 are both divisible by 3, so to include numbers that are not divisible by three, we need at least one twenty-pac. With only one 20-pac, we can't catch numbers of the form 3a + 1, and so 37 is not possible.

Lets look at the next numbers:
38 = 20 + 2(9)
39 = 5(6) + 9
40 = 2(20)
41 = 20 + 9 + 2(6)
42 = 4(9) + 6
43 = XXXXXXXXXXX
44 = 20 + 2(9) + 6
45 = 5(9)
46 = 2(20) + 6
47 = 20 + 3(9)
48 = 4(9) + 2(6)
49 = 2(20) + 9

And we have our run of six (44 through 49). Therefore 43 is the largest number that cannot be made.

(Of course in the real world, if you were a regular customerapproached the manager and explained why you needed exactly 43, I'm sure that he would slip you an extra three in an order of 40.)

Posted by TomM on 2002-10-10 06:19:49