Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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
From: Brad
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

Hi Brad,

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

for all integer values of k. (If you don't know about this, write 
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 
already the smallest positive solution.

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

Does this help?  Write back if you'd like to talk about this 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/