Author |
Topic: Chicken nuggets (Read 5495 times) |
|
SSS
Guest
|
Here is the problem that has really been bothering me.
You go to the drive in at McDonalds and order chicken nuggets. You are told they come in boxes of 6, 9, and 20. So, if you wanted 41 chicken nuggets you would buy one box of 20, one of 9, and two of 6.
The question is, what is the greatest number of nuggets that you cannot buy?
It would be helpful if you also posted how you got the answer.
|
|
 IP Logged |
|
|
|
asterex
Guest
|
You mean it's really been bothering you since you heard it as the Car Talk Puzzler on the radio this morning, and you want us to solve it for you. That wouldn't be fair, would it?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
 |
Re: Chicken nuggets
« Reply #2 on: May 14th, 2005, 8:29pm » |
 Quote  Modify
|
C'mon, SSS, just work it through. Make a little chart of all the numbers up through, say, 100, and start systematically crossing off the ones you can buy. As long as you're careful and thorough the answer (and the reasoning behind it) should become clear fairly quickly.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Chicken nuggets
« Reply #3 on: May 16th, 2005, 2:01am » |
Quote Modify
|
A hint, once you have 6 consecutive numbers, you can get any number higher.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Chicken nuggets
« Reply #4 on: May 17th, 2005, 2:39am » |
Quote Modify
|
Actually, the largest number of nuggets you can not buy depends on your wealth. If it is not infinite (yes, it can happen, even in this forum), then I'm afraid there is no solution.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Chicken nuggets
« Reply #5 on: May 17th, 2005, 3:05am » |
Quote Modify
|
You don't need to consider more than one box of 9 since 2 boxes of 9 are the same as 3 boxes of 6.
Similarily, 3 boxes of 20 are the same as 10 boxes of 6.
Therefore, all you need to check is combinations with N boxes of 6, 0 or 1 boxes of 9 and 0 to 2 boxes of 20.
Then you can notice that 9 is the only odd number. Even numbers can be reached only without the box of 9, odd number only with it. If you cannot buy an even number M, you cannot buy M+9, an odd number and larger than M.
So you only need to consider odd numbers and combinations including the box of 9.
If you consider the numbers modulo 3, you can see that numbers = 1 mod 3 are those that can be reached only with 2 boxes of 20, and you cannot buy M, a multiple of 3, iff you cannot buy M+2*20.
Therefore you only need to consider combinations with 2 boxes of 20.
Considering now combinations wth 1 box of 9 and 2 boxes of 20, you search the largest M =
N*6+1*9+2*20, that can not be bought. That must be for N=-1. So the result is -1*6+1*9+2*20 = 43.
|
| « Last Edit: May 17th, 2005, 3:15am by Grimbal » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Chicken nuggets
« Reply #6 on: May 17th, 2005, 9:13pm » |
Quote Modify
|
There's a nice closed form solution for two numbers; what is the most efficient method for finding the answer for n numbers? I would guess that the solution requires a certain amount of brute force, but I would be curious to hear what you guys have to say on this.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Chicken nuggets
« Reply #7 on: May 19th, 2005, 4:45am » |
Quote Modify
|
on May 17th, 2005, 9:13pm, Deedlit wrote:| There's a nice closed form solution for two numbers; what is the most efficient method for finding the answer for n numbers? I would guess that the solution requires a certain amount of brute force, but I would be curious to hear what you guys have to say on this. |
|
A warmup (just to let you know I'm still around  ):
1. A solution for n=3 exists with complexity O(log(a)), where a is the smallest of three numbers;
2. For arbitrary n, the problem is NP-hard.
|
| « Last Edit: May 22nd, 2005, 11:18pm by Barukh » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Chicken nuggets
« Reply #8 on: May 21st, 2005, 8:38am » |
Quote Modify
|
on May 19th, 2005, 4:45am, Barukh wrote:
A warmup (just to let you know I'm still around ):
|
|
Good to know.
Quote:
2. For arbitrary N, the problem is NP-hard. |
|
Could you be a little more specific? which values are bounded by n, and which are fixed?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Chicken nuggets
« Reply #9 on: May 22nd, 2005, 11:40pm » |
Quote Modify
|
on May 21st, 2005, 8:38am, Deedlit wrote:| Could you be a little more specific? which values are bounded by n, and which are fixed? |
|
I had to be more careful of course… 
Let a be the smallest of n numbers, A the largest. The “NP-hardness” of the problem implies that – unless P = NP – there doesn’t exist a polynomial algorithm in n and log(A) at the same time.
If n is fixed, there exists a polynomial algorithm in log(A) [1989]. This is done by reducing the problem to “Covering an n-dimensional space with polytopes placed at lattice points”. I don’t know how practical the algorithm is, though. 
If n is variable, there is a claim of an algorithm with time complexity O(na) [2004]. The algorithm is very easy to implement. It is based on iterative computation of residue classes for a.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove