Sunday, July 12, 2009

Largest impossible score


Problem:
If two possible points in a game is p and q, what is the largest impossible score of the game which can't be achieved? Or it can't be determined? In other words, for integers p, q ≥ 0, what is the maximum number m which can't be written as a linear combination of p, q, i.e. px + qy, where, x, y ≥ 0.

Solution:
The score can only be determined when p and q are co-primes, i.e. g = GCD(a,b) = 1. Otherwise, we can only make the multiples of g and the remaining numbers can't be made which means the maximum number can't be determined, or infinite! This also covers the case if exactly one of p or q is 0.

One other required condition is p,q > 1. If anyone of p or q is 1, there is no such score which can't be achieved, i.e. answer will be 0. If p and q both are 0, we can't even make any score...

Now, we can arrange the numbers from 0 to p*q-1 in a rectangular array as follows:

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

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

We have circled the multiples of p in the above table and claim these observations:

  • There will be q circled numbers. As we have exactly p numbers in each of q columns, so each column will have exactly one circled number, i.e. multiple of p, which implies, there will be a total of q circled number in this table.

  • No two circled numbers are in same same column and there will be only one circled number in any column. For the same reason stated above, exactly one circled number in each column.

  • Any circled number is possible. This is trivial, because, the circled numbers are multiple of one of the two given numbers, i.e. in the form p*x + q*0 or p*0 + q*x.

  • Any number below the circled one in the same column is possible. We have seen any circled number is possible. A circled number is the first multiple of p in the respective column, i.e. n*p, where n ≥1, so the following numbers in the column will be: n*p + q, n*p + 2*q. n*p + 3*q, ... ... ... which are always possible.

  • Any number above the circled one in the same column is impossible. This is also explained in the previous step. As any circled number in a column is the first one which is a multiple of one element, the number above this one will be neither the multiple of any of the two numbers. So it is impossible.

  • Any number ≥ p*q is possible. As we complete p rows of the table with q columns, we already have one circled number in each column, so, any number > p*q-1 (i.e. the last element of the table) will be surely following any of the q circled numbers, so any number starting from the p+1th row, starting from p*q will be possible.


Now considering all these observations, we can see that, largest impossible number is the number just above the last circled number. The last circled number is p*q-p, i.e. 21-3 = 18 and number above it is (p*q-p)-q, i.e. 18-7 = 11. So in general, largest impossible number is: p*q - p - q.

Conclusion:
If you are given p, q :: two positive numbers, the largest number, m, which can't be expressed as a linear combination of p, q i.e. in the form px + qy, where x and y are two non-negative numbers, is p * q - p - q, when p, q > 1 and GCD(p, q) is 1 i.e. p, q are co-primes.

2 comments:

  1. any uva or spoj problem regarading this concept??

    ReplyDelete
    Replies
    1. http://www.codechef.com/problems/CHEFLUCK

      Delete