wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Chicken nuggets
        
(Message started by: SSS on May 14^th, 2005, 2:26pm)

Title: Chicken nuggets
Post by SSS on May 14^th, 2005, 2:26pm

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.

Title: Re: Chicken nuggets
Post by asterex on May 14^th, 2005, 6:37pm

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?

Title: Re: Chicken nuggets
Post by SMQ on May 14^th, 2005, 8:29pm

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

Title: Re: Chicken nuggets
Post by towr on May 16^th, 2005, 2:01am

A hint, once you have 6 consecutive numbers, you can get any number higher.

Title: Re: Chicken nuggets
Post by Grimbal on May 17^th, 2005, 2:39am

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.
;)

Title: Re: Chicken nuggets
Post by Grimbal on May 17^th, 2005, 3:05am

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.

Title: Re: Chicken nuggets
Post by Deedlit on May 17^th, 2005, 9:13pm

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.

Title: Re: Chicken nuggets
Post by Barukh on May 19^th, 2005, 4:45am

on 05/17/05 at 21:13:29, Deedlit wrote:

A warmup (just to let you know I'm still around :D):

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.

Title: Re: Chicken nuggets
Post by Deedlit on May 21^st, 2005, 8:38am

on 05/19/05 at 04:45:39, Barukh wrote:

A warmup (just to let you know I'm still around :D):

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?

Title: Re: Chicken nuggets
Post by Barukh on May 22^nd, 2005, 11:40pm

on 05/21/05 at 08:38:01, 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… ;D

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.