IMO 1997 SL 4

Origin: IRN

Problem

An n \times n matrix with entries from {1, 2, . . ., 2n −1} is called a coveralls matrix if for each i the union of the ith row and the ith column contains 2n −1 distinct entries. Show that: (a) There exist no coveralls matrices for n = 1997. (b) Coveralls matrices exist for infinitely many values of n.

Solution

(a) Suppose that an n \times n coveralls matrix A exists for some n > 1. Let x \in{1, 2, . . ., 2n −1} be a fixed number that does not appear on the fixed diagonal of A. Such an element must exist, since the diagonal can contain at most n different numbers. Let us call the union of the ith row and the ith column the ith cross. There are n crosses, and each of them contains exactly one x. On the other hand, each entry x of A is contained in exactly two crosses. Hence n must be even. However, 1997 is an odd number; hence no coveralls matrix exists for n = 1997. (b) For n = 2, A2 = 1 2 3 1

is a coveralls matrix. For n = 4, one such matrix is, for example, A4 = ⎡ ⎢⎢⎣ 1 2 5 6 3 1 7 5 4 6 1 2 7 4 3 1 ⎤ ⎥⎥⎦.

This construction can be generalized. Suppose that we are given an n \times n coveralls matrix An. Let Bn be the matrix obtained from An by adding 2n to each entry, and Cn the matrix obtained from Bn by replacing each diagonal entry (equal to 2n + 1 by induction) with 2n. Then the matrix A2n =

An Bn Cn An

is coveralls. To show this, suppose that i \leqn (the case i > n is similar). The ith cross is composed of the ith cross of An, the ith row of Bn, and the ith column of Cn. The ith cross of Ai covers 1, 2, . . ., 2n −1. The ith row of Bn covers all numbers of the form 2n+j, where j is covered by the ith row of An (including j = 1). Similarly, the ith column of Cn covers 2n and all numbers of the form 2n + k, where k > 1 is covered by the ith column of An. Thus we see that all numbers are accounted for in the ith cross of A2n, and hence A2n is a desired coveralls matrix. It follows that we can find a coveralls matrix whenever n is a power of 2. Second solution for part b. We construct a coveralls matrix explicitly for n = 2k. We consider the coordinates/cells of the matrix elements modulo n throughout the solution. We define the i-diagonal (0 \leqi < n) to be the set of cells of the form (j, j + i), for all j. We note that each cross contains exactly one cell from the 0-diagonal (the main diagonal) and two cells from each i-diagonal. For two cells within an i diagonal, x and y, we define x and y to be related if there exists a cross containing both x and y. Evidently, for every cell x not on the 0-diagonal there are exactly two other cells related to it. The relation thus breaks up each i-diagonal (i > 0) into cycles of length larger than 1. Due to the diagonal translational symmetry (modulo n), all the cycles within a given i-diagonal must be of equal length and thus of an even length, since n = 2k. The construction of a coveralls matrix is now obvious. We select a number, say 1, to place on all the cells of the 0-diagonal. We pair up the remaining numbers and assign each pair to an i-diagonal, say (2i, 2i+1). Going along each cycle within the i-diagonal we alternately assign values of 2i and 2i + 1. Since the cycle has an even length, a cell will be related only to a cell of a different number, and hence each cross will contain both 2i and 2i + 1.