Found problems: 1
2024 IMC, 9
A matrix $A=(a_{ij})$ is called [i]nice[/i], 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 & 1\\2 & 2 & 2 \end{pmatrix}$ and $\begin{pmatrix} 1 & 1 & 3\\2 & 4 & 4 \end{pmatrix}$.