Tuesday, August 08, 2006

Another puzzle

Chicken McNuggets
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!

technorati tags:

Blogged with Flock

6 comments :

-Quentin 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)

-Quentin 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. :-)

moonfever0 said...

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

-Quentin 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.....

-Quentin 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.

moonfever0 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!

Related Posts Plugin for WordPress, Blogger...