# Easy Unattainable Score Problem

#### 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?

#### undefined

MHF Hall of Honor
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)?)

• [email protected]

#### 1337h4x

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?

#### 1337h4x

Anyone have any clarity to offer?

#### undefined

MHF Hall of Honor
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.

#### hollywood

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