Upper bound of Euclidean norm on vectors in $\mathbb{R}^n$ Show that for any vectors $v_1,\ldots,v_n \in \{-1,1\}^n \subset \mathbb{R}^n$, there exist $\epsilon_1,\ldots,\epsilon_n \in \{-1,1\}$ such that the Euclidean norm of $v=\sum_{i=1}^n \epsilon_i v_i$ is bounded by $n$.
Any help appreciated. 
 A: Hint: what is the expectation of $<\epsilon_iv_i,\epsilon_jv_j>$? Of $<v,v>$ ?
Update: as it was not clear, note that it is not zero for $i=j$
Thus, we have $E(<v,v>)=\sum_{i,j} E(<\epsilon_iv_i,\epsilon_j v_j>)=\sum_i <\epsilon_iv_i, \epsilon_iv_i>=n^2$. So there is a vector of the length $\sqrt{<v,v>} \leq n$
A: There's a non-probabilistic solution. 
The basis of recurrence is easily checked for $n=1,\,2$. Suppose that the statement is true for $n-1$, and consider the case $n$.
Without losing generality, we can suppose that $v^1_i =1$ (i.e. first element of each vector is $1$). So, we can write that $v_i = (1,\bar v_i)$, where $\bar v_i\in \{-1,1\}^{n-1}$. Then the sum writes
$$\sum_{i=1}^n\epsilon_i v_i = \begin{pmatrix}\sum_{i=1}^n\epsilon_i\\ \epsilon_n\bar v_n +\sum_{i=1}^{n-1}\epsilon_i \bar v_i \end{pmatrix}.$$
Euclidian norm writes $$\left\|\sum_{i=1}^n\epsilon_i v_i\right\|^2 = \left(\sum_{i=1}^n\epsilon_i\right)^2+\left\|\sum_{i=1}^{n-1}\epsilon_i \bar v_i \right\|^2+\|\bar v_n\|^2 + 2\epsilon_n \left(\bar v_n, \sum_{i=1}^{n-1}\epsilon_i \bar v_i\right).$$
Take $\epsilon_i$ $i=1..n-1$ such that the norm of the sum $\left\|\sum_{i=1}^{n-1}\epsilon_i \bar v_i \right\|^2$ is minimised (by hypothesis, it's bounded by $(n-1)^2$). Then take $\epsilon_n$ such that the scalar product $\epsilon_n \left(\bar v_n, \sum_{i=1}^{n-1}\epsilon_i \bar v_i\right)$ is non-positive. Therefore, the norm is estimated by 
$$\left\|\sum_{i=1}^n\epsilon_i v_i\right\|^2 \le n+ (n-1)^2 + (n-1)=n^2.$$
