Easy Unattainable Score Problem

Apr 2009
96
0
Hello,

My book says that there is a simple proof to provide the following, but it doesn't give it. Can someone please explain this:

Suppose there is a game in which there are two kinds of scoring events. One event gives a score of m points, and the other gives a score of n points. Assuming that m and n are relatively prime, we can derive a formula for the largest unattainable score and prove that the answer is correct.

Can anyone help derive this formula and prove that its true?
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Hello,

My book says that there is a simple proof to provide the following, but it doesn't give it. Can someone please explain this:

Suppose there is a game in which there are two kinds of scoring events. One event gives a score of m points, and the other gives a score of n points. Assuming that m and n are relatively prime, we can derive a formula for the largest unattainable score and prove that the answer is correct.

Can anyone help derive this formula and prove that its true?
I haven't looked over this too closely, but you can try this link. (Yahoo! Answers - Sylvester's Proof that g(a,b) = ab - (a+b)?)
 
  • Like
Reactions: chiph588@
Apr 2009
96
0
I haven't looked over this too closely, but you can try this link. (Yahoo! Answers - Sylvester's Proof that g(a,b) = ab - (a+b)?)

I'm confused by this guy's proof. I have only m and n in my problem, he has m and n, a and b, etc.

Could someone clarify this and make the connection to what I was asking?
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Where did you see that the other poster's proof had an n? There are a, b, x, y, m, but no n.

It is merely a choice of letter assignments, which are really arbitrary. Here your m and n are instead called a and b. When we talk of a linear combination of a and b in nonnegative integers, that can be expressed as ax + by, for nonnegative integers x and y. (Any attainable score is a linear combination of a and b.)

m is introduced by the definition of congruence. Suppose

\(\displaystyle c \equiv d\ (\text{mod }e)\)

This is true if and only if c - d is a multiple of e; that is, there exists an integer f such that

\(\displaystyle c - d = fe\)

which is the same as, there exists an integer f such that

\(\displaystyle c = d + fe\)

I still have not looked over the lattice points part, but I did not find any errors in the proof provided by the poster regarding the first part.
 
Mar 2010
1,055
290
So we need to prove two things. Given positive integers a, b with gcd(a,b)=1:

1. For all integers c > ab-a-b, there exist nonnegative integers x, y such that ax + by = c.

2. For c = ab-a-b, there are no solutions to ax + by = c in nonnegative integers.

- Hollywood