IMC 2024 · Problem 9

A matrix $A = (a_{ij})$ is called nice, if it has the following properties:

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

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

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

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

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

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