Chicken McNuggets can be purchased in quantities of 6, 9, and 20 pieces. You can buy exactly 15 pieces by purchasing a 6 and a 9, but you can't buy exactly 10 McNuggets. What is the largest number of McNuggets that can NOT be purchased?

Hint 1

We need a systematic way to figure out which quantities we can purchase, so let's start out by writing down the numbers 1, 2, 3, .... We'll hope the number is not too big, maybe not bigger than 50, so write down a table

 1  2  3  4  5  6  7  8  9  10
11 12 13 ...

down through 50. Then underline each number that can be purchased. You can use this method to keep from getting lost: First underline 6, 9, and 20, because you know those can be purchased. Then move up the table to each underlined item (keeping one finger on it so you don't lose your place), and separately add 6, 9, and 20 to that item and underline the answer. So you would start by putting your finger on 6, then underlining 6 + 6 = 12, 6 + 9 = 15, and 6 + 20 = 26. Then move your finger up to the next underlined item (that's 9) and again add 6, 9, and 15. Keep going until your finger runs off the end of the table.

Hint 2

Here's what the table should look like:

 1  2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

From looking at the table we would guess that any number past 43 can be purchased, but how can we be sure? For example, can we tell from this table that 51 can be purchased?

Hint 3

Yes, we can tell that 51 can be purchased, because if we first purchase 6, we would need 45 more, and the table tells us we can purchase 45. Use the fact that we have 6 in a row that can be purchased to show that any amount greater than 43 can be purchased.

The Rest of the Solution

To purchase some larger number, start by purchasing packages of 6 until the number needed becomes 50 or less. Since we are only reducing the number needed by 6 each time, at this point we need a number in the range 45-50, and we already know that any of these numbers can be purchased.

Greatest Common Divisor of Several Numbers

When we started working on this problem, it was not obvious that that was a largest number that could not be purchased. We optimistically assumed that there really was a largest one, and in fact that it would be somewhere before 50.

What if the sizes of boxes had been 6, 9, and 21? This looks very much like the original problem, but in this case there is no largest number that cannot be purchased, no matter how far you go. Why? Because each of the sizes of a multiple of 3, and so any amount that we purchase must be a multiple of 3.

You are probably familiar with the idea of the greatest common divisor (sometimes called the greatest common factor ) of two numbers. In fact any three positive integers have a GCD too, as do any four, and so on. The GCD of several numbers is defined the same way as for two numbers: it is the largest number that exactly divides all the numbers. In the McNuggets problem we know that if the GCD of the box sizes is not 1, then there is no largest quantity that cannot be purchased (since any combination of boxes would add up to a quantity that is divisible by the GCD).

What if the GCD is 1? In the original problem we had sizes of 6, 9, and 20, and the GCD of these is 1 (even though 3 divides both 6 and 9, it does not divide all three items, so the GCD is not 3). In fact if the GCD is 1 then there is always a largest quantity that cannot be purchased. So for another example, if the boxes came in sizes of 15, 21, and 35, the GCD of all three is 1 (even though any two have a GCD that is greater than 1), and there is a largest quantity that cannot be purchased (it's 139).

To see that there always is a largest one in the GCD=1 case, we need the fact that if the GCD of several numbers is 1, then some linear integral combination of them is 1. For example,

2x6 + 1x9+(-1)x20=1

This one cannot be purchased, because we would need to purchase a negative number of 20-piece boxes, but we'll fix that in a minute. We also remember in this case that it is enough to find 6 consecutive purchasable amounts, and then everything after that will be purchasable. So, still ignoring the fact that there are some negative quantities, we can simply multiply this equation to get

2x6 + 1x9+(-1)x20=1
4x6 + 2x9+(-2)x20=2
6x6 + 3x9+(-3)x20=3
8x6 + 4x9+(-4)x20=4
10x6 + 5x9+(-5)x20=5
12x6 + 6x9+(-6)x20=6

Now we'll fix up the negative quantities. These all come from the 20-piece boxes, and if we simply add 6 of these boxes to each equations we are done:

2x6 + 1x9+5x20=121
4x6 + 2x9+4x20=122
6x6 + 3x9+3x20=123
8x6 + 4x9+2x20=123
10x6 + 5x9+1x20=125
12x6 + 6x9+0x20=126

So we know from this logic that any quantity of 120 or more can be purchased, so the largest non-purchasable quantity is 119 or less (in fact we found it was 43).

The same reasoning works for any sizes of boxes, as long as the GCD=1. We get a linear combination of the box sizes for each number from 1 up through the smallest box size, then adjust the combinations to make all the quantities positive.

References

Oystein Ore, Number Theory and its History, Dover reprint, 1988, pp. 153 and following. All about GCD of several numbers, how to find the linear combinations that give the GCD, and how to solve linear equations in several integer variables.
Click here to view the original problem submitted by Frances.