# Thread: Easy Unattainable Score Problem

1. ## Easy Unattainable Score Problem

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?

2. Originally Posted by 1337h4x
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)?)

3. Originally Posted by undefined
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?

4. Anyone have any clarity to offer?

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

$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

$c - d = fe$

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

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

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