The Chicken McNuggets Puzzle

[lpetrich]

For a long time, the fast-food chain McDonald's sold its  Chicken McNuggets in packs of 6, 9, and 20. If one wants some number of these nuggets, how many of each pack would one have to buy? Are there any numbers of nuggets that one cannot get in this fashion?

• McNugget Numbers | Math Brain Teaser
• 4 piece Chicken McNuggets®: Made with White Meat Chicken | McDonald's
•  Coin problem

Variations:

A McDonald's Happy Meal includes a pack of 4. What are possible numbers from 4, 6, 9, and 20?

McDonald's now sells Chicken McNuggets in sizes of 4, 6, 10, and 20. What numbers of pairs of nuggets are possible?

If one can remove packs of nuggets in addition to adding them, what numbers are possible?

There are similar puzzles involving coins and bills (banknotes).

How many pence (pennies) can one make with the British two pence and five pence coins?

Most currency is decimal, and uses multiples like 1, 2, 5, 10, 20, 50, 100, ... so one can compose the same problem with (say) US $20 and $50 bills.

The US is a bit unusual about less than $1 value. Its coins are a penny (1c), nickel (5c), dime (10c), quarter (25c), and a half-dollar (50c).

So one can ask how many multiples of 5c can one make with dimes and quarters.

 

[lpetrich]

 List of British banknotes and coins lists numerous coins and bills from British pre-decimal currency. In that system, 12 pence (d) make 1 shilling (s), and 20 shillings make 1 pound (L). Here are the values of some of them:

• Quarter farthing: 1/16 d
• Third farthing: 1/12 d
• Half farthing: 1/8 d
• Farthing: 1/4 d
• Halfpenny: 1/2 d
• Three farthings: 3/4 d
• One penny: 1 d
• Three halfpence: 1 1/2 d = 3/2 d
• Twopence, half groat: 2 d
• Threepence: 3 d
• Groat: 4 d
• Sixpence: 6 d
• Shilling: 1 s = 12 d
• Helm, quarter noble, gold penny: 1 s 6 d = 18 d
• Two shillings, florin, quarter angel, gold penny *: 2 s = 24 d
• Half crown: 2 s 6 d = 2 s 6 d = 30 d
• Half florin, leopard: 3 s = 36 d
• Half noble, half angel: 3 s 4 d = 40 d
• Double florin: 4 s = 48 d
• Half noble *: 4 s 2 d = 50 d
• Crown of the rose: 4 s 6 d = 54 d
• Crown: 5 s = 60 d
• Quarter guinea: 5 s 3 d = 63 d
• Half angel *: 5 s 6 d = 66 d
• Double leopard: 6 s = 72 d
• Noble, angel, half mark: 6 s 8 d = 80 d
• Third guinea: 7 s = 84 d
• Rose noble, ryal, half sovereign, half pound, double crown, half laurel, half unite: 10 s = 120 d
• Half guinea: 10 s 6 d = 126 d
• Mark: 13 s 4 d = 160 d
• Spur ryal: 15 s = 180 d
• Pound, sovereign, unite, laurel, carolus, broad: 1 L = 20 s = 240 d
• Guinea: 1 L 1 s = 21 s = 252 d
• Carolus *: 1 L 3 s = 23 s = 276 d
• Rose ryal: 1 L 10 s = 30 s = 360 d
• Two pounds, two guineas: 2 L = 40 s = 480 d
• Two guineas *: 2 L 2 s = 42 s = 504 d
• Fifty shillings: 2 L 10 s = 50 s = 600 d
• Triple unite: 3 L = 60 s = 720 d
• Five pounds, five guineas: 5 L = 100 s = 1200 d
• Five guineas *: 5 L 5 s = 105 s = 1260 d

Second value is given with a *.

So there are lots of opportunities to pose this kind of puzzle with British pre-decimal currency. Like 1 pound (20 s) and 1 guinea (21 s) - What's the minimum number of shillings that can always be expressed as pounds and guineas?

 

[Swammerdami]

I've explored this topic once a decade or so, but never knew what is the BEST way to pose a specific puzzle.

Coins of $3, $4, and $21 are nice.
You can do any value up to $15 with three coins. (For $15, give $21 and receive two $3 coins in change).
You can do any value up to $(15 + 21*(N-3)) with N coins.

Other coin triplets that include $3 and $4 also have merit. With $3, $4 and $29 you can do any value up to $(12 + 29*(N-3)) with N coins.
(Substituting $30 for the $29 means you need five coins just to do $17.)

 

[lpetrich]

• Diophantine Equation -- from Wolfram MathWorld - where only integer solutions are allowed
• Frobenius Equation -- from Wolfram MathWorld - what one wants to solve here, like 2*n2 + 5*n5 = n, where n2 and n5 >= 0
• Frobenius Number -- from Wolfram MathWorld - maximum number where one cannot find a solution: n = 3
• Coin Problem -- from Wolfram MathWorld
• McNugget Number -- from Wolfram MathWorld

Wolfram Mathematica and Alpha have built-in functions FrobeniusSolve[] and FrobeniusNumber[] for solving this problem.

Named after German mathematician Ferdinand Georg Frobenius (1849-1917).


The algorithm that I use is essentially what is stated in Wikipedia.

I start with a zero total value, since that always exists: n2 = n5 = 0.

The next value is one, and attempting to add a 2d coin gives a previous number of -1. So that number has no valid solution.

The next value is two, and one can add a 2d coin to the zero solution, giving n2 = 1, n5 = 0.

The next value is three, and that also is invalid.

The next value is four, and one adds a 2d coin to the 2 solution, giving n2 = 2, n5 = 0.

The next value is five, and one adds a 5d coin to the 0 solution, giving n2 = 0, n5 = 1.

Since there are now two contiguous values, one can add a 2d coin to either the four or the five solution to give solutions for all higher integers.

In summary:
0: 0 0
1:
2: 1 0
3:
4: 2 0
5: 0 1

 

[lpetrich]

Here are some numbers for impossible sums.

The 2d-5d coin puzzle: 1, 3

The Chicken McNuggets puzzles:
6-9-20: 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43

4-6-9-20: 1, 2, 3, 5, 7, 11

6-10-20 (2): 2, 4, 8, 14

4-6-10-20 (2): 2

The pound-guinea puzzle: I won't list all the impossible numbers, but the maximum of them is 379


If one allows negative numbers, one can get every possible number. Consider 20-packs and 9-packs of Chicken McNuggets.

Take 5 20-packs and remove 11 9-packs. One nugget will remain.

Take 9 9-packs and remove 4 20-packs. One nugget will remain.