The Chicken McNugget problem
Tonight's idea
McDonald's once sold Chicken McNuggets in boxes of 6, 9 and 20. You can buy 15 and 26, but not 16: nothing adds up. Which totals are possible?
Try small ones: 1 to 5 fail, 6 works, 7 and 8 fail, 9 works, 10 and 11 fail, 12 works. The failures thin out but keep coming. The picture shows them in orange.
The last failure is 43. Here is why nothing after it fails. The six totals 44 to 49 can all be made (you will check). Add a box of 6 to each and you get 50 to 55. Add another and you get 56 to 61. Every number from 44 up is one of those six plus some boxes of 6.
A run of six successes in a row, one for each remainder on dividing by 6, ends the failures for good.
The largest impossible total is the Frobenius number of the sizes. For two sizes with no common factor there is a formula (exercise 3); for three, nobody has found one.
Watch one: why 43 fails
Suppose \(43 = 20a + 9b + 6c\), with \(a, b, c\) the numbers of each box. At most two boxes of 20 fit, since three make 60. Remove them: \(a = 0\) leaves 43, \(a = 1\) leaves 23, \(a = 2\) leaves 3.
The leftover must be made from 6s and 9s, both multiples of 3, so it must be a multiple of 3. But 43 and 23 are not, and 3 is smaller than any box. So 43 is impossible. The same check on every total up to 43 finds all 22 orange dots.
Your turn
- Make each of 44, 45, 46, 47, 48 and 49 from boxes of 6, 9 and 20. Then say, in one sentence, why 50 to 55 must also be possible.
- Use the method of the example to show that 25 and 31 are impossible.
- A post office sells only 5-cent and 7-cent stamps. (a) List every postage that cannot be made exactly. (b) For two sizes \(a\) and \(b\) with no common factor, the Frobenius number is \(ab - a - b\). Check it against your list, and against sizes 3 and 5.
- Boxes of 6, 10 and 15. Any two of these share a factor, but no number bigger than 1 divides all three. Find the largest total that cannot be made. Look for six in a row, then prove the total just before the run fails.
Stretch: the 4-piece box
A box of 4 is added to 6, 9 and 20. What is the largest impossible total now, and how many fail altogether? Then, for sizes 3 and 5, pair each total \(n\) from 0 to 7 with \(7 - n\). What do you notice about each pair, and what does it say about how many fail?
Answers
- \(44 = 20 + 4 \times 6\), \(45 = 9 + 6 \times 6\), \(46 = 2 \times 20 + 6\), \(47 = 20 + 9 + 3 \times 6\), \(48 = 8 \times 6\), \(49 = 2 \times 20 + 9\). Other ways exist. Adding one box of 6 to each gives 50 to 55, and another gives 56 to 61, and so on forever.
- 25: with no 20 the leftover is 25, with one 20 it is 5. Neither is a multiple of 3, so neither can be made from 6s and 9s. 31: leftovers 31 and 11, again not multiples of 3.
- (a) 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18, 23. Twelve postages fail, and 24 to 28 are five in a row (24 = 5 + 5 + 7 + 7, 25, 26 = 5 + 7 + 7 + 7, 27 = 5 + 5 + 5 + 5 + 7, 28), so everything after 23 works. (b) \(5 \times 7 - 5 - 7 = 23\). For 3 and 5: \(15 - 3 - 5 = 7\), and indeed 1, 2, 4, 7 fail while 8 = 3 + 5, 9 and 10 start a run of three.
- 29. The run: 30 = 15 + 15, 31 = 6 + 10 + 15, 32 = 6 + 6 + 10 + 10, 33 = 6 + 6 + 6 + 15, 34 = 6 + 6 + 6 + 6 + 10, 35 = 10 + 10 + 15. Then 29: with one 15 the leftover is 14, with none it is 29. Sixes and tens only make even totals, so 29 fails; and 14 is not 6, 10, 12 or 16, so it fails too.
Stretch. With 4, 6, 9 and 20 the failures are 1, 2, 3, 5, 7 and 11: six of them, the largest 11. (After 11: 12, 13 = 4 + 9, 14, 15 = 6 + 9, which is four in a row, enough when a box of 4 exists.) For 3 and 5 the pairs are (0, 7), (1, 6), (2, 5), (3, 4), and in each pair exactly one total can be made. So exactly half of the totals from 0 to 7 fail: four of them. The same pairing works for any coprime \(a\) and \(b\), which is why the number of failures is always \(\tfrac{(a-1)(b-1)}{2}\).