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,\dots,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,\dots,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$ matrixes is even. For example, the only two nice $2 \times 3$ matrices are $\begin{pmatrix} 1 & 1 & 12 & 2 & 2 \end{pmatrix}$ and $\begin{pmatrix} 1 & 1 & 32 & 4 & 4 \end{pmatrix}$ .