Welcome to our community

Be a part of something great, join today!

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

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Jameson

Administrator
Staff member
Jan 26, 2012
4,040
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?
--------------------
Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Jameson

Administrator
Staff member
Jan 26, 2012
4,040
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.

Some additional comments:
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.