uniolympiads English

IMC 2024, Ημέρα 2, Θέμα 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}.

Πρωτότυπο από το επίσημο 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

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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).

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 4–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;