Stamps problem

[Primarygun]

Would you guys show the prove of after finding that number, n

3x+5y=n+k,

x and y are non-negative integers vary with the change of k

where n and k > 0.

[psi20]

I'm not sure I understand what you're asking Primarygun. But are you saying that each different set of two stamp prices, x and y, generates a different "lowest price," n?

 

This is not true because

3 7 12

4 5 12

[Primarygun]

Concerning on our case, ax+by=n, Obviously, that's 3x1+5x1=8

The demand for x y n of them are non-negative integers

But how would you prove 3x+5y=n+k

where all the unknowns are non-negative integers.

Yes, after you had found n, you still need to prove that.

[psi20]

I'm still at a lost at what you're saying . Could you define your variables maybe? Each person uses a different variable for the same thing-- i used m and n, but others used x, y, a, b, etc.

 

The price of the stamps are going to be non-negative integers just by nature. If the stamps' prices were negative, that means that the person SELLING the stamps PAYS the buyer. As much as I would like that, it just doesn't happen, normally, in this world.

 

The number of stamps are going to be non-negative integers by nature, too. You can't buy negative stamps, unless you consider selling stamps buying negative ones. If you buy negative seven stamps, and the next day you buy ten stamps, how many stamps would you have? You don't hear questions like that everyday.

 

Because the price of "x" number of stamps = the price of 1 stamp * x

and both the price and x are positive,

the price of "x" number of stamps will be positive too.

[Primarygun]

I'm still at a lost at what you're saying . Could you define your variables maybe? Each person uses a different variable for the same thing-- i used m and n' date=' but others used x, y, a, b, etc.

 

The price of the stamps are going to be non-negative integers just by nature. If the stamps' prices were negative, that means that the person SELLING the stamps PAYS the buyer. As much as I would like that, it just doesn't happen, normally, in this world.

 

The number of stamps are going to be non-negative integers by nature, too. You can't buy negative stamps, unless you consider selling stamps buying negative ones. If you buy negative seven stamps, and the next day you buy ten stamps, how many stamps would you have? You don't hear questions like that everyday.

 

Because the price of "x" number of stamps = the price of 1 stamp * x

and both the price and x are positive,

the price of "x" number of stamps will be positive too.[/quote']

 

I knew it.

How would you prove it's 8 but not 5?

[pulkit]

I knew it.

How would you prove it's 8 but not 5?

 

An empirical formula has been put forward for :-

a) Minimum price

b) Minimum increment

c) Generation of next price

 

All three resuls being empirical do not carry any proof yet.

 

The result in part © (look at post #22) explains how to ensure positive nos of each stamp (By taking mod it ensures positive nos).

[psi20]

If you're wondering "How do you derive the formula based on other formulas and theorems?" I have no idea. But it'd be a good challenge to derive it.

If the formula does work, which I think it does because nobody can find a counter-example to it, then it means that there is exactly 1 "lowest price"

and that the interval is the GCF of the two prices.

I'm just guessing here but it might be figured out from sequences and series. After the lowest price, there's an arithmetic sequence. There's another weird sequence before it.

[pulkit]

Proving it by induction may be slightly easier than actually trying to work it out from scratch.

[Primarygun]

Yes, the difference with next price is for x and y values are 2 and -1 respectively, it can be 5 also.

I tried to prove the interval by mod 3.

But show nothing.

Pulkit,what's your process?

What's introduction, haven't learnt yet,\?

[psi20]

I'm not sure if this is a proof or some kind of flawed logic I made up, but here goes.

 

With this problem, we can see some generalizations.

One is that the possible prices continue at an interval after a certain point. The second generalization is that if a price is a factor of another price, the smaller price will be the starting point. The third generalization is the interval of possible prices after the starting point will be the greatest common factor of the two stamp prices.

 

Let m=price of one stamp, n =price of another stamp, a= greatest common factor of the stamp prices, and P = starting point.

 

A formula was found to determine the starting point of two stamps with prices m and n. This formula was :

 

(mn - a(m+n) + a^2)/a = P, where m <> n. (m does not equal n)

 

First, we show that it works for the first case. Let m = 2 and n = 3

 

(2*3 - 1(2+3) + 1^2)/1 = P and P = 2, therefore it works for the first case.

 

Next, we show that there isn't a price lower than P that is actually the starting point and works.

 

Using our third generalization, which is that the interval after the starting point is the greatest common factor of the two stamp prices, we say that

 

P - a <> xm + yn , where x and y are non-negative integers. x and y represent the number of each stamp and therefore can't be negative.

 

We're going to prove that P - a = xm + yn is wrong, therefore proving

P - a <> xm + yn

 

Assume P - a = xm + yn

 

(mn - a(m+n) + a^2)/a - a = xm + yn Because (mn - a(m+n) + a^2)/a = P

 

(mn - a(m+n) + a^2 - a^2)/a = xm + yn Because a^2/a = a

 

(mn - a(m+n))/a = xm + yn Because a^2 - a^2 = 0

 

Let m = ab and n = ac

 

(ab*ac - a(ab+ac))/a = x(ab) + y(ac) Substitution

 

(bca^2 - a(a(b+c)))/a = xab + yac Because a*a = a^2 and Distributive Prop.

 

(bca^2 - a^2(b+c))/a = xab + yac Because a*a = a^2

 

bca - a(b+c) = xab + yac By dividing by a on the left side

 

a(bc - (b+c)) = a(xb + yc) Because Distributive Prop.

 

bc - (b+c) = xb + yc Divide by a

 

bc - b - c = xb + yc Distrib. Prop.

 

b(c-1) - c = c(b-1) - b = xb + yc Distrib Prop.

 

However, this is impossible because x and y are non-negative integers.

 

Therefore , P - a <> xm + yn .

 

Hey, I think I solved it.

[e(ho0n3]

What you have done is not induction, but rather a proof by contradiction (which does the job nicely by the way). However, there is still the issue of your formula's deduction which is what I'm interested in.

[e(ho0n3]

Wait! I'm assuming that a = gcd(m,n). Your proof assumes that gcd(m,n) is the minimum increment. To make your proof valid, you need to prove that the difference between a number S (> P) and P is a multiple of gcd(m,n), i.e. S - P = (k)gcd(m,n) for some integer k > 0.

[psi20]

Yeah, that's what I just thought up.

[psi20]

I was trying to prove that P can be put into the form xm + yn where x and y are the number of stamps, m and n are the prices, and P is the lowest price. So x and y are non-negative integers whose sum is at least one.

 

(mn - a(m+n) + a^2)/a = P

 

mn/a - (m+n) + a = P

 

Let m = ab and n = ac, so a = m/b

 

mn/1/m/b - (m+n) + m/b

 

nb - m - n + m/b

 

n (b-1) + m(-1 + 1/b) ...

 

Now I'm just confused. Does that mean x = (-1 + 1/b) and y = (b-1)? That means that b <=1 for x to be non-negative. I'm sure my logic is flawed though.