IMC 2011, Day 1, Problem 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
Original from the official PDF

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
(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
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.