Jump to content

Stamps problem


psi20

Recommended Posts

My math teacher gave us this problem.

 

You're selling stamps. One costs 3 cents and the other costs 5 cents. People can buy as many stamps as they wish. If x is how many 3 cent stamps someone buys, and y is how many 5 cent stamp someone buys, 3x + 5y represents the price of both of them. What is the lowest price of combined stamps, 3x + 5y, so that every price after that continues at an interval of 1 cent.

 

The next problem is what if you have m cent stamps and n cent stamps. What is the lowest combined price so that every price after that continues at an interval of 1 cent?

 

My English may be vague and incorrect, so tell me if you need clarification.

Link to comment
Share on other sites

You can buy so many 3 stamps and so many 5 stamps. Obviously you can't pay 1 or 2 cents for any combination. You can pay three cents (1 3cent stamp). You can't pay 4 cents, but you can pay 5 cents. After what point will every price become available through some combination of the two stamps. That is what the question is asking.

Link to comment
Share on other sites

You can buy so many 3 stamps and so many 5 stamps. Obviously you can't pay 1 or 2 cents for any combination. You can pay three cents (1 3cent stamp). You can't pay 4 cents, but you can pay 5 cents. After what point will every price become available through some combination of the two stamps. That is what the question is asking.

 

No, what does x and y equal for 7 cents then? see my post above.

Link to comment
Share on other sites

What I meant by the lowest price, Primarygun is in this example.

 

Say you sell 3 cent stamps and 5 cent stamps. It's possible for you to get 3 cents, from 1 -cent stamp. It's possible for you to get 5 cents, from 1 5-cent stamp. It's possible for you to get 8 cents, from 1 5-cent and 1 3-cent. It's possible for you to get 9 cents, from 3 3-cent stamps. It's possible to get 10 cents, from 2 5-cent stamps. It's possible for you to get 11 cents, from 2 3-cent stamps and 1 5-cent stamps. So it goes 3,5,8,9,10,11,12,13...

 

Sometimes it doesn't go by one cent intervals. Suppose you have 4-cent stamps and 10-cent stamps. It's impossible to have an it rising by one.

 

So Aeschylus, if you had 2 random numbers, you wouldn't use z +1 = n(x + p) + m(y - q) = n(x - r) + m(y + s) , but what would you use?

Link to comment
Share on other sites

Aeschylus' method is all you need. z + 1 = n(x + p) + m(y - q) implies that 1 = mp - nq. This means either mp is odd and np is even, or mp is even and np is odd, which further implies that either m is odd, or n is odd. The example with m = 4 and n = 10 won't work because they are both even.

Link to comment
Share on other sites

Sorry, I did word this problem incorrectly. The original problem didn't assume that the interval would be 1 cent. The interval could be 2 cents, 3 cents, or any cents. But you had to find the lowest price so that there's an interval after that price.

 

Anyways, I don't see how the formula works on 5 and 7.

 

So z = 5x + 7y

z + 1 = 5(x-4) + 7(y+3) = 5(x-11) + 7(y+8)

 

That means the lowest price has to have at least 4 5's or 11 5's? Now I'm confused.

Link to comment
Share on other sites

Very good counter-example. I retract what I wrote earlier. Here is another counter-example: z + 1 = 5(x + 10) + 7(y - 7).

 

I don't see any method of solving your problem other than by brute force (i.e. plugging, chugging, and looking).

Link to comment
Share on other sites

Well like I said, my math teacher gave us this problem. He said it took the teachers at the school 45 minutes to figure it out. He's really smart and all the math teachers combined took pretty long to figure it out. The math teachers tried to figure out a formula after they had the problem. They were unsuccessful. Then they did e(ho0n3 's method of "plugging, chugging, and looking." They came up with the formula after that.

 

Well, my math teacher gave us the problem without any hints. In 45 minutes, the class came up with some generalizations. One was that the numbers continue at an interval after a certain point. The second generalization, a pretty obvious one, is that if a number is a factor of another number, the smaller number will be the starting point. The third generalization is that if both numbers are even, then they will have an interval of 2, which turned out to be wrong.

 

After the class was over, I "plugged and chugged" until I had a list of about 15 sets of numbers. I came up with another generalization. The interval was the greatest common factor of the two numbers. I don't have the list anymore because I threw away the paper.

 

Actually, I'm not 100% sure this is the formula I came up with several months ago, but it works.

 

The first two numbers will be the stamps' prices and the third number is the lowest price.

 

2 3 2

2 5 4

2 7 6

2 9 8

3 4 6

3 5 8

3 7 12

3 8 14

4 5 12

 

4 6 4

4 7 18

4 9 24

...

6 8 12

6 9 6

6 10 16

...

8 10 24

...

100 263 25937

 

 

 

No, I didn't actually write out the 100 and 263 one. But this is what the formula predicts. The formula is (if you don't want to stare at those numbers and see for yourself)

 

 

 

 

(M*N/Greatest Common Factor of M and N) - (M + N) + Greatest Common Factor of M and N

 

Oh, but I do warn you, my teacher never told me whether or not I got the answer. So I don't know if that's it. And even if he did, I wouldn't have remembered.

Link to comment
Share on other sites

After reading the psi20's formula, I was reminded of something. It is a well known fact that gcd(m,n) = am + bn for some integers a and b (where m and n are both non-negative integers). Given a number of the form pm + qn, p and q being both non-negative integers, the "next" number can be constructed by adding gcd(m,n), i.e. pm + qn + gcd(m,n) = pm + qn + am + bn = (p + a)m + (q + b)n. As long as p + a and q + b are non-negative integers, then all is well.

 

The first "trick" is in finding integers a and b closest to 0 satisfying gcd(m,n) = am + bn. Let m = 8 and n = 3. gcd(8,3) = 1 = (-1)8 + (3)3, so a = -1 and b = 3. The second "trick" is to use the following formula: (|b| - 1)n + |a|m = (2)3 + (1)8 = 14, to obtain the lowest value (or price) sought.

 

I check this for a couple of cases and it seems to work (maybe somebody can prove me wrong). I don't why/how it works. Maybe someone can shed a light on this.

Link to comment
Share on other sites

After reading the psi20's formula, I was reminded of something. It is a well known fact that gcd(m,n) = am + bn for some integers a and b (where m and n are both non-negative integers). Given a number of the form pm + qn, p and q being both non-negative integers, the "next" number can be constructed by adding gcd(m,n), i.e. pm + qn + gcd(m,n) = pm + qn + am + bn = (p + a)m + (q + b)n. As long as p + a and q + b are non-negative integers, then all is well.

 

The first "trick" is in finding integers a and b closest to 0 satisfying gcd(m,n) = am + bn. Let m = 8 and n = 3. gcd(8,3) = 1 = (-1)8 + (3)3, so a = -1 and b = 3. The second "trick" is to use the following formula: (|b| - 1)n + |a|m = (2)3 + (1)8 = 14, to obtain the lowest value (or price) sought.

 

I check this for a couple of cases and it seems to work (maybe somebody can prove me wrong). I don't why/how it works. Maybe someone can shed a light on this.

 

 

Let m=6 and n=10.

Your formula would use b=-1 and a=2, hence minimum value turns out to be 12.

But if increment was in units of gcd, then 14 should be possible, which is clearly untrue.

 

Whereas psi20's formula of gcd+lcm-sum would have this lowest value as 16, beyond which every number at interval 2 can be made.

 

I would have believe that psi20's formula for least value holds (maybe it can be proved by double induction on m and n) and increments are equal to gcd of the two numbers.

Link to comment
Share on other sites

Let m=6 and n=10.

Your formula would use b=-1 and a=2' date=' hence minimum value turns out to be 12.

But if increment was in units of gcd, then 14 should be possible, which is clearly untrue.[/quote']

 

I think there is a mix up. You're suppose to let m be the bigger number. For your example, m = 10 and n = 6 so gcd(m,n) = gcd(10,6) = 2 = 10a + 6b. This means a = -1 and b = 2. Then (|b| - 1)n + |a|m = (1)6 + (1)10 = 16.

 

I have found a counter-example though. Let m = 3 and n = 2. gcd(3,2) = 1 = 3a + 2b so a = 1 and b = -1. Then (|b| - 1)n + |a|m = (0)2 + (1)3 = 3. The answer should be 2 however.

 

Another counter-example. Let m = 9 and n = 8. gcd(9,8) = 1 = 9a + 8b so a = 1 and b = -1. Then (|b| - 1)n + |a|m = (0)8 + (1)9 = 9. However, I don't see how 10 = 9p + 8q.

 

I would really like to derive psi20's formula instead of proving it. It shouldn't be too hard in my opinion.

Link to comment
Share on other sites

Oh, does GCD stand for greatest common factor? I've heard of GCF, greatest common factor, and LCD, least common denominator, but not GCD before. But then again, it's been a long time since I was taught those.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.