29th IMO shortlist 1988/14 solution

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?

Answer 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 < 0, then n of the sums are positive and n are non-positive. So if there are k positive row sums, then there are n-k non-positive row sums, n-k positive column sums and k non-positive column sums.

Thus whatever the value of N, we may assume that there are k row sums ≥ 0, n-k row sums ≤ 0, n-k column sums ≥ 0, and k column sums ≤ 0. Let L be the set of row indices for which the row sum is ≥ 0, and R the set for which it is ≤ 0. Similarly, let L' be the set of column indices for which the column sum is ≥ 0, and R' the set for which it is ≤ 0.

Then we have ∑ |r_i| + ∑ |c_j| = ∑_L r_i - ∑_R r_i + ∑_L' c_j - ∑_R' c_j = ∑_LL' + ∑_LR' - ∑_RL' - ∑_RR' + ∑_LL' + ∑_RL' - ∑_LR' - ∑_RR', where ∑_LL' denotes the sum of a_ij for i in L and j in L' (and similarly for the other terms) = 2 ∑_LL' - 2 ∑_RR'. But ∑_LL' and ∑_RR' each have k(n-k) terms, each of which is at most 1, so 2 ∑_LL' - 2 ∑_RR' ≤ 4k(n-k). Hence ∑ |r_i| + ∑ |c_j| ≤ 4k(n-k). But ∑ |r_i| + ∑ |c_j| = 2(1 + 2 + ... + n) - |N| = n(n+1) - |N| ≥ n², so n² <= 4k(n-k). But n² - 4k(n-k) = (n - 2k)², so if n is odd then n² > 4k(n - k). Contradiction.

29th IMO shortlist 1988