IMC selection 2025, Problem 1
Έστω θετικοί ακέραιοι με με και με . Θέτουμε
Βρείτε το .
Original from the official 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 }.](/archive/epilogi-imc/epilogi-imc-2025-p1.png)
This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Το ζητούμενο μέγιστο ισούται με .
Έστω και οι γραμμές του . Δηλαδή
Έχουμε
Καθεμία από τις δύο διαστάσεις στο τέλος είναι το πολύ . Για την πρώτη είναι προφανές αφού . Για τη δεύτερη, παρατηρούμε ότι είναι η τάξη του πίνακα με γραμμές τις με όποια σειρά θέλουμε. Σε αυτόν τον πίνακα, όλες οι στήλες με δείκτη είναι , άρα η τάξη του είναι το πολύ .
Ισχυρισμός: Η τιμή λαμβάνεται. Δηλαδή, υπάρχει με .
Θεωρούμε με . Αυτό είναι εφικτό γιατί . Έστω ότι τα στοιχεία των , όταν μπουν σε αύξουσα σειρά είναι τα
Ο (συμμετρικός) πίνακας με
Σχόλιο: Η λύση απλοποιείται αν πούμε πως με χρήση ενός μετασχηματισμού ομοιότητας μπορούμε να υποθέσουμε ότι .
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?
Moves you mark come back sooner in triage.