McDonalds used to sell Chicken McNuggets in boxes of six, nine and 20, and then added a box of four McNuggets in a Happy Meal.
Your challenge is to work out the largest number of Chicken McNuggets that it is not possible to buy. That is, by purchasing any number of each of the four box sizes, in any combination, what is the largest number that you cannot buy.
Clearly you cannot buy one, two or three. Four is one box of four, but five is not possible. Six is one box of six, but seven is not possible. Eight is two boxes of four, nine is a box of nine, and ten is a box of four and a box of six.
Eleven cannot be done.
Twelve is two boxes of six, 13 is a box of four and a box of nine, 14 is two boxes of four and a box of six, and fifteen is a box of six and a box of nine.
We have now made four consecutive numbers of McNuggets and the smallest box contains four. So we can make any number by adding one or more boxes of four to twelve, 13, 14 or 15.
So eleven is the largest number of McNuggets it is not possible to buy.
Before the box of four McNuggets was introduced, things were much harder.
The answer in this case is 43. We will leave you to work out the list of numbers that can and cannot be made, as above, if you so wish.
To show that this is the highest number of McNuggets that used to be unbuyable:
44 = 6 + 9 + 9 + 20
45 = 5 * 9
46 = 6 + 20 + 20
47 = 3 * 9 + 20
48 = 6 + 6 + 4 * 9
49 = 9 + 20 + 20
So now we have six consecutive numbers and six is the smallest box, so we can make any number by adding one or more boxes to one of these six.
Generally, the largest number that can't be made from a set of other numbers is called the Frobenius number. The specific problem with McNuggets was devised by Henri Picciotto in a McDonalds, presumably whilst eating Chicken McNuggets.