IMC 2011, Ημέρα 1, Θέμα 5
Let be a positive integer and let be a -dimensional vector space over the two-element field. Prove that for arbitrary vectors , there exists a sequence of indices such that .
Ilya Bogdanov, Moscow and Géza Kós, Budapest
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(Ilya Bogdanov, Moscow and Géza Kós, Budapest)
Solution. Let . The statement is translation-invariant (i.e. replacing the vectors by ), so we may assume that . Let .
Lemma. The vectors can be permuted in such a way that form a basis of .
Proof. We prove by induction on . If or then the statement is trivial.
First choose the vector such a way that ; this is possible since is generated by some vectors and we have . Next, choose such that . (By , not all vectors are the same.)
Now let and let . For any , let be the class of the factor space containing . Apply the induction hypothesis to the vectors . Since , the vectors can permuted in such a way that , , is a basis of . Then is a basis of .
Now we can assume that is a basis of . The vector is the sum of vectors, so . Hence, with some , therefore
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.