IMO 1997 · Problem 4

An \(n \times n\) matrix whose entries come from the set \(S=\{1,2,\ldots,2n-1\}\) is called a silver matrix if, for each \(i=1,2,\ldots,n\), the \(i\)th row and the \(i\)th column together contain all elements of \(S\). Show that

(a) there is no silver matrix for \(n=1997\);

(b) silver matrices exist for infinitely many values of \(n\).

Official text of the problem. Official problem paper (PDF)

Solution

For each \(i\), the union of the \(i\)th row and the \(i\)th column consists of exactly \(2n-1\) positions. Thus, in a silver matrix, these positions contain each element of \(S\) exactly once.

(a) Suppose a silver matrix exists. For each \(s\in S\), let \(d_s\) be the number of diagonal entries equal to \(s\), and let \(e_s\) be the number of off-diagonal entries equal to \(s\).

Count the occurrences of \(s\) in the unions of row \(i\) and column \(i\), summed over all \(i=1,\ldots,n\). Each union contains \(s\) exactly once, so the count is \(n\). Each diagonal occurrence is counted once, while an off-diagonal occurrence at position \((i,j)\) is counted twice: in the union indexed by \(i\) and in the union indexed by \(j\). Hence \[ n=d_s+2e_s. \]

If \(n=1997\), every \(d_s\) is odd and therefore at least \(1\). Consequently, \[ 1997=\sum_{s\in S}d_s\ge |S|=3993, \] a contradiction. Thus no silver matrix exists for \(n=1997\).

(b) We prove that a silver matrix exists for every \(n=2^k\), where \(k\) is a nonnegative integer.

The matrix \((1)\) is silver, giving the case \(n=1\). It remains to show how to construct a silver matrix of order \(2n\) from one of order \(n\).

Let \(A\) be a silver matrix of order \(n\). For \(1\le i,j\le n\), let \(r_{ij}\) be the remainder of \(i+j-2\) upon division by \(n\), and define \[ B_{ij}=2n+r_{ij}, \qquad C_{ij}=3n+r_{ij}. \] For any fixed row or column, the remainders \(r_{ij}\) run through \(0,1,\ldots,n-1\) exactly once. Therefore every row and every column of \(B\) contains exactly the numbers \[ 2n,2n+1,\ldots,3n-1, \] and every row and every column of \(C\) contains exactly the numbers \[ 3n,3n+1,\ldots,4n-1. \]

Consider the \(2n\times2n\) matrix \[ M= \begin{pmatrix} A&B\\ C&A \end{pmatrix}. \] All its entries belong to \(\{1,2,\ldots,4n-1\}\).

For \(1\le i\le n\), row \(i\) and column \(i\) of \(M\) together contain the corresponding row and column of the upper-left copy of \(A\), row \(i\) of \(B\), and column \(i\) of \(C\). These contain, respectively, all elements of \[ \{1,\ldots,2n-1\},\qquad \{2n,\ldots,3n-1\},\qquad \{3n,\ldots,4n-1\}. \]

Likewise, row \(n+i\) and column \(n+i\) contain the corresponding row and column of the lower-right copy of \(A\), row \(i\) of \(C\), and column \(i\) of \(B\), so they also contain all elements of \(\{1,\ldots,4n-1\}\).

Thus \(M\) is silver. Repeatedly applying this construction gives silver matrices of orders \[ 1,2,4,8,\ldots, \] proving that infinitely many orders are possible.

The solution was checked against Evan Chen's published IMO solution notes.