Associated Topics || Dr. Math Home || Search Dr. Math

### Greatest Impossible Score in a Game

```Date: 01/26/2003 at 12:13:10
From: M Sim
Subject: Greatest impossible score in a game

If the two values possible in a game are p and q, the greatest
impossible score is (pq - p - q). Why is it that?

Example: if two values are 3, 7. Here you can score 3, 6, 7, 9, 10,
12, 13, 14, ..... So the greatest impossible value here is 11
(3*7-3-7 = 11).
```

```
Date: 01/27/2003 at 08:42:24
From: Doctor Jacques
Subject: Re: Greatest impossible score in a game

Hello, and thank you for writing to Dr Math.

First of all, note that we must require p and q to be co-prime (to
have no common factor). Indeed, if d is a common factor, we can only
make multiples of d, and all other numbers will be impossible, without
maximum. For example, if p and q are both even, all odd numbers are
impossible.

Let us therefore assume that p and q are co-prime, and that 1 < p < q.

We can arrange the numbers from 0 to pq-1 in a rectangular array of p
rows and q columns:

0        1 ...     q-1
q       q+1....   2q-1
........
(p-1)q ...        pq -1

In this table, let us circle the multiples of p.

I will make some claims and let you try to prove them one at a time:

1. There will be q circled numbers (this is obvious).

2. No two circled numbers will be in the same column. (This results
from the fact that p and q are co-prime - do you see why?)

3. There is exactly one circled number in each column.

4. Any circled number is possible.

5. Any number below a circled number and in the same column is
possible.

6. Any number above a circled number and in the same column is
impossible.

7. Any number below the table (>= pq) is possible.

Now, if you put everything together and think about it a little, you
should be able to see that the last impossible number is the one just
above the last circled number.

For example, if p = 3 and q = 7, we have the following table:

(0)  1    2   (3)   4    5   (6)
7   8   (9)  10   11  (12)  13
14 (15)  16   17  (18)  19   20

The last circled number is 21-3 = 18, and the number above it is
18-7 = 11.

Please write back if you require further help.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 07/24/2004 at 13:21:21
Subject: diophantine equations

I have a proof that I am stuck on.  Given px + qy = n and that the
gcd(p,q) is a factor of n, prove that:

If n > pg - (p+q) there is at least 1 positive solution for x and y.
If n = pq - (p+q) there is no solution in positive integers.
If 0 <= n < pq - (p+q) there may or may not be a solution in positive
integers x and y.
```

```
Date: 07/25/2004 at 04:32:21
From: Doctor Jacques
Subject: Re: diophantine equations

I understand that "positive" includes 0.

Notice first that, if d = gcd(p,q) > 1, we can divide everything by d
and get an equivalent equation in which p and q are relatively prime.
We may therefore assume that gcd(p,q) = 1; this will simplify the
calculations.

From the theory of linear Diophantine equations, we know that,
if gcd(p,q) = 1:

* There is always a solution in integers (not necessarily positive).
This solution can be found by the Euclidean algorithm.

* If (x0, y0) is any solution, all solutions can be expressed as:

x = x0 + kq
y = y0 - kp

back).

We can observe:

* All values of x and y are arithmetic progressions with differences
q and p, respectively.

* A greater value of x corresponds to a smaller value of y.

For the first part, let us assume that there is no positive solution.
This means that, if y is the smallest positive solution, the
corresponding x will still be negative. Indeed, we cannot increase x
to make it positive, since that would require decreasing y, and y is

Let us therefore assume that x and y correspond to that solution with
the smallest y. This means that:

0 <= y <= p-1           [1]

since, otherwise, we could subtract p from y and get a smaller
positive y. As x is negative, we also have:

x <= -1                 [2]

If we multiply [1] by q and [2] by p, and add the equations, we get:

n = px + qy <= pq - (p+q)

This means that, if n does not satisfy that relation, i.e.,
if n > pq - (p+q), there will always be a positive solution.

For the second part, assume that n = pq - (p+q). We may write:

px + qy = pq - (p+q)
p(x+1) + q(y+1) = pq     [3]

As x and y are >= 0, x+1 and y+1 are > 0. The above equation shows
that x+1 is a multiple of q (as everything else is), and that y+1 is
a multiple of p. As these values are > 0, we have:

x+1 >= q
y+1 >= p

and, if you put that in equation [3], you get a contradiction, since
the left-hand side is at least equal to 2pq.

For the third part, there is, strictly speaking, nothing to prove -
the statement is equivalent to "something may be true or false". We
can say a little more by showing examples of both cases, to show that
they actually happen (unless p or q is equal to 1).

If p or q is 1, the condition reduces to n = 0, and there is a single
positive solution : x = y = 0.

If both p and q are greater than 1, we have no positive solution for
n = 1, and we have at least a positive solution for n = 0, so both
cases can happen.

There is also a more visual interpretation of this problem in our
archive, in the following article:

Greatest Impossible Score in a Game
http://mathforum.org/library/drmath/view/62084.html

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/

```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search