Inequality for $n$ vectors in $\mathbb{R}^n$ I'm struggling to prove that for $v_1,v_2,...,v_n \in \mathbb{R}^n$ unit vectors there exists $a_1,...,a_n \in \{-1,1\}$ such that 
$$|a_1v_1 + ... + a_nv_n| \leq \sqrt{n}$$
I tried to prove it explicitly, but got stuck when expanding the magnitude and the sum of squares I got sums of mixed products $2\sum_{j\leq n}\sum _{i <j} v_{ki} v_{kj}$ (for a vector $v_k = [v_{k1}, v_{k2}, ..., v_{kn}]$ for instance). That's why I also tried induction, but it turned out troublesome since in this problem not only does the number of vectors increases but also their length becomes larger so that the induction assumption is hard to use.
Do you have any hints? 
 A: A stronger statement is true: If $v_1, \dots, v_m$ are unit vectors in $\mathbf{R}^n$, then there exist $a_1, \dots, a_m \in \{-1, 1\}$ such that
$$
\| a_1 v_1 + \dots + a_m v_m \| \le \sqrt{m}.
$$
There is no need to require $m = n$, and in fact the stronger statement above is easier to prove by induction on $m$.
Here is how to construct $a_1, \dots, a_m$: Start by taking $a_1 = 1$. Suppose $k \ge 1$ and $a_1, \dots, a_k$ have been chosen. Let
$$
w = a_1 v_1 + \dots + a_k v_k.
$$
By induction, we can assume $\|w\| \le \sqrt{k}$.
Choose $a_{k+1} = 1$ if
$$
\|w + v_{k+1}\| \le \| w - v_{k+1}\|
$$
and choose $a_{k+1} = -1$ if the inequality above does not hold.
The Parallelogram Equality tells us that
\begin{align*}
\|w + v_{k+1}\|^2 + \| w - v_{k+1}\|^2 &= 2(\|w\|^2 + \|v_{k+1}\|^2)\\
&\le 2(k+1).
\end{align*}
Thus
$$
\min\{ \|w + v_{k+1}\|, \| w - v_{k+1} \|\} \le \sqrt{k+1},
$$
which completes the proof by induction that this procedure works.
A: Choose the $(a_i)$ uniformly and independently at random. Then $$\mathbb{E}|a_1v_1+...+a_nv_n|^2=\mathbb{E}\sum_{j}\left(\sum_{i}a_iv_i^j\right)^2\\=\sum_j \mathbb{E} \left( \sum_i(a_iv_i^j)^2 + \sum_{i\lt k}a_ia_kv^j_iv^j_k\right)\\=\sum_j(\sum_i(v_i^j)^2+0)\\=n$$
Conclusion follows
