uniolympiads Ελληνικά

IMC 2011, Day 1, Problem 5

Let nn be a positive integer and let VV be a (2n−1)(2n-1)-dimensional vector space over the two-element field. Prove that for arbitrary vectors v1,…,v4n−1∈Vv_1, \dots, v_{4n-1} \in V, there exists a sequence 1≤i1<⋯<i2n≤4n−11 \le i_1 < \dots < i_{2n} \le 4n - 1 of indices such that vi1+⋯+vi2n=0v_{i_1} + \dots + v_{i_{2n}} = 0.

Ilya Bogdanov, Moscow and Géza Kós, Budapest

Original from the official PDFLet n be a positive integer and let V be a (2n − 1)-dimensional vector space over the two-element field. Prove that for arbitrary vectors v 1 , . . . , v 4n−1 ∈ V , there exists a sequence 1 ≤ i 1 < . . . < i 2n ≤ 4n − 1 of indices such that v i 1 + . . . + v i 2n = 0. (Ilya Bogdanov, Moscow and Géza Kós, Budapest)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Ilya Bogdanov, Moscow and Géza Kós, Budapest)

Solution. Let V=aff{v1,…,v4n−1}V=\mathrm{aff}\{v_1,\ldots,v_{4n-1}\}. The statement vi1+⋯+vi2n=0v_{i_1}+\dots+v_{i_{2n}}=0 is translation-invariant (i.e. replacing the vectors by v1−a,…,v4n−1−av_1-a,\ldots,v_{4n-1}-a), so we may assume that 0∈V0\in V. Let d=dim⁡Vd=\dim V.

Lemma. The vectors can be permuted in such a way that v1+v2,v3+v4,…,v2d−1+v2dv_1+v_2,v_3+v_4,\ldots,v_{2d-1}+v_{2d} form a basis of VV.

Proof. We prove by induction on dd. If d=0d=0 or d=1d=1 then the statement is trivial.

First choose the vector v1v_1 such a way that aff(v2,v3,…,v4n−1)=V\mathrm{aff}(v_2,v_3,\ldots,v_{4n-1})=V; this is possible since VV is generated by some d+1d+1 vectors and we have d+1≤2n<4n−1d+1\le2n<4n-1. Next, choose v2v_2 such that v2≠v1v_2\ne v_1. (By d>0d>0, not all vectors are the same.)

Now let ℓ={0,v1+v2}\ell=\{0,v_1+v_2\} and let V′=V/ℓV'=V/\ell. For any w∈Vw\in V, let w~=ℓ+w={w,w+v1+v2}\tilde w=\ell+w=\{w,w+v_1+v_2\} be the class of the factor space V′V' containing ww. Apply the induction hypothesis to the vectors v~3,…,v~4n−1\tilde{v}_3,\ldots,\tilde{v}_{4n-1}. Since dim⁡V′=d−1\dim V'=d-1, the vectors can permuted in such a way that v~3+v~4\tilde{v}_3+\tilde{v}_4, …\ldots, v~2d−1+v~2d\tilde{v}_{2d-1}+\tilde{v}_{2d} is a basis of V′V'. Then v1+v2,v3+v4,…,v2d−1+v2dv_1+v_2,v_3+v_4,\ldots,v_{2d-1}+v_{2d} is a basis of VV.

Now we can assume that v1+v2,v3+v4,…,v2d−1+v2dv_1+v_2,v_3+v_4,\ldots,v_{2d-1}+v_{2d} is a basis of VV. The vector w=(v1+v3+⋯+v2d−1)+(v2d+1+v2d+2+⋯+v2n+d)w=(v_1+v_3+\dots+v_{2d-1})+(v_{2d+1}+v_{2d+2}+\dots+v_{2n+d}) is the sum of 2n2n vectors, so w∈Vw\in V. Hence, w+ε1(v1+v2)+⋯+εd(v2d−1+v2d)=0w+\varepsilon_1(v_1+v_2)+\dots+\varepsilon_d(v_{2d-1}+v_{2d})=0 with some ε1,…,εd∈F2\varepsilon_1,\ldots,\varepsilon_d\in\mathbb F_2, therefore

∑i=1d((1−εi)v2i−1+εiv2i)+∑i=2d+12n+dvi=0.\sum_{i=1}^d\Big((1-\varepsilon_i)v_{2i-1}+\varepsilon_iv_{2i}\Big)+\sum_{i=2d+1}^{2n+d}v_i=0.
The left-hand side is the sum of 2n2n vectors.

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?