Help with a math proof...

[HonkeyDonk]

after reading this thread...i'm still confused on the question at hand.

you're saying that 9x + 16y = n, where x, y, n are all integers greater than 0. right?

so how can n have a largest value that can't be expressed in that form 9x + 16y?

How is AB -(A+B) the largest value of n? AB-(A+B) in this case is 119. what about 120? or 121, or 2000, or etc.

 

[Spencer278]

Originally posted by: eLiu

Originally posted by: Spencer278
AB-A-B cannot be represented by Ax+by should be easy
Ax+By = AB - (A+B)
Ax + by - Ab + (A+B) = 0
A(x-b) + by + A + B = 0 For this to be true b most b >= x or a=x=b=y=0

Yes...but so far the kicker is how do I show that there are no values larger than AB - (A+B). Or even...how would one derive this formula?

I don't know how to do induction on variables like that.

 

[Spencer278]

Originally posted by: HonkeyDonk
after reading this thread...i'm still confused on the question at hand.

you're saying that 9x + 16y = n, where x, y, n are all integers greater than 0. right?

so how can n have a largest value that can't be expressed in that form 9x + 16y?

How is AB -(A+B) the largest value of n? AB-(A+B) in this case is 119. what about 120? or 121, or 2000, or etc.

There is no x and y that can express 119 in this case rember x and y have to be integers greater then 0.

 

[HonkeyDonk]

Originally posted by: Spencer278

Originally posted by: HonkeyDonk
after reading this thread...i'm still confused on the question at hand.

you're saying that 9x + 16y = n, where x, y, n are all integers greater than 0. right?

so how can n have a largest value that can't be expressed in that form 9x + 16y?

How is AB -(A+B) the largest value of n? AB-(A+B) in this case is 119. what about 120? or 121, or 2000, or etc.

There is no x and y that can express 119 in this case rember x and y have to be integers greater then 0.

right, i understand that.

but what about n = 121? no x, y that are integers > 0 can be used in 9x+16y to get n to be 121?

still confused

 

[b0mbrman]

Furthermore, when A = B, the formula doesn't hold...Say A=5 and B=5...then AB - (A + B) would be 15...which can be expressed as A(2) + B(1)...this problem has issues eLiu :|

 

[HonkeyDonk]

Originally posted by: b0mbrman
Furthermore, when A = B, the formula doesn't hold...Say A=5 and B=5...then AB - (A + B) would be 15...which can be expressed as A(2) + B(1)...this problem has issues eLiu :|

ok, for this part, you can't have a=5, b=5, cuz the problem showed 9x +16y = n,

A = 9, B = 16.

but i'm still confused b/c you can have infinitely many numbers, each larger than the one before where you can't have 9x + 16y express that particular number.

so how is 119 the largest number?

 

[Cerebus451]

Originally posted by: HonkeyDonk

Originally posted by: Spencer278

Originally posted by: HonkeyDonk
after reading this thread...i'm still confused on the question at hand.

you're saying that 9x + 16y = n, where x, y, n are all integers greater than 0. right?

so how can n have a largest value that can't be expressed in that form 9x + 16y?

How is AB -(A+B) the largest value of n? AB-(A+B) in this case is 119. what about 120? or 121, or 2000, or etc.

There is no x and y that can express 119 in this case rember x and y have to be integers greater then 0.

right, i understand that.

but what about n = 121? no x, y that are integers > 0 can be used in 9x+16y to get n to be 121?

still confused

9 * 1 + 16 * 7 = 121, x = 1, y = 7, so 121 can be expressed as 9x + 16y

 

[Spencer278]

Originally posted by: HonkeyDonk

Originally posted by: Spencer278

Originally posted by: HonkeyDonk
after reading this thread...i'm still confused on the question at hand.

you're saying that 9x + 16y = n, where x, y, n are all integers greater than 0. right?

so how can n have a largest value that can't be expressed in that form 9x + 16y?

How is AB -(A+B) the largest value of n? AB-(A+B) in this case is 119. what about 120? or 121, or 2000, or etc.

There is no x and y that can express 119 in this case rember x and y have to be integers greater then 0.

right, i understand that.

but what about n = 121? no x, y that are integers > 0 can be used in 9x+16y to get n to be 121?

still confused

x = 1 y = 7
9(1) + 16(7) = 121.

To slow.

 

[LordMorpheus]

Originally posted by: eLiu
Hey all,
First of all, this isn't for homework, it's just b/c I'm curious. I was doing a math contest the other day, and one of the problems went something like this:

Given x and y, and n are non-negative integers. 9x+16y=n. Find the largest value of n that cannot be expressed in the form 9x+16y.

I didn't know a smart way to do it...so I guess and checked. However, it turns out there's a formula for this kind of stuff: the largest n that cannot be expressed by Ax+By is:

AB - (A+B)

So...I was wondering why this is/where the formula came from. Can anyone help me prove it..?

Thanks,
-Eric

hey! Thats from today's MOML!!! A fellow missourite!

and, erm, no, i can't help you prove it.

 

[HonkeyDonk]

Originally posted by: Cerebus451

Originally posted by: HonkeyDonk

Originally posted by: Spencer278

Originally posted by: HonkeyDonk
after reading this thread...i'm still confused on the question at hand.

you're saying that 9x + 16y = n, where x, y, n are all integers greater than 0. right?

so how can n have a largest value that can't be expressed in that form 9x + 16y?

How is AB -(A+B) the largest value of n? AB-(A+B) in this case is 119. what about 120? or 121, or 2000, or etc.

There is no x and y that can express 119 in this case rember x and y have to be integers greater then 0.

right, i understand that.

but what about n = 121? no x, y that are integers > 0 can be used in 9x+16y to get n to be 121?

still confused

9 * 1 + 16 * 7 = 121, x = 1, y = 7, so 121 can be expressed as 9x + 16y

hmm...guess I miscalculated that one.

edit: Ok, I see it now...any number greater than 119 can be expressed as 9x + 16y where x, y are integers >0.

I can rest in peace now.

 

[b0mbrman]

Originally posted by: HonkeyDonk

Originally posted by: b0mbrman
Furthermore, when A = B, the formula doesn't hold...Say A=5 and B=5...then AB - (A + B) would be 15...which can be expressed as A(2) + B(1)...this problem has issues eLiu :|

ok, for this part, you can't have a=5, b=5, cuz the problem showed 9x +16y = n,

A = 9, B = 16.

but i'm still confused b/c you can have infinitely many numbers, each larger than the one before where you can't have 9x + 16y express that particular number.

so how is 119 the largest number?

Think of the numbers as 9 and (9 + 7)

With 9 and (9 + 7), you can get every factor of 9, and every number that's 7 greater than a factor of 9

Double 16 and you get 32 = 3(9) + 5.

With 9 and 3(9) + 5, you can get every factor of 9 and every number >=32 that's 5 greater than a factor of 9

Triple 16 and you get 48 = 5(9) + 3

Eventually, you get all the numbers from 1 to 8 in the right edge...that's why there's a greatest number that cannot be expressed as Ax + By

 

[eLiu]

Originally posted by: b0mbrman
Furthermore, when A = B, the formula doesn't hold...Say A=5 and B=5...then AB - (A + B) would be 15...which can be expressed as A(2) + B(1)...this problem has issues eLiu :|

mmm...well in the case that A=B, then n would be infinitely large, would it not? I mean, if A=B, then the only values n that you can express will be multiples of A.

So...I'll take make another edit that excludes the A=B case.

I'm sorry this has been so unclear...the formula was given to me on an answers page to the contest--no explanation, just that the answer is 119 b/c 16*9 - (16+9) = 119.

 

[Kyteland]

Here is your solution:

BASE CASE:
120 = (3)*16 + (8)*9
121 = (7)*16 + (1)*9
122 = (2)*16 + (10)*9
123 = (6)*16 + (3)*9
124 = (1)*16 + (12)*9
125 = (5)*16 + (5)*9
126 = (0)*16 + (14)*9
127 = (4)*16 + (7)*9
128 = (8)*16 + (0)*9

INDUCTIVE STEP:
Assume for all n>128 that n=16x+9y

n+9 = 16x+9y+9
n+9 = 16x+9(y+1)

QED


Since you provided all 9 possible base cases, you have proved for all possible n>=120 that it can be represented bu that equation. Let em know if anything is unclear. I didn't expound much on the inductive step.

 

[eLiu]

Originally posted by: Kyteland
Here is your solution:

BASE CASE:
120 = (3)*16 + (8)*9
121 = (7)*16 + (1)*9
122 = (2)*16 + (10)*9
123 = (6)*16 + (3)*9
124 = (1)*16 + (12)*9
125 = (5)*16 + (5)*9
126 = (0)*16 + (14)*9
127 = (4)*16 + (7)*9
128 = (8)*16 + (0)*9

INDUCTIVE STEP:
Assume for all n>128 that n=16x+9y

n+9 = 16x+9y+9
n+9 = 16x+9(y+1)

QED


Since you provided all 9 possible base cases, you have proved for all possible n>=120 that it can be represented bu that equation. Let em know if anything is unclear. I didn't expound much on the inductive step.

Ooohhh...that makes sense 🙂 Thanks! Would there be any point to proving this thing generally? Like for any values of A and B (except where A=B)? I mean, by what you gave me I understand why it works...and for the 'general' case, it makes sense intuitively...

Also...do you know how the formula AB-(A+B) was originally generated? I mean it works in all situations (except A=B)

 

[b0mbrman]

Ok, got the general solution...

As a note, there are at least these two conditions

B>A
A/B cannot be expressed as a rational number...actually, the lowest common factor of the two numbers must be AB...

 

[Spencer278]

A(x-b) + by + A + B = 0
Assuming X = 0 so b > X we get
-AB+by +A + b =0
-A(B+1) + B(y+1) = 0 for this to be true a>y and b>x
I don't see any reason that does not work so time to start over
A(x+1) + B(y + 1) = AB Stolen from someone above
(x+1) +B/A(y+1) = B
(x+1)/B + (Y+1)/A = 1
x/b + 1/b + y/a + 1/A = 1 I still don't see it oh well time for doing other profs

 

[MikeMike]

the answer is 119.

in the key, they made a HUGE chart, 16 wide, and went down to a certain point. and then canceled out all of the multiples of 16, and the multiples of 9, then they crossed off the multiples of 3, (multiples of 9 are also multiples of 3) then they crossed of multiples of, 2 and 8.

you get left with 119, that is straight from the answer key.

we had one kid get a 6 on that OHML, he made a program for that last problem. i got a 4 (STUPID me and adding an extra 2 to the 5th question)

also, the question was stated that it had to have no non negative solutions, and a & b were different.

MIKE

 

[Spencer278]

Originally posted by: Kyteland
Here is your solution:

BASE CASE:
120 = (3)*16 + (8)*9
121 = (7)*16 + (1)*9
122 = (2)*16 + (10)*9
123 = (6)*16 + (3)*9
124 = (1)*16 + (12)*9
125 = (5)*16 + (5)*9
126 = (0)*16 + (14)*9
127 = (4)*16 + (7)*9
128 = (8)*16 + (0)*9

INDUCTIVE STEP:
Assume for all n>128 that n=16x+9y

n+9 = 16x+9y+9
n+9 = 16x+9(y+1)

QED


Since you provided all 9 possible base cases, you have proved for all possible n>=120 that it can be represented bu that equation. Let em know if anything is unclear. I didn't expound much on the inductive step.

Now do it in general with out any numbers.

 

[Kyteland]

Originally posted by: b0mbrman
Ok, got the general solution...

As a note, there are at least these two conditions

B>A
A/B cannot be expressed as a rational number...actually, the lowest common factor of the two numbers must be AB...

I think you mean A and B must be coprime, or that A/B must be in it's most reduced form.

 

[Kyteland]

Originally posted by: Spencer278

Now do it in general with out any numbers.

I don't think there is an elegant general solution. Notice that there are 9 base cases here. In general if A>B then there are B base cases. Since there is no upper limit on what A and B can be then there is no upper limit on the number of base cases.

Also there is a trick in generating the base cases. In the above case you use the fact that 4*16-7*9=1 and that -9*16+16*9=0 to generate the next case. There is no general rule to construct these numbers for any A and B.

 

[Spencer278]

Originally posted by: Kyteland

Originally posted by: Spencer278

Now do it in general with out any numbers.

I don't think there is an elegant general solution. Notice that there are 9 base cases here. In general if A>B then there are B base cases. Since there is no upper limit on what A and B can be then there is no upper limit on the number of base cases.

Also there is a trick in generating the base cases. In the above case you use the fact that 4*16-7*9=1 and that -9*16+16*9=0 to generate the next case. There is no general rule to construct these numbers for any A and B.

Yeah I know that it seems impossible to prove in general but isn't that what eLiu was asking for?

 

[b0mbrman]

eLiu, did you figure it out yet? 🙂

 

[bleeb]

That problem is too easy for the GENIUS minds at ATOT.

 

[mwliu]

Just notice this post. You can find a simple proof of this in the October's Math Magazine, titled "An algorithm to Solve the Frobenius Problem" by Robert W. Owens. Believe it or not, this question has been around for over a century. The case you asked about can be stated formally as follow:

Given a, b both integers with gcd(a,b) = 1. Find the largest number not expressible by ax+by where x and y are non-negative integers. The article above gives a very elementary proof of this. One of the first known proof of this was by J. J. Sylvester in 1884. Frobenius as subsequently asked given A={a, b, c, ...} a set of positive integers with gcd(a,b,c,...) = 1, find the largest number not expressible as a non-negative combination of A. There is no known formula for this, even for the case of only 3 numbers.

If you goto MacDonalds, you can buy McNuggets in amount of 6 pc, 9 pc, or 20 pc. What is the largest number of nuggests you can't buy? Play with this!


Good lucks,
Mark.