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. Define a standard Young tableaux of shape \(\displaystyle m\times n\) as an \(\displaystyle m\times n\) matrix with the set of entries \(\displaystyle \{1,2,\ldots,mn\}\), increasing in every row and in every column as in (ii).

Call two standard Young tableaux \(\displaystyle Y_1,Y_2\) friends, if they differ by a switch of two consecutive numbers \(\displaystyle x,x+1\) (the places of \(\displaystyle x\) and \(\displaystyle x+1\) must be not neighbouring, for such a switch preserving the monotonicity in rows and columns).

For a nice \(\displaystyle m\times n\) matrix \(\displaystyle A\) we construct a standard Young tableaux \(\displaystyle Y_A\) of shape \(\displaystyle m\times n\) as follows: if \(\displaystyle A\) has \(\displaystyle n_i\) entries equal to \(\displaystyle i\) (\(\displaystyle i=1,2,\ldots,2t\)), we replace them by the numbers from \(\displaystyle n_1+\ldots+n_{i-1}+1\) to \(\displaystyle n_1+\ldots+n_{i}\) preserving monotonicity.

Note that our \(\displaystyle Y_A\) has exactly \(\displaystyle 2t-1\) friends, where \(\displaystyle 2t\) is the number of distinct entries in \(\displaystyle A\), and moreover, every standard Young tableaux with odd number of friends corresponds to a unique nice matrix. It remains to apply the handshaking lemma (i.e., the sum of the degrees equals twice the number of edges in this graph).