uniolympiads Ελληνικά

IMC selection 2026, Problem 2

Δίνεται ένας n×nn \times n πίνακας A=(ai,j)A = (a_{i,j}) με στοιχεία μη αρνητικούς πραγματικούς αριθμούς για τον οποίο το στοιχείο στην πρώτη γραμμή και δεύτερη στήλη του πίνακα A+A2+⋯+An−1A + A^2 + \dots + A^{n-1} είναι ίσο με μηδέν. Να δείξετε ότι υπάρχουν μη κενά και ξένα υποσύνολα X,YX, Y του {1,2,…,n}\{1, 2, \dots, n\} με ένωση X∪Y={1,2,…,n}X \cup Y = \{1, 2, \dots, n\} τέτοια ώστε για κάθε i∈Xi \in X και κάθε j∈Yj \in Y να έχουμε ai,j=0a_{i,j} = 0.

Original from the official PDFΔίνεται ένας n × n πίνακας A = (a i,j ) με στοιχεία μη αρνητικούς πραγματικούς αριθμούς για τον οποίο το στοιχείο στην πρώτη γραμμή και δεύτερη στήλη του πίνακα A + A 2 + ⋯ + A n−1 είναι ίσο με μηδέν. Να δείξετε ότι υπάρχουν μη κενά και ξένα υποσύνολα X, Y του {1, 2, …, n} με ένωση X ∪ Y = {1, 2, …, n} τέτοια ώστε για κάθε i ∈ X και κάθε j ∈ Y να έχουμε a i,j = 0.

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

Κατασκευάζουμε ένα κατευθυνόμενο γράφημα με κορυφές τα 1,2,…,n1, 2, \dots, n και κατευθυνόμενες ακμές (i,j)(i, j) (θα το γράφουμε και ως i→ji \to j) για κάθε διατεταγμένο ζεύγος δεικτών τέτοιο ώστε ai,j>0a_{i,j} > 0.

Ισχυρισμός: Δεν υπάρχει μονοπάτι 1→i1→⋯→ir→21 \to i_1 \to \cdots \to i_r \to 2 στο κατευθυνόμενο γράφημα.

Γιατι μπορουμε να εχουμε οτι στο μονοπατι δεν επαναλαμβανεται καποιος δεικτης, αρα r≤n−2r \le n - 2 και (Ar+1)1,2>0(A^{r+1})_{1,2} > 0, που είναι άτοπο από την υπόθεση (r+1≤n−1)(r + 1 \le n - 1).

Θέτουμε λοιπόν

X:={k∈[n]: υπαˊρχει μονοπαˊτι αποˊ το 1 το k στο γραˊφημα}∪{1},X := \{k \in [n] :\ \text{υπάρχει μονοπάτι από το 1 το } k \text{ στο γράφημα}\} \cup \{1\},
Y:=[n]∖XY := [n]\setminus X. Τα X,YX, Y είναι μη κενά (2∈Y2 \in Y) με ένωση το [n][n]. Έστω τώρα i∈X,j∈Yi \in X, j \in Y. Αν ai,j>0a_{i,j} > 0, τότε από τον ορισμό του XX θα είχαμε ότι επίσης j∈Xj \in X (στο μονοπάτι που οδηγεί από το 11 στο ii προσθέτουμε ακόμα ένα βήμα, το i→ji \to j), άτοπο αφού j∈[n]∖Xj \in [n]\setminus X.

Transcribed from the official solutions, page 2. 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?