IMO 1988 SL 14

Origin: HUN

Problem

For what values of n does there exist an n \times n array of entries −1, 0, or 1 such that the 2n sums obtained by summing the elements of the rows and the columns are all different?

Solution

Consider an array [aij] of the given property and denote the sums of the rows and the columns by ri and cj respectively. Among the ri’s and cj’s, one element of [−n, n] is missing, so that there are at least n nonnegative and n nonpositive sums. By permuting rows and columns we can obtain an array in which r1, . . . , rk and c1, . . . , cn−k are nonnegative. Clearly n  i=1 |ri| + n  j=1 |cj| \geq n  r=−n |r| −n = n2. But on the other hand,

n  i=1 |ri| + n  j=1 |cj| = k  i=1 ri − n  i=k+1 ri + n−k  j=1 cj − n  j=n−k+1 cj =

 i\leqk aij −  i>k aij +  j\leqn−k aij −  j>n−k aij = = 2 k  i=1 n−k  j=1 aij −2 n  i=k+1 n  j=n−k+1 aij \leq4k(n −k). This yields n2 \leq4k(n −k), i.e., (n −2k)2 \leq0, and thus n must be even. We proceed to show by induction that for all even n an array of the given type exists. For n = 2 the array in Fig. 1 is good. Let such an n \times n array be given for some even n \geq2, with c1 = n, c2 = −n + 1, c3 = n −2, . . . , cn−1 = 2, cn = −1 and r1 = n −1, r2 = −n + 2, . . . , rn−1 = 1, rn = 0. Upon enlarging this array as indicated in Fig. 2, the positive sums are increased by 2, the nonpositive sums are decreased by 2, and the missing sums −1, 0, 1, 2 occur in the new rows and columns, so that the obtained array (n + 2) \times (n + 2) is of the same type. -1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 n \times n Fig. 1 Fig. 2