Author |
Topic: Candy Boxes (Read 679 times) |
|
R
Senior Riddler
Addicted!!!
Gender: 
Posts: 502
|
 |
Candy Boxes
« on: Oct 19th, 2009, 6:48am » |
 Quote  Modify
|
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.
|
| « Last Edit: Oct 19th, 2009, 7:04am by R » |
 IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Candy Boxes
« Reply #1 on: Oct 19th, 2009, 6:53am » |
Quote Modify
|
For (1): When GCD(A,B)  1
Need clues of rest.
|
| « Last Edit: Oct 19th, 2009, 7:09am by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Candy Boxes
« Reply #2 on: Oct 19th, 2009, 11:12am » |
Quote Modify
|
(2)
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nega1sqrt
Guest
|
(3) | hidden: | The smallest number is A*B - A - B.
Look up Mcnugget numbers and Frobenius numbers. |
|
| « Last Edit: Oct 19th, 2009, 5:04pm by nega1sqrt » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Candy Boxes
« Reply #4 on: Oct 20th, 2009, 1:29am » |
Quote Modify
|
on Oct 19th, 2009, 5:03pm, nega1sqrt wrote:(3) | hidden: | The smallest number is A*B - A - B.
Look up Mcnugget numbers and Frobenius numbers. |
|
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Candy Boxes
« Reply #5 on: Oct 20th, 2009, 1:53pm » |
Quote Modify
|
on Oct 20th, 2009, 1:29am, towr wrote:
That's the largest number you can't get. |
|
How can you say that?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Candy Boxes
« Reply #6 on: Oct 20th, 2009, 2:07pm » |
Quote Modify
|
on Oct 20th, 2009, 1:53pm, R 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Candy Boxes
« Reply #7 on: Oct 20th, 2009, 2:26pm » |
Quote Modify
|
on Oct 20th, 2009, 2:07pm, 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?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Candy Boxes
« Reply #8 on: Oct 20th, 2009, 2:59pm » |
Quote Modify
|
on Oct 20th, 2009, 2:26pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nega1sqrt
Guest
|
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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Candy Boxes
« Reply #10 on: Oct 21st, 2009, 1:21am » |
Quote Modify
|
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  x < B.
See also this thread.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove