uniolympiads English

Επιλογή IMC 2026, Θέμα 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.

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

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

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

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

Επίσημη λύση

Κατασκευάζουμε ένα κατευθυνόμενο γράφημα με κορυφές τα 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.

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

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

Πώς πήγε;