If $v_1,v_2,\ldots,v_n\in \mathbb{R}^n$ s.t $\|v_k\|=1$, then $\exists\epsilon_k=\pm 1$ s.t. $\left\|\sum_{k=1}^n \epsilon_k v_k\right\|\le \sqrt{n}$. 
Let $v_1,v_2,\ldots,v_n$ be vectors of $\mathbb{R}^n$ such that $\|v_i\|=1$ for all $i=1,2,\ldots,n$.  Prove that there exist $\epsilon_1,\epsilon_2,\ldots,\epsilon_n \in \{-1,1\}$ such that
$$\left\|\sum_{k=1}^{n} \epsilon_kv_k \right\| \leq \sqrt{n}\,.$$
Here, $\|\_\|$ is the standard Euclidean norm on $\mathbb{R}^n$.

My Idea: I found an non-probailistic method and proved the existence by induction. I need the probabilistic one.  My idea is to take random variables of Rademacher with probability $1/2$ then the expected value of the sum, the problem is that we have Euclidean norm? any suggestions?
 A: Let $\epsilon_1,\epsilon_2,\ldots,\epsilon_n$ be uniformly randomly and independently chosen from $\{-1,+1\}$ (i.e., they are independent Rademacher random variables).  We want to calculate
$$E:=\mathbb{E}\left[\left\|\sum_{k=1}^n\,\epsilon_k\,v_k\right\|^2\right]\,.$$
Noting that $\epsilon_k^2=1$ for all $k=1,2,\ldots,n$, the expansion of the expected value above is
$$E=\sum_{k=1}^n\,\|v_k\|^2+2\,\sum_{1\leq i<j\leq n}\,\mathbb{E}\left[\epsilon_i\,\epsilon_j\right]\,\langle v_i,v_j\rangle\,,$$
where $\langle\_,\_\rangle$ is the standard inner product on $\mathbb{R}^n$.
Since $$\mathbb{E}[\epsilon_i\,\epsilon_j]=\mathbb{E}[\epsilon_i]\,\mathbb{E}[\epsilon_j]=0\cdot 0=0$$ for all indices $i$ and $j$ such that $i\neq j$, we get
$$E=\sum_{k=1}^n\,\|v_k\|^2\,.$$
Because $\|v_k\|=1$ for all $k=1,2,\ldots,n$, we have $E=n$.  Hence, there exist $\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n\in\{-1,+1\}$ for which
$$\left\|\sum_{k=1}^n\,\varepsilon_k\,v_k\right\|^2\leq E=n\,.$$
The claim follows immediately.
