uniolympiads English

Επιλογή IMC 2025, Θέμα 1

Έστω k,nk, n θετικοί ακέραιοι με με k≤n/2k \le n/2 και I⊂[n]:={1,2,…,n}I \subset [n] := \{1, 2, \dots, n\} με ∣I∣=k|I| = k. Θέτουμε

AI:={A∈Rn×n:Ai,j=0 αν i,j∈[n]∖I}.\mathcal{A}_I := \{A \in \mathbb{R}^{n \times n} : A_{i,j} = 0 \text{ αν } i, j \in [n] \setminus I\}.

Βρείτε το max⁡{rank⁡(A):A∈AI}\max\{\operatorname{rank}(A) : A \in \mathcal{A}_I\}.

Πρωτότυπο από το επίσημο PDFΈστω k, n θετικοί ακέραιοι με με k ≤ n/2 και I ⊂ [n] ∶= {1, 2, … n} με |I| = k. Θέτουμε 𝒜 I ∶= {A ∈ ℝ n×n ∶ A i,j = 0 αν i, j ∈ [n] ⧵ I}. Βρείτε το max{rank(A) ∶ A ∈ 𝒜 I }.

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

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

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

Επίσημη λύση

Το ζητούμενο μέγιστο ισούται με 2k2k.

Έστω A∈AIA \in \mathcal{A}_I και a1,a2,…,ana_1, a_2, \dots, a_n οι γραμμές του AA. Δηλαδή

A=(a1a2⋮an)\mathrm{A} = \begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{pmatrix}

Έχουμε

rank⁡(A)=dim⁡<{a1,a2,…,an}>≤dim⁡<{ai : i∈I}>+dim⁡<{ai : i∈[n]∖I}>.\operatorname{rank}(A) = \dim < \{a_1, a_2, \dots, a_n\} > \le \dim < \{a_i \,:\, i \in I\} > + \dim < \{a_i \,:\, i \in [n]\setminus I\} > .

Καθεμία από τις δύο διαστάσεις στο τέλος είναι το πολύ kk. Για την πρώτη είναι προφανές αφού I=kI = k. Για τη δεύτερη, παρατηρούμε ότι είναι η τάξη του πίνακα με γραμμές τις {ai : i∈[n]∖I}\{a_i \,:\, i \in [n]\setminus I\} με όποια σειρά θέλουμε. Σε αυτόν τον πίνακα, όλες οι στήλες με δείκτη j∈[n]∖Ij \in [n]\setminus I είναι 00, άρα η τάξη του είναι το πολύ kk.

Ισχυρισμός: Η τιμή 2k2k λαμβάνεται. Δηλαδή, υπάρχει A∈AIA \in \mathcal{A}_I με rank⁡(A)=2k\operatorname{rank}(A) = 2k.

Θεωρούμε J⊂[n]∖IJ \subset [n]\setminus I με ∣J∣=k|J| = k. Αυτό είναι εφικτό γιατί 2k≤n2k \le n. Έστω ότι τα στοιχεία των I,JI, J, όταν μπουν σε αύξουσα σειρά είναι τα

i1<i2<⋯<ik,j1<j2<⋯<jk.\begin{aligned} &i_1 < i_2 < \cdots < i_k, \\ &j_1 < j_2 < \dots < j_k. \end{aligned}

Ο (συμμετρικός) πίνακας AA με

Ar,s={1αν {r,s}={it,jt} για καˊποιο t∈[k],0διαφορετικαˊ,A_{r,s} = \begin{cases} 1 & \text{αν } \{r, s\} = \{i_t, j_t\} \text{ για κάποιο } t \in [k], \\ 0 & \text{διαφορετικά,} \end{cases}
έχει ακριβώς 2k2k μη μηδενικές γραμμές οι οποίες μάλιστα είναι γραμμικά ανεξάρτητες.

Σχόλιο: Η λύση απλοποιείται αν πούμε πως με χρήση ενός μετασχηματισμού ομοιότητας μπορούμε να υποθέσουμε ότι I=[k]I = [k].

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

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

Πώς πήγε;