# Problem of the week #53 - April 1st, 2013

Status
Not open for further replies.

#### Jameson

Staff member
At McDonald's you can order Chicken McNuggets in boxes of 6, 9, and 20. What is the largest number of nuggets that it is not possible to obtain by purchasing some combination of boxes?
--------------------

#### Jameson

Staff member
Congratulations to the following members for their correct solutions:

1) Sudharaka

Solution (from Sudharaka):
The largest number is 43. (Refer >>this<<)

This problem stems from the Frobenius Coin Problem. Since there's no explicit formula known to calculate the Frobenius number when the number of elements of a set is three or more, one way to solve this problem is to a numerical method such as the Rödseth's algorithm.

As you can see on the Wikipedia page linked above, the complete list of number of Chicken McNuggets you can't make with boxes of 6, 9 and 20 is 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43.

Here's how you can make the numbers 44-49 with 6, 9, and 20.

$$44 = 6 + 9 + 9 + 20$$
$$45 = 9 + 9 + 9 + 9 + 9$$
$$46 = 6 + 20 + 20$$
$$47 = 9 + 9 + 9 + 20$$
$$48 = 6 + 6 + 9 + 9 + 9 + 9$$
$$49 = 9 + 20 + 20$$

You can continue the sequence by adding 6 to the above list so again we see that 43 is the largest number we can't make this way.

Status
Not open for further replies.