Greatest Impossible Score in a GameDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/