### 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?

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 aij for n. Let the row sums be ri and the column sums be cj. The ri and cj 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 ∑ |ri| + ∑ |cj| = ∑L ri - ∑R ri + ∑L' cj - ∑R' cj = ∑LL' + ∑LR' - ∑RL' - ∑RR' + ∑LL' + ∑RL' - ∑LR' - ∑RR', where ∑LL' denotes the sum of aij 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 ∑ |ri| + ∑ |cj| ≤ 4k(n-k). But ∑ |ri| + ∑ |cj| = 2(1 + 2 + ... + n) - |N| = n(n+1) - |N| ≥ n2, so n2 <= 4k(n-k). But n2 - 4k(n-k) = (n - 2k)2, so if n is odd then n2 > 4k(n - k). Contradiction.