4by12

Chicken McNuggets

McDonald’s sells its Chicken McNuggets in groups of 6, 9, and 20. What is the largest number of McNuggets you can’t buy?

Solution: I’m sure there’s a simpler solution to this, but here goes. Let , which is an amount we can buy using only boxes of 6 nuggets. Let’s see how we can ‘fill in the gaps’ between two consecutive , by removing some 6’s and replacing them with 9’s and 20’s:

• (condition: n>=3)
• (n>=1)
• (n>=6)
• (n>=4)
• (n>=8)

Note that only the first two options are original — the rest are simply combinations of the first two. So, if n is large enough (n >= 8 ), we can fill in all the gaps between and by removing some boxes of 6 nuggets, and replacing them with various combinations of 9 and 20 nuggets.

This means that, starting with , we can buy any number of nuggets. What about the numbers between and ? According to the list above, given n=7 we can create all the numbers in this range except, perhaps, .

It’s easy to see that there’s indeed no way to buy 43 nuggets: 43 itself isn’t divisable by 3, so you can’t get 43 with a combination of 6’s and 9’s. So you must use either one or two boxes of 20. But 43-20=23 is again not divisable by 3, and 43-20*2=3 is less than 6.

Hence, 43 is the largest amount of nuggets you can’t buy at McDonald’s.