Chicken McNuggets come in packs of 6, 9 and 20.

combinatorics/coinage/mcnuggets New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Chicken McNuggets come in packs of 6, 9 and 20.  What is the largest
number of McNuggets you cannot order?  For what pack sizes x, y, z is
there such a largest number, and how can it be determined
mathematically?

-- "Enter Your Name Here" <user@host.uci.edu>, and Pete Mitchell
   <pwm@mv.mv.com>, September 1995

[ Editor: the first question is from the posting "a few of my
favorites"; the second is Pete Mitchell's. ]

Show solution

By my count it's 43.

-- Sue Garcia <sue@cray.com>

I, also, "brute forced" it to get 43; however it seems there must be
some mathematical basis for solving this, no?

Okay, here goes a systematic methodology for solving the McNugget
problem that can be applied to other values (besides 20, 9, and 6):

Take the smallest value (in this case 6).  Gear your mind to the fact
that you'll be using this a base (modulo), so in this case we're
thinking in "mod 6".  Now, divide the set of positive integers into
their respective "remainder" sets (i.e. the solution of "n mod 6"), as
follows:
  set 0:    6,12,18,24,...   (solutions for "n mod 6 = 0")
  set 1:  1,7,13,19,25,...   (solutions for "n mod 6 = 1")
  set 2:  2,8,14,20,26,...   (solutions for "n mod 6 = 2")
  set 3:  3,9,15,21,27,...   (solutions for "n mod 6 = 3")
  set 4:  4,10,16,22,28,...  (solutions for "n mod 6 = 4")
  set 5:  5,11,17,23,29,...  (solutions for "n mod 6 = 5")

It is obvious that, once we can obtain (i.e. order this quantity of) a
member of a given set, all subsequent members of that set are also
obtainable (just by tacking on more orders of 6).  Thus, the problem
reduces to establishing the smallest obtainable member of each set.

Set 0 is the trivial case since 6 is our established base.  Now, we
just check (sequentially) numbers obtainable using 9 and 20 (again,
since we're in base 6, adding 6's don't change the set, so we can
ignore it).

9 satisfies set 3.  (still need 1, 2, 4, 5)
18 (9+9) rehits set 0.  And here (if not before) we note that at *most*
  one "9" will be used, since an even number of 9's is the same as 6
  (and hence 0, in this base) and an odd number of 9's is the same as
  one 9 (and hence 3, in this base).
20 satisfies set 2.  (still need 1, 4, 5)
29 (20+9) satisfies set 5.  (still need 1, 4)
40 (20+20) satisfies set 4.  (still need 1)
49 (20+20+9) satisfies set 1. (got 'em all!)

Now, since set 1 was the last to be accounted for, and since 49 *is*
obtainable, the last *inobtainable* number is 43 (49-6).

-- Pete Mitchell <pwm@mv.mv.com>