Tuesday, August 08, 2006

Another puzzle

Here's another puzzle that I found years ago posted on a lab whiteboard at MIT.
Chicken McNuggets come in 6, 9 and 20 pieces. What is the maximum number of pieces that you CANNOT buy? That is, after this number you can buy each subsequent amount with combinations of 6, 9 and 20 pieces.
OK, this puzzle doesn't include the 4 piece meal which simply degenerates after 11 pieces (hmm, could be a hint?). To be legit, I think I saw this puzzle before they introduced the 4 piece Happy Meal in 1989. Good luck!

7 comments :

Anonymous said...

Ok...here is a guess, but I think it is right. The answer is 63....and that comes from 20 + 9 + 6 added to the difference between them.... 3 + 11 + 14.

I am not s0 positive about this one, but it sort of makes sense that this would be the key.

I was able to create 64 up to 70, and I just gave up after that. (I have to get that Journal post up at some point tonight.... :-)

I didn't spend much time... so I am either way off or it was not so tough. (I'd bet on the former)

Anonymous said...

BTW: Right or wrong....I'm so glad I didn't see this while I was in class! I would have instantly fixated on it and never paid attention to one thing going on there. :-)

Angela said...

Bzzzt, 9 x 7 = 63, so that isn't the right answer.

Anonymous said...

Ok....how about 43?

How did I get that you ask ..... Hack-o-rama all the way.

At lunch I was sitting in front of a computer, so I took out the baseball bat and hacked a script together. (yes, I am a hacker and not a programmer...so it is a hack)

#!/bin/csh
#
#
foreach c6 ( 0..100 )
foreach c9 ( 0..100 )
foreach c20 ( 0..100 )
@ answer = (20 * $c20) + (9 * $c9) + (6 * $c6)
echo $answer
end
end
end

I then sorted the results, got the unique values and compared them to a list of sequential numbers.

make_seq_data.csh > a
calc.csh | sort -n | uniq > b
diff a b

The break comes at 43...with the same contents up to 3500.

At some point I am going to try and reverse engineer why this is the number....but being at work right now, I'm out of brain cycles and time.

I warned you that I was a hacker.....

Anonymous said...

So maybe my path to the solution was not so bad....here are some pages on "McNugget Numbers":

http://mathworld.wolfram.com/
McNuggetNumber.html
http://en.wikipedia.org/wiki/McNugget_number

I sort of stopped there....I started to go on to read about Greedy and reverse-Greedy Algorithms, and my brain started to get limp.

It was just not the right kind of work day to come home from and try to absorbe soemthing like that.

Angela said...

Wow, I had no idea there was a even a mathematical topic that would be called McNugget number. This has always been an interesting problem for me as I have not been able to prove the result using a true algorithm, but rather an elimination process through multiples. Here is how I explain it.

Any combination of 6 and 9 will produce a result that is divisible by 3 starting greater than 6. So

6, 9, 12, 15, 18, 21, 24, 27, etc.

are all eliminated. You can take each of these numbers and then add 20 to them, eliminating some numbers in between these multiples of 3, so

26, 29, 32, 35, 38, 41, 44, 47, etc.

are eliminated. Now you take these numbers and add twenty again and you eliminate

46, 49, 52, 55, etc.

At this point you have eliminated all numbers from 44 up, where 44 is in the 2nd list, 45 is in the first list (divisible by 3), 46 is in the 3rd list, 47 is in the 2nd list, etc. All subsequent numbers will belong to one of these lists. So the maximum number not appearing in these lists is 43.

At least this is a way for the average person to prove it without the greedy algorithm. No one would possibly want that many McNuggets anyway!

Parichino said...

I think the cleanest way to approach this is similar to Angela's solution, using modulo-3 congruence.

All integers can be divided into 3 groups; those that are 0, 1 or 2 (mod 3).

It's clear that any positive integer 6 or greater that is 0 (mod 3) can be made, using only the boxes of 6 and 9, but the proof is below.*

Then all you have to do is throw in a single 20 to create an offset of 2.
20 is 2 (mod 3) so if you include a box of 20, then you can create all the integers that are 2 (mod 3), but of course only starting at 26.

Then throw in another 20. Since 40 is 1 (mod 3) you can now create all those integers, but of course only starting at 46.

After 46, using the above methods you can generate any integer.

Counting backwards from 46...

number mod
------ ---
46 1 using 2 20's
45 0 using no 20's and only 6's and 9's
44 2 using 1 20 and some 6's and 9's
43 1 smallest number mod 1 that can be made is 46. So 43 cannot be made.

So 43 is the answer.