Stamps problem

[psi20]

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.

[Aeschylus]

8, because if z = 3x + 5y, then z + 1 = 3(x +2) + 5(y - 1) = 3(x - 3) + 5(y + 2).

 

and any z greater than or equal to 8 must contain at least 1 y term or at least 3 x terms.

[psi20]

Can you generate a formula to find the lowest price, given the price of 2 stamps a and b?

[Primarygun]

Sorry, I don't understand what do "every price after that continues at an interval of 1 cent"mean?

[jordan]

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.

[Aeschylus]

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.

[Primarygun]

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

Ya I think so too. Otherwise, the answer is over several hundred cents.

And so... What's the question, can anyone tell me what it is asking?

[Aeschylus]

Ya I think so too. Otherwise' date=' the answer is over several hundred cents.

And so... What's the question, can anyone tell me what it is asking?[/quote']

 

The answer is 8 cents which I proved above.

[Aeschylus]

You can extend the solution by saying:

 

if z = nx + my is given by the smallest z that satisfies:

 

z +1 = n(x + p) + m(y - q) = n(x - r) + m(y + s)

 

Tho' I'm not 100% on this oen and I'm sure ther's a neater solution.

[psi20]

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?

[e(ho0n3]

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.

[psi20]

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.

[e(ho0n3]

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

[psi20]

No, there's a formula for finding it. Or at least the formula worked on the numbers I used to find it.

[Primarygun]

Do you still need the formula?

If you do, I try to write it for you.

But first of all, that would not be the perfect solution since I haven't learnt many algebra yet, such as quadric

[Dave]

Quadratic?

[Primarygun]

Sorry, wrong spelling, should be quadratic

[pulkit]

No, there's a formula for finding it. Or at least the formula worked on the numbers I used to find it.

 

Kindly post this formula

 

The problem (for the general case) definately seems non-trivial to me.

[psi20]

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.

[e(ho0n3]

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.

[pulkit]

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.

[e(ho0n3]

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.

[psi20]

I should go ask my teacher about it. I never approached him about whether or not he or anyone proved it.

[psi20]

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.

[pulkit]

HCF GCD and GCF are all the same thing