29th IMO 1988 shortlist Problem 14 For what values of n, does there exist an n x n array of entries 0, ±1 such that all rows and columns have different sums?
n even. Solution For n = 2m we may take: 1 1 1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 -1 0 1 1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 0 Thus rows 1, 2, ... , m have sums 2m, 2m-2, 2m-4, ... , 2, and the rows m+1, m+2, ... , 2m have sums -1, -3, ... , -(2m-1). Columns 1, 2, ... , m have sums -(2m-2), -(2m-4), ... , 0, and columns m+1, ... , 2m have sums 1, 3, 5, ... , 2m-1. So we get each of the sums -(2m-1), -(2m-2), ... , -1, 0, 1, 2, ... , 2m just once. Now suppose that we have a solution a ij for n. Let the row sums be r i and the column sums be c j . The r i and c j are all different and all lie in the range -n to n. There are 2n+1 values in that range. Let the value in the range -n to n not taken by any row or column sum be N. Suppose that N = 0. Suppose there are k positive row sums. Then there are n-k negative row sums, n-k positive column sums and k negative column sums. Suppose N > 0. Then n of the sums are negative and n are non-negative. So if there are k non-negative row sums, then there are n-k negative row sums, n-k non-negative column sums and k negative column sums. Similarly, if N  4k(n - k). Contradiction. 29th IMO shortlist 1988 © John Scholesjscholes@kalva.demon.co.uk 16 Dec 2002