The McNuggets Puzzle
McNuggets, the object of derision in the “Parts is parts” commercial, the subject of several comedy routines, and the source of much bad stuff in my diet from their 1984 Gold Rush until I gained the common sense not to eat unidentifiable processed deep fried from-somewhere-in-the-chicken stuff…
(McNuggets now come in an all white meat variety. I read that halal McNuggets can be found in Detroit. For today, irrelevant.)
McNuggets are the subject of one of my favorite puzzles for kids, and one that I will use several times over the next few weeks (likely this Friday with one class).
The puzzle is classic. You can google it and get the answer, no problem. But if you want to play with it here, if you want to ask questions, go ahead.
What is the largest number of McNuggets that cannot be purchased?
Originally McNuggets were sold in boxes of 6, 9, or 20. No other way.
We could get exactly 15 (a package of 9 and a package of 6) but no way to get exactly 14 (no fair buying 15 and throwing one out). We could get 60 (3 boxes of 20). Could we buy 59? Sure: 1 box of 20, 3 boxes of 9, and 2 boxes of 6.
So what is the largest number that we could not get on the nose?
JD2718 
Math ignoramus says, “Do we know the largest number? Am I missing something re this ‘infinity’ thing?” I could keep testing really big numbers, but shouldn’t there always be a higher number, at least theoretically?
Math ignoramus will go to Google for the answer now.
Well, not a terrible thought — if we only had 6 and 9, for instance, there would always be a larger number that we couldn’t get (anything not divisible by 3, for instance). It so happens, however, that when you have a set of numbers without a common factors (such as the set {6, 9, 20}) there always gets a point where you will be able to get all numbers. For instance, if at any point we have k nuggets, including a box of 6 and a box of 20, then we can get to k + 1 by trading in the box of 6 and box of 20 for 3 boxes of 9. If we could keep doing this forever, we’d be golden — of course, eventually we’ll have to run out of 20s and 6s. But at that point, we might have (for instance) 5 boxes of 9, in which case we could trade in for 2 boxes of 20 and one box of 6, etc.
As a matter of fact, one doesn’t even need the boxes of 6 in order for the answer not to be “infinity.” But adding the boxes of 6 does make the answer go down (I’m just not sure how much :-) ).
Another, perhaps better way of seeing why the answer could be (is) finite: suppose you were ever able to get six numbers in a row — say, 44, 45, 46, 47, 48 and 49, by some combinations of 6, 9 and 20. After you can do that, you’re done: adding 6 to each of them gets you every single larger number. So you just have to find a string of 6 such numbers were you can do that. One (very sub-optimal) way is using just 9s and 20s:
116 = 4*9 + 4*20
117 = 13*9
118 = 2*9 + 5*20
119 = 11*9 + 20
120 = 6*20
121 = 9*9 + 2*20
And after that, just add 6s to get every larger number in terms of 9s, 20s and 6s.
I just solved a (somewhat) related problem over at Puzzle of the Day.
But I need the McNuggets. They are what gets the high school kids engaged.
So Amelia, the answer is going to be something less than 116. I don’t know the best way to start…. Maybe try to make some numbers. We can’t get 23. Maybe work up from there?
And of course no nuggets for the munchkin, right? Home school = good food, I take it?
you’ve just made my head spin. i need a big mac…
thanks for your great blog and good luck with the students out there in the bronx.
eric from sf
I tried a bunch of random higher numbers (less than 116) on looseleaf at the dinner table: 53, 89, 107, 115, 114. They all came up McNuggetable. I am halfway to understanding JBL’s comments, but after this and physics homework, I’m just happy there’s math to keep me humble :)
So you are attacking the puzzle. Bravo and good luck.
And Eric, it’s not so bad. And thanks for the good wishes.
Jonathan
My advice is to start at the bottom. In this particular case, there are also other things we can do to help out, using particular properties of the numbers 6, 9 and 20. (Unfortunately, there is no known general solution for boxes of sizes a, b, c.) Keep reading if you want spoilers:
Using just 6 and 9, we can get all multiples of 3 larger than 3. In order to get things which are one less than a multiple of 3, we need to use a single 20. In order to get things one more than a multiple of 3, we’ll need to use two 20s. What this suggests immediately is to start looking around 40 — in particular, 43 is one more than a multiple of 3, so we need two twenties, but we can’t get the remaining 3 with any combination of 6s, 9s and 20s and so we lose. After that, we just have to work up to see if we can get the next numbers, and it turns out that we can.
Alternatively, note that any even number we can make, we can make with just 6s and 20s. (This is because we must have an even number of 9s for the sum to be even, and we can trade two 9s in for 6s, so we can trade all the 9s in for 6s and be left with 6s and 20s.) So, what’s the highest even number we can’t get? It turns out to be 34. So that means 43 is the largest odd number we can’t get, and thus we can get everything larger than or equal to 44.
Another (shorter) problem is to do the football problem. With 7 point touchdowns and 3 point field-goals, what is the largest point total that is impossible to get.
3 is possible
4 is not
5 is not
6 is possible (3-3)
7 is possible
8 is not
9 is possible (3-3-3)
10 is possible (7-3)
11 is not
12 is possible (3-3-3-3)
13 is not
14 is possible (7-7)
15 is possible (3-3-3-3-3)
16 is not
17 is possible (7-7-3)
18 is possible (3-3-3-3-3-3)
19 is not
20 is (7-7-3-3)
21 is (7-7-7)
22 is (7-3-3-3-3-3)
23 is a field goal more than 20 (possible)
24 is a field goal more than 21 (possible)
25 is a field goal more than 22 (possible)
23 is two field goals more than 20 (possible)
23 is two field goals more than 21 (possible)
23 is two field goals more than 22 (possible)
and so on. So the largest impossible one was 19 points.
JBL, I think you’re correct that there is no general solution for three box sizes. However, there *is* a general solution for coprime box sizes a and b: it is ab – a – b.
Amelia,
I see you’ve gone private. Your reasons are yours, but I was starting to enjoy reading…
Also, google shows only one use of “mcnuggetable” anywhere. Take a bow, neologist.
Nick, for a, b, c pairwise coprime, c > b > a, don’t we have ab – a – b?
For a, b where gcf(a,b) = c, the greatest multiple of c that we cannot make can be found by a/c = x, b/c = y c(xy – x – y).
I’d like to put those two together into a general solutions for the mcnuggets, but stymied so far.
I think 43 the largest non McNugget number?
44 = 20+4×6
45 = 9×5
46 = 20×2+6
47 = 20+3×9
48 = 6×8
49 = 20×2+9
This means that every bigger number can be constructed.
sorry, I saw now that the answer was given already by JBL.
Nice puzzle :-)
Re the football puzzle (#9): The answer is actually 11. You can get 13 points — it’s a touchdown and two field goals.
Thanks for the catch mizar. I looked straight at that one and didn’t see it.
Nice Puzzle
the sol: is 43
You like men