uniolympiads Ελληνικά

IMC 2024, Day 2, Problem 9

A matrix A=(aij)A = (a_{ij}) is called nice, if it has the following properties:

(i) the set of all entries of AA is {1,2,…,2t}\{1, 2, \dots, 2t\} for some integer tt;

(ii) the entries are non-decreasing in every row and in every column: ai,j≤ai,j+1a_{i,j} \le a_{i,j+1} and ai,j≤ai+1,ja_{i,j} \le a_{i+1,j};

(iii) equal entries can appear only in the same row or the same column: if ai,j=ak,ℓa_{i,j} = a_{k,\ell}, then either i=ki = k or j=ℓj = \ell;

(iv) for each s=1,2,…,2t−1s = 1, 2, \dots, 2t-1, there exist i≠ki \ne k and j≠ℓj \ne \ell such that ai,j=sa_{i,j} = s and ak,ℓ=s+1a_{k,\ell} = s + 1.

Prove that for any positive integers mm and nn, the number of nice m×nm \times n matrices is even. For example, the only two nice 2×32 \times 3 matrices are (111222)\begin{pmatrix} 1 & 1 & 1 \\ 2 & 2 & 2 \end{pmatrix} and (113244)\begin{pmatrix} 1 & 1 & 3 \\ 2 & 4 & 4 \end{pmatrix}.

Original from the official PDFA matrix A = (a ij ) is called nice, if it has the following properties: (i) the set of all entries of A is {1, 2, . . . , 2t} for some integer t; (ii) the entries are non-decreasing in every row and in every column: a i,j ≤ a i,j+1 and a i,j ≤ a i+1,j ; (iii) equal entries can appear only in the same row or the same column: if a i,j = a k,ℓ , then either i = k or j = ℓ; (iv) for each s = 1, 2, . . . , 2t − 1, there exist i ̸ = k and j ̸ = ℓ such that a i,j = s and a k,ℓ = s + 1. Prove that for any positive integers m and n, the number of nice m × n matrices is even. 1 1 1 1 1 3 For example, the only two nice 2 × 3 matrices are and . 2 2 2 2 4 4

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

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 m×nm \times n as an m×nm \times n matrix with the set of entries {1,2,…,mn}\{1, 2, \dots, mn\}, increasing in every row and in every column as in (ii).

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

For a nice m×nm \times n matrix AA we construct a standard Young tableaux YAY_A of shape m×nm \times n as follows: if AA has nin_i entries equal to ii (i=1,2,…,2t)(i = 1, 2, \dots, 2t), we replace them by the numbers from n1+…+ni−1+1n_1 + \ldots + n_{i-1} + 1 to n1+…+nin_1 + \ldots + n_i preserving monotonicity.

Note that our YAY_A has exactly 2t−12t - 1 friends, where 2t2t is the number of distinct entries in AA, 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?