• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Help with a math proof...

E

eLiu

Diamond Member
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

edit1million: Thanks b0mbrman for pointing out a problem...I'm going to say that we will exclude the case where A is divisible by B (or vice versa). B/c in that case, n is the set of all numbers not divisible by A (or B), which has no largest value.
 
i know there is probably a simple answer to this, but wouldn't it always be that x and y are -1 and -1 in this case? that's the largest non-non-negative integer...
 
sorry...i had a brain-fart there or something...

anyway, I edited the post to reflect the correct problem. >.< sorry guys
 
Given x and y, and n are integers. 9x+16y=n. Find the largest value of n for which x and y are both non-negative integers.
Click to expand...
I don't see how there's a maximum n...

Anytime x and y get greater, n gets greater...they don't ever become negative unless 9x >n or 16y > n...
 
Originally posted by: b0mbrman
Given x and y, and n are integers. 9x+16y=n. Find the largest value of n for which x and y are both non-negative integers.
Click to expand...
I don't see how there's a maximum n...

Anytime x and y get greater, n gets greater...they don't ever become negative unless 9x >n or 16y > n...
Click to expand...

look at it again...I changed the post b/c I fouled up stating the problem massively...not sure what was going through my head.

 
You still aren't stating the problem correctly -- without additional limits (such as "32-bit unsigned") there is no largest integer. integers are an infinite set like b0mbrman says.
 
Originally posted by: eLiu
First of all, this isn't for homework, it's just b/c I'm curious.
Click to expand...
You are either a bad liar or you get a wedgie every day after school...

 
hmm interesting problem... my first guess is to try some form of pigeon hole... but yea, i'll think about it some more.
 
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
Click to expand...

You can prove using induction that all integers n greater than AB-A-B can be represented by the formula Ax+By=n. You can also prove that AB-A-B cannot be represented by that equation. QED.

 
Originally posted by: DaveSimmons
You still aren't stating the problem correctly -- without additional limits (such as "32-bit unsigned") there is no largest integer. integers are an infinite set like b0mbrman says.
Click to expand...

i think there was the limit of not being able to be expressed in that form (9x+16y)
 
Originally posted by: Kyteland
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
Click to expand...

You can prove using induction that all integers n greater than AB-A-B can be represented by the formula Ax+By=n. You can also prove that AB-A-B cannot be represented by that equation. QED.
Click to expand...

ah yes, that's good.
 
Originally posted by: DaveSimmons
You still aren't stating the problem correctly -- without additional limits (such as "32-bit unsigned") there is no largest integer. integers are an infinite set like b0mbrman says.
Click to expand...

You misunderstand the question. This is like asking what the maximum of the equation -x^2 is. Although integers have no maximum, this question does. That maximum is AB-A-B.
 
Like what he is asking is what is the greatest value of n that can't be expressed as
9x + 16y = n like
9x + 16y != 12
if x and y are non-negitive integers. Your on your own for proving that is the largest n that works but i think you could start by proving by induction that all values greater then AB-A-B work then I don't know.
 
Originally posted by: Kyteland
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
Click to expand...

You can prove using induction that all integers n greater than AB-A-B can be represented by the formula Ax+By=n. You can also prove that AB-A-B cannot be represented by that equation. QED.
Click to expand...

mm...Pwned?

haha...but seriously...if anyone figures it out (like without the QED bit), please tell me...or give me a hint for how to start.

And I'm serious--this isn't for homework. My calculus teacher from 2 years ago is also working on this thing...I'm kind of trying to race him to finish, but I doubt it'll happen (the guy's an MIT graduate...pretty bright I should think)

-Eric
 
Sounds like a fun proof to do... should be relatively easy to do using abstract algebra; I'll try to think of an easy way to show it on my way home
 
Originally posted by: DrPizza
Sounds like a fun proof to do... should be relatively easy to do using abstract algebra; I'll try to think of an easy way to show it on my way home
Click to expand...

haha...I might be taking that course next semester, but as of yet, I don't really have any experience with it.
 
Originally posted by: eLiu
Originally posted by: b0mbrman
Given x and y, and n are integers. 9x+16y=n. Find the largest value of n for which x and y are both non-negative integers.
Click to expand...
I don't see how there's a maximum n...

Anytime x and y get greater, n gets greater...they don't ever become negative unless 9x >n or 16y > n...
Click to expand...

look at it again...I changed the post b/c I fouled up stating the problem massively...not sure what was going through my head.
Click to expand...
yes...

B > A
A, 2A, 3A, ... , BA
B, 2B, 3B, ... , AB

values of n that can't be expressed by A's
n < A
kA < n < (k+1)A
(B-1)A < n < BA

values of n that can't be expressed by B's
n < B
jB < n < (j+1)B
(B-1)A < n < BA

Mlech, I don't know where I'm going and I'm tired of this...someone else finish it...

Here's something else to get you started...

Ax + By = AB - (A + B)
Ax +A + By + B = AB
A(x+1) + B(y + 1) = AB
 
Originally posted by: eLiu
Originally posted by: Kyteland
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
Click to expand...

You can prove using induction that all integers n greater than AB-A-B can be represented by the formula Ax+By=n. You can also prove that AB-A-B cannot be represented by that equation. QED.
Click to expand...

mm...Pwned?

haha...but seriously...if anyone figures it out (like without the QED bit), please tell me...or give me a hint for how to start.

And I'm serious--this isn't for homework. My calculus teacher from 2 years ago is also working on this thing...I'm kind of trying to race him to finish, but I doubt it'll happen (the guy's an MIT graduate...pretty bright I should think)

-Eric
Click to expand...

I just told you exactly how to do it. Did you ever take a logic course that taught how to do induction? We did lots of problems exactly like this. It is relatively simple to prove by induction that everything greater than AB-A-B can be represented by that equation. You will have multiple base cases. If you haven't learned induction then I don't know how to go about proving this.

 
Originally posted by: Kyteland
Originally posted by: DaveSimmons
You still aren't stating the problem correctly -- without additional limits (such as "32-bit unsigned") there is no largest integer. integers are an infinite set like b0mbrman says.
Click to expand...

You misunderstand the question. This is like asking what the maximum of the equation -x^2 is. Although integers have no maximum, this question does. That maximum is AB-A-B.
Click to expand...
No, he originally wrote the problem incorrectly...
 
Originally posted by: b0mbrman
Originally posted by: Kyteland
Originally posted by: DaveSimmons
You still aren't stating the problem correctly -- without additional limits (such as "32-bit unsigned") there is no largest integer. integers are an infinite set like b0mbrman says.
Click to expand...

You misunderstand the question. This is like asking what the maximum of the equation -x^2 is. Although integers have no maximum, this question does. That maximum is AB-A-B.
Click to expand...
No, he originally wrote the problem incorrectly...
Click to expand...
Ah, 😱
 
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
 
Originally posted by: Kyteland
Originally posted by: eLiu
Originally posted by: Kyteland
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
Click to expand...

You can prove using induction that all integers n greater than AB-A-B can be represented by the formula Ax+By=n. You can also prove that AB-A-B cannot be represented by that equation. QED.
Click to expand...

mm...Pwned?

haha...but seriously...if anyone figures it out (like without the QED bit), please tell me...or give me a hint for how to start.

And I'm serious--this isn't for homework. My calculus teacher from 2 years ago is also working on this thing...I'm kind of trying to race him to finish, but I doubt it'll happen (the guy's an MIT graduate...pretty bright I should think)

-Eric
Click to expand...

I just told you exactly how to do it. Did you ever take a logic course that taught how to do induction? We did lots of problems exactly like this. It is relatively simple to prove by induction that everything greater than AB-A-B can be represented by that equation. You will have multiple base cases. If you haven't learned induction then I don't know how to go about proving this.
Click to expand...

I know what induction is...at a very like, basic level. I don't have a whole lot of experience with it. I'm only a senior in high school. I mean, I can use induction to prove summation formulas...we used it in calculus to prove sequence convergence too. But I don't have any formal experience with it. Maybe I should just leave this one alone...?
 
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
Click to expand...

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?
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top