## Tuesday, June 16, 2015

### McNugget Numbers

 With only 2 pence and 5 pence coins, one cannot make 3 pence,  but one can make any higher amount.
McNugget Numbers are a special case of what is known as the Frobenius problem, after the mathematician Ferdinand Frobenius). The problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number.
"Various British Pennys". Licensed under CC BY-SA 3.0 via Wikipedia

By Fritz Saalfeld (Own work) [CC BY-SA 2.5

The McNuggets version of the coin problem was introduced by Henri Picciotto, who included it in his algebra textbook. Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working the problem out on a napkin. A McNugget number is the total number of McDonald's Chicken McNuggets in any number of boxes. The original boxes (prior to the introduction of the Happy Meal-sized nugget boxes) were of 6, 9, and 20 nuggets.

If you look at the numbers you can reach with boxes of 6, 9, and 20 nuggets, you notice that you can only reach multiples of 3 and multiples of 3 plus multiples of 20. So starting with 1, you can come up the the following list of numbers you cannot reach (non-McNugget numbers):

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43
At 44, you realize that the next six numbers can be reached by:

44 = 6 + 9 + 9 + 20
45 = 9 + 9 + 9 + 9 + 9
46 = 6 + 20 + 20
47 = 9 + 9 + 9 + 20
48 = 6 + 6 + 9 + 9 + 9 + 9
49 = 9 + 20 + 20

Now you know that all the numbers above these can be reached. You can add 6 to each of these six numbers and get the next six numbers. You can do this to infinity, so 43 is the largest non-McNugget Number. Anytime you can get the smallest number that number times in a row, you've got the largest non-McNugget number.

Bonus Round: Since the introduction of the 4 piece Happy Meal, what is the largest non-McNugget number. Use 4, 6, 9 and 20. Answer Below.

The answer is 11, did you get it?

Any larger integer can be obtained by adding some number of 6s to the appropriate partition above.                                                       (