Maths Olympiad Prep

Library / /127 of 128

Combinatorics Difficulty 7.9 National Olympiad, round 2 Prove it Philippines

Problem:
Let nn be a positive integer. An n×nn \times n matrix (a rectangular array of numbers with nn rows and nn columns) is said to be a platinum matrix if
(i) the n2n^2 entries are integers from 11 to nn;
(ii) each row, each column, and the main diagonal (from the upper left corner to the lower right corner) contains each integer from 11 to nn exactly once; and
(iii) there exists a collection of nn entries containing each of the numbers from 11 to nn, such that no two entries lie on the same row or column, and none of which lie on the main diagonal of the matrix.
Determine all values of nn for which there exists an n×nn \times n platinum matrix.

Solution

Solution:
There is no platinum matrix for n=1n=1 and for n=2n=2. We claim that a platinum matrix exists for all integers n3n \geq 3.

Define a transversal as a collection of nn matrix entries which are taken from distinct rows and columns, and which contains each of the numbers 11 to nn.

When n3n \geq 3 is odd, we can construct an n×nn \times n platinum matrix in the following manner: First, fill up the first row with 1,n,n1,,3,21, n, n-1, \ldots, 3, 2 from left to right. Then fill up each "diagonal" (which goes up to down, left to right and wraps back to the 1st column after the nnth column) by starting with its first row entry and incrementing by 11 as we go down to the last row. From this point onwards, entries are reduced modn\bmod n, but with nn written instead of 00. For example, for n=3n=3, we have the following platinum matrix.
(132321213)=(123)+(312)+(31) \left(\begin{array}{lll} 1 & 3 & 2 \\ 3 & 2 & 1 \\ 2 & 1 & 3 \end{array}\right)=\left(\begin{array}{lll} 1 & & \\ & 2 & \\ & & 3 \end{array}\right)+\left(\begin{array}{lll} 3 & \\ & & 1 \\ 2 & & \end{array}\right)+\left(\begin{array}{ll} & \\ 3 & \\ & 1 \end{array}\right)
From the construction described, the entry in row ii, column jj (1i,jn1 \leq i, j \leq n) is aij=2ija_{ij}=2i-j (again, reduced modn\bmod n as mentioned above). For a fixed row ii, the entries for different columns jj and jj' are distinct. For a fixed column jj, the entries for different rows ii and ii' are distinct since nn is odd. The diagonal whose first row entry is 22 is a transversal; in fact, each diagonal is a transversal. Thus, the matrix is platinum.

Let n8n \geq 8 be even, so n35n-3 \geq 5 is odd. Consider the (n3)×(n3)(n-3) \times (n-3) platinum matrix, denoted by Cn3C_{n-3}, following the construction above. We start constructing our n×nn \times n platinum matrix as follows:
(Cn3C3)whereC3=(n2nn1nn1n2n1n2n) \left(\begin{array}{c|c} C_{n-3} & \\ \hline & C_3 \end{array}\right) \quad \text{where} \quad C_3=\left(\begin{array}{ccc} n-2 & n & n-1 \\ n & n-1 & n-2 \\ n-1 & n-2 & n \end{array}\right)
We then need to fill in the 3×(n3)3 \times (n-3) matrix and the (n3)×3(n-3) \times 3 matrix adjacent to Cn3C_{n-3}. To do this, from the (n3)1=n44(n-3)-1=n-4 \geq 4 diagonals of Cn3C_{n-3} other than its main diagonal, choose 33. For one of these transversals, project its entries vertically into an empty row and horizontally into an empty column, then replace all of the entries of this chosen transversal by n2n-2. Then repeat this procedure using the symbols n1n-1 and nn using the two other transversals. The resulting matrix is then a platinum matrix. Of the n44n-4 \geq 4 transversals described above for Cn3C_{n-3}, at least one has not been used yet. This, along with a "transversal" of C3C_3 other than its main diagonal, then form a transversal of the formed n×nn \times n matrix; none of the entries of this transversal are in the main diagonal. The matrix formed is thus platinum.

The following illustrates the construction for the case n=8n=8. The final matrix is platinum, with the boxed entries all off-diagonal and forming a transversal.

Figure 1

Figure 2

Lastly, consider the following matrices.
(1234341243212143)(123456536142415263241635654321362514) \left(\begin{array}{llll} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ 2 & 1 & 4 & 3 \end{array}\right) \quad \left(\begin{array}{llllll} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 3 & 6 & 1 & 4 & 2 \\ 4 & 1 & 5 & 2 & 6 & 3 \\ 2 & 4 & 1 & 6 & 3 & 5 \\ 6 & 5 & 4 & 3 & 2 & 1 \\ 3 & 6 & 2 & 5 & 1 & 4 \end{array}\right)
It is straightforward to verify that these are platinum matrices for n=4n=4 and n=6n=6.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.