IMO 1997/B1 solution

IMO 1997

Problem B1

An n x n matrix whose entries come from the set S = {1, 2, ... , 2n-1} is called silver matrix if, for each i = 1, 2, ... , n, the ith row and the ith 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.

Solution

(a) If we list all the elements in the rows followed by all the elements in the columns, then we have listed every element in the array twice, so each number in S must appear an even number of times. But considering the ith row with the ith column, we have also given n complete copies of S together with an additional copy of the numbers on the diagonal. If n is odd, then each of the 2n-1 numbers appears an odd number of times in the n complete copies, and at most n numbers can have this converted to an even number by an appearance on the diagonal. So there are no silver matrices for n odd. In particular, there is no silver matrix for n = 1997.

(b) Let A_i,j be an n x n silver matrix with 1s down the main diagonal. Define the 2n x 2n matrix B_i,j with 1s down the main diagonal as follows: B_i,j = A_i,j; B_i+n,j+n = A_i,j; B_i,j+n = 2n + A_i,j; B_i+n,j = 2n + A_i,j for i not equal j and B_i+n,i = 2n. We show that B_i,j is silver. Suppose i ≤ n. Then the first half of the ith row is the ith row of A_i,j, and the top half of the ith column is the ith column of A_i,j, so between them those two parts comprise the numbers from 1 to 2n - 1. The second half of the ith row is the ith row of A_i,j with each element increased by 2n, and the bottom half of the ith column is the ith column of A_i,j with each element increased by 2n, so between them they give the numbers from 2n + 1 to 4n - 1. The only exception is that A_i+n,i = 2n instead of 2n + A_i,i. We still get 2n + A_i,i because it was in the second half of the ith row (these two parts do not have an element in common). The 2n fills the gap so that in all we get all the numbers from 1 to 4n - 1.

An exactly similar argument works for i > n. This time the second half of the row and the second half of the column (which overlap by one element) give us the numbers from 1 to 2n - 1, and the first halves (which do not overlap) give us 2n to 4n - 1. So B_i,j is silver. Hence there are an infinite number of silver matrices.

38th IMO 1997