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?
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.