wu :: forums - Print Page


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

        riddles >> easy >> Candy Boxes
        
(Message started by: R on Oct 19^th, 2009, 6:48am)

Title: Candy Boxes
Post by R on Oct 19^th, 2009, 6:48am

In a shop there are sufficient numbers of two kinds boxes of candies, which contain A units and B units of candies respectively. There may exist the smallest number of units of candies such that if a client buys a number of units of candies more than or equal to that smallest number, the shop clerk doesn't need to open any boxes of candies.

(1): When doesn't the smallest number exist?
(2): What's the necessary and sufficient condition for a smallest number to exist?
(3): If the smallest number does exist, what is it ?

Ex: If there are boxes of 3 units and 5 units, the smallest number is 8.

8 = 1*3 + 1*5
9 = 3*3
10 = 2*5
11 = 2*3 + 1*5
12 = 4*3
13 = 1*3 + 2*5
14 = 3*3 + 1*5
15 = + 3*5
...

Because 7 cannot be expressed this way, the smallest number is 8.

Title: Re: Candy Boxes
Post by R on Oct 19^th, 2009, 6:53am

For (1): When [hide]GCD(A,B) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif1[/hide]
Need clues of rest.

Title: Re: Candy Boxes
Post by towr on Oct 19^th, 2009, 11:12am

(2)
[hide]GCD(A,B) = 1 is necessary and sufficient. If GCD(A,B) > 1, then you can't get anything other than multiples of GCD(A,B)

So suppose GCD(A,B) = 1 and WLOG assume A < B
If we can form A consecutive numbers, then we can get all later number as well.
Because GCD(A,B) = 1, there exist integers x >= y > 0 such that xA - yB = 1; and you can find them with an extended version of the Euclidean algorithm. (For A,B=3,5 this gives x,y=2,1)

Now we're looking for a sequence of numbers
N = pA + qB
N+1 = (p+x)A + (q-y)B
...
N+A-1 = (p+(A-1)x)A + (q-(A-1)y)B

If we take N = (A-1)y B, then we can trivially get every number that's greater (which isn't to say that this N is the minimum). So therefore a smallest number above which we can get all must also exist.[/hide]

Title: Re: Candy Boxes
Post by nega1sqrt on Oct 19^th, 2009, 5:03pm

(3) [hideb]The smallest number is A*B - A - B.
Look up Mcnugget numbers and Frobenius numbers.[/hideb]

Title: Re: Candy Boxes
Post by towr on Oct 20^th, 2009, 1:29am

on 10/19/09 at 17:03:25, nega1sqrt wrote:

(3) [hideb]The smallest number is A*B - A - B.
Look up Mcnugget numbers and Frobenius numbers.[/hideb]

That's the largest number you can't get. Which is 1 lower than the number you want.
But how do you find it and prove it? (without googling or using wikipedia etc)

Title: Re: Candy Boxes
Post by R on Oct 20^th, 2009, 1:53pm

on 10/20/09 at 01:29:15, towr wrote:

That's the largest number you can't get.

How can you say that?

Title: Re: Candy Boxes
Post by towr on Oct 20^th, 2009, 2:07pm

on 10/20/09 at 13:53:59, R wrote:

How can you say that?

3*5-3-5=7, 2*3-2-3=1, etc; you can't get those. But you can get the next number and every number after, 8,9,10,... and 2,3,4,... in the examples.

Title: Re: Candy Boxes
Post by R on Oct 20^th, 2009, 2:26pm

on 10/20/09 at 14:07:04, towr wrote:

3*5-3-5=7, 2*3-2-3=1, etc; you can't get those. But you can get the next number and every number after, 8,9,10,... and 2,3,4,... in the examples.

I meant to ask How did you conclude that? Any proof of the fact that "A*B-A-B" will be largest number you cannot represent. Or you are also looking for a proof for that?

Title: Re: Candy Boxes
Post by towr on Oct 20^th, 2009, 2:59pm

on 10/20/09 at 14:26:35, R wrote:

I meant to ask How did you conclude that? Any proof of the fact that "A*B-A-B" will be largest number you cannot represent. Or you are also looking for a proof for that?

I conclude it from the combination of the fact that nega1sqrt didn't make up his answer, and that I remember when it came up somewhere before (although I couldn't remember it). He's just off by one, due to the way the question was phrased.

Of course, it does leave the matter of proof open.
And while I'm sure wiki or google have the answer, I'll give it a think myself for now.

Title: Re: Candy Boxes
Post by nega1sqrt on Oct 20^th, 2009, 9:52pm

I can't find the proof anywhere. :'(
It can also be written as (a-1)(b-1)-1.
Does that help?
The paper is by J. J. Sylvester
This was on Wolfram MathWorld:
Sylvester, J. J. "Question 7382." Mathematical Questions from the Educational Times 41, 21, 1884.

Title: Re: Candy Boxes
Post by Eigenray on Oct 21^st, 2009, 1:21am

The key point is this: a number is not representable as Ax + By, with x,y nonnegative integers, iff it can be represented as Ax+By with y < 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x < B.

See also [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1135937010]this thread[/link].