5th ASU 1971 Problem 1 (1) Player A writes down two rows of 10 positive integers, one under the other. The numbers must be chosen so that if a is under b and c is under d, then a + d = b + c. Player B is allowed to ask for the identity of the number in row i, column j. How many questions must he ask to be sure of determining all the numbers? (2) An m x n array of positive integers is written on the blackboard. It has the property that for any four numbers a, b, c, d with a and b in the same row, c and d in the same row, a above c (in the same column) and b above d (in the same column) we have a + d = b + c. If some numbers are wiped off, how many must be left for the table to be accurately restored?
(1) is trivial. We can write the condition as b - a = d - c, so the 10 numbers in the first row and 1 in the second row can all be chosen arbitrarily. Hence at least 11 questions are needed. But they are also sufficient. Having determined those numbers, the others immediately follow. (2). The m+n-1 numbers in the first row and first column can all be chosen arbitrarily, but are sufficient to determine all the numbers. Hence at least m+n-1 numbers must survive. 5th ASU 1971 © John Scholes jscholes@kalva.demon.co.uk 1 May 2002