IMC 2011 · Day 1 · P5

Let $V = \operatorname{aff}\{v_1, \dots, v_{4n-1}\}$. The statement $v_{i_1} + \dots + v_{i_{2n}} = 0$ is translation-invariant (i.e. replacing the vectors by $v_1 - a, \dots, v_{4n-1} - a$), so we may assume that $0 \in V$. Let $d = \dim V$.

Lemma. The vectors can be permuted in such a way that $v_1 + v_2, v_3 + v_4, \dots, v_{2d-1} + v_{2d}$ form a basis of $V$.

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

First choose the vector $v_1$ such a way that $\operatorname{aff}(v_1, v_2, v_3, \dots, v_{4n-1}) = V$; this is possible since $V$ is generated by some $d+1$ vectors and we have $d + 1 \le 2n < 4n - 1$. Next, choose $v_2$ such that $v_2 \ne v_1$. (By $d > 0$, not all vectors are the same.)

Now let $\ell = \{0, v_1 + v_2\}$ and let $V' = V/\ell$. For any $w \in V$, let $\tilde{w} = \ell + w = \{w, w + v_1 + v_2\}$ be the class of the factor space $V'$ containing $w$. Apply the induction hypothesis to the vectors $\tilde{v}_3, \dots, \tilde{v}_{4n-1}$. Since $\dim V' = d - 1$, the vectors can permuted in such a way that $\tilde{v}_3 + \tilde{v}_4$, …, $\tilde{v}_{2d-1} + \tilde{v}_{2d}$ is a basis of $V'$. Then $v_1 + v_2, v_3 + v_4, \dots, v_{2d-1} + v_{2d}$ is a basis of $V$.

Now we can assume that $v_1 + v_2, v_3 + v_4, \dots, v_{2d-1} + v_{2d}$ is a basis of $V$. The vector $w = (v_1 + v_3 + \dots + v_{2d-1}) + (v_{2d+1} + v_{2d+2} + \dots + v_{2n+d})$ is the sum of $2n$ vectors, so $w \in V$. Hence, $w + \varepsilon_1 (v_1 + v_2) + \dots + \varepsilon_d (v_{2d-1} + v_{2d}) = 0$ with some $\varepsilon_1, \dots, \varepsilon_d \in \mathbb{F}_2$, therefore $$\sum_{i=1}^{d} \bigl( (1 - \varepsilon_i) v_{2i-1} + \varepsilon_i v_{2i} \bigr) + \sum_{i=2d+1}^{2n+d} v_i = 0.$$ The left-hand side is the sum of $2n$ vectors.