Mcnugget numbers...?

Question

Originally chicken mcnuggets from mcdonald's could be purchased in quantities of 6, 9, or 20. If n nuggets can be ordered as a combination of 6, 9, and 20 it is called a mcnugget number. For example, 21 is a mcnugget number since one would order 2 boxes of 6 mcnuggets and one box of nine mcnuggets. Find all positive integers that are NOT mcnugget numbers, and explain how you know that the last in your list is in fact the last non mcnugget number...

This is crazy hard and i'm stumped, any help?

Answer 1

The list of non-McNugget numbers -
1,2,3,4,5, 7,8,10,11, 13, 14, 16, 17, 19,
22, 23, 25, 28, 31, 34, 37, 43,

I did it by trial and error - it is also given in wikipedia, I see.

proof:
44 - 20 + 9 + 9 + 6
45 - 9.5
46 - 20 + 20 + 6
47 - 20 + 9 + 9 + 9
48 - 9.4 + 6 + 6
49 - 20 + 20 + 9
50 - 20 + 6.5
51 - 9.5 + 6
52 - 20 + 20 + 6 + 6
53 - 20 + 9.3 + 6
54 - 9.6
55 - 20 + 20 + 9 + 6
56 - 20 + 6.6
57 - 9.5 + 6 + 6
58 - 20 + 20 + 9 + 9
59 - 20 + 9 + 6.5
60 - 20 + 20 + 20 or 6.10 etc
61 - 20 + 20 + 9 + 6 + 6
62 - 20 + 6.7
63 - 9.7

After that it repeats adding 20.

Answer 2

Wow! It turns out there is something known as the Chicken McNugget Theorem that deals with this question. Here is a link with information about the McNugget numbers:

http://en.wikipedia.org/wiki/McNugget_number

Some of theory behind it is complicated (number theory and whatnot). Still you can use logic to determine most of the non-mcnugget numbers.