Bound for the sum of vectors in $\mathbb{R}^n$

Question

I have the following problem (it seems to be very famous, but I couldn't find reference)

Problem. Given $k$ vectors $v_1,v_2,\ldots,v_k\in\mathbb{R}^n$ such that for each $i$ the inequality $|v_i|\leq 1$ holds (here $|v|$ is the euclidean $|\cdot|_2$ norm). Prove that there exist $\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_k\in\{-1,1\}$ such that the following inequalty holds $$ \left|\sum_{i=1}^{k}\varepsilon_i v_i\right|\leq\sqrt{n}. $$

For $k\leq n$ it can be shown by probabilistic argument (i. e. by averaging $\left|\sum\varepsilon_i v_i\right|^2$ over all $2^k$ possible $k$-tuples $(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_k)\in\{-1,1\}^n$). However, this approach can't be extended for $k>n$. Moreover, this bound is sharp because we can take any orthonormal basis $v_1,v_2,\ldots,v_n$ in $\mathbb{R}^n$ and then inequality will turn to equality (for any choice of $\varepsilon_i$).

It's unclear for me how even to solve the problem in case $n=2$.

So, how to solve this problem?

Update. It seems that this is an open problem for $n\geq 3$ (found the following question on MO: https://mathoverflow.net/questions/272373/balanced-vectors)

Answer 1

Here is the proof for the case $n=2$ (the case $n=1$ is easy). To start with, we will prove the following statement:

Lemma. Given three vectors $v_1$, $v_2$, and $v_3$ in $\mathbb{R}^2$ such that length of each vector $v_i$ is at most $1$. Then, there are indices $i$ and $j$ such that $v_i+v_j$ or $v_i-v_j$ has length at most $1$.

Proof. Consider six vectors $\pm v_i$ with initial point at the origin $O$. Then, the six corresponding rays divide the plane into the six regions. Hence, there are two vectors with the angle at most $2\pi/6=\pi/3$ between them. Without loss of generality we can suppose that this two vectors are $v_1$ and $v_2$. Then, $|v_1-v_2|\leq 1$ because $\angle(v_1,v_2)\leq \pi/3$. Thus, we can choose $i=1$ and $j=2$.

Now, if $k\geq 3$, we can apply the lemma $k-2$ times and then use the case $k=2$ (just consider vector $v_i\pm v_j$ instead of $v_i$ and $v_j$).

Maybe this lemma can be extended to the higher dimensions, but I can't prove it.