International Mathematics Competition
for University Students
2024

IMC2024: Day 2, Problem 9

Problem 9. A matrix \(\displaystyle A=(a_{ij})\) is called nice, if it has the following properties:

(i) the set of all entries of \(\displaystyle A\) is \(\displaystyle \{1,2,\ldots,2t\}\) for some integer \(\displaystyle t\);

(ii) the entries are non-decreasing in every row and in every column: \(\displaystyle a_{i,j}\leq a_{i,j+1}\) and \(\displaystyle a_{i,j}\leq a_{i+1,j}\);

(iii) equal entries can appear only in the same row or the same column: if \(\displaystyle a_{i,j}=a_{k,\ell}\), then either \(\displaystyle i=k\) or \(\displaystyle j=\ell\);

(iv) for each \(\displaystyle s=1,2,\ldots,2t-1\), there exist \(\displaystyle i\ne k\) and \(\displaystyle j\ne \ell\) such that \(\displaystyle a_{i,j}=s\) and \(\displaystyle a_{k,\ell}=s+1\).

Prove that for any positive integers \(\displaystyle m\) and \(\displaystyle n\), the number of nice \(\displaystyle m\times n\) matrices is even.

For example, the only two nice \(\displaystyle 2\times 3\) matrices are \(\displaystyle \begin{pmatrix} 1&1&1\\2&2&2 \end{pmatrix}\) and \(\displaystyle \begin{pmatrix} 1&1&3\\2&4&4 \end{pmatrix}\).

Fedor Petrov, St Petersburg State University

  Solution