| |||||||||||||||

## IMC2024: Day 2, Problem 9
(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
Call two standard Young tableaux \(\displaystyle Y_1,Y_2\) 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). | |||||||||||||||

© IMC |