Let $v_1, v_2,...,v_n \in \mathbb{R}^n$ be unit vectors. Use probabilistic method to show that there exist constants $a_1, a_2,..., a_n \in \{-1,1\}$ such that $||a_1 v_1 + a_2 v_2 + ... + a_n v_n ||_2 \leq \sqrt{n}$.
I think I should make a n random variable $X_i$ that take values in $\{-1,1\}$ each with probability ½, and somehow show that the probability that the squared $2-$norm of the linear combination with coefficients $X_i$ is greater than n, is less than 1. But I am not sure how I should go about that. Any hint would be appreciated.
You shouldn't look for the probability that the norm squared is greater than $n$. You should look for it's expectation value. We have
$$\left|\sum a_jv_j\right|^2 = \sum\sum a_j a_k v_j\cdot v_k = \sum a_j^2|v_j|^2 + \sum_{j\ne k} a_j a_k v_j\cdot v_k = n + \sum a_ja_kv_jv_k$$
Assume that $a_j$ are mutually independent variables with $P(a_j=\pm1) = 1/2$
Now the expectation value of $a_ja_k = 0$ so the expectation value of the norm squared is $n$. This can only happen if it's probable that it's less than or equal to $n$ - therefore there must exist $a_j$s that make it less than or equal to $n$.