IMC 2024, Day 2, Problem 9
A matrix is called nice, if it has the following properties:
(i) the set of all entries of is for some integer ;
(ii) the entries are non-decreasing in every row and in every column: and ;
(iii) equal entries can appear only in the same row or the same column: if , then either or ;
(iv) for each , there exist and such that and .
Prove that for any positive integers and , the number of nice matrices is even. For example, the only two nice matrices are and .
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(proposed by Fedor Petrov, St Petersburg State University)
Solution. Define a standard Young tableaux of shape as an matrix with the set of entries , increasing in every row and in every column as in (ii).
Call two standard Young tableaux friends, if they differ by a switch of two consecutive numbers (the places of and must be not neighbouring, for such a switch preserving the monotonicity in rows and columns).
For a nice matrix we construct a standard Young tableaux of shape as follows: if has entries equal to , we replace them by the numbers from to preserving monotonicity.
Note that our has exactly friends, where is the number of distinct entries in , 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).
Transcribed from the official solutions, pages 4–5. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.