Balanced vectors

Question

If $n$ vectors $a_1, a_2, \cdots , a_n$ are given in $\mathbb{R}^n$ with all lengths at most $1$, then it is not to hard to see that we can put $+$ and $-$ in place of $*$ in the expression $$a_1 * a_2 * \cdots * a_n$$ so that the result will have length at most $\sqrt{n}$.

To see this, it's enough to choose $\lambda_1, \cdots, \lambda_n$ independently and uniformly from $\{\pm 1\}$. Then, put $X={|\sum_{i=1}^{n}a_i\lambda_i|}^2$. By a simple calculation, you will find that $E(X)=n$. Hence there exist specific $\lambda_1, \cdots, \lambda_n = \pm 1$ with and with $X\leq n$. Taking square roots gives the theorem.

Now I am curious to know, is it possible to generalize this theorem as follows?

Assume $N>n$ vectors $a_1, a_2, \cdots , a_N$ are given in $\mathbb{R}^n$ with all lengths at most $1$. Is it possible to put $+$ and $-$ in place of $*$ in the expression $$a_1 * a_2 * \cdots * a_N ,$$ so that the result will have length at most $\sqrt{n}$.

Answer 1

It is a classical result of Barany and Grinberg (generalizing an earlier result of Spencer) that there exist $\lambda_1,\dotsc,\lambda_N\in\{\pm 1\}$ with $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le 2n. $$ The paper of Barany-Grinberg was published in 1981, but they indicated that the problem was posed in 1963 by Dvoretzky. Interestingly, Barany and Grinberg, along with Gergely Ambrus, have just published another paper on this subject.

Notice that for $n=2$, it is easy to get the sharp bound $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le \sqrt 2; $$ it follows by using induction and observing that among any three vectors in $\mathbb R^2$ of length at most $1$, there are two vectors such that either their sum, or their difference has length at most $1$, and that for any two vectors of length at most $1$, either their sum, or their difference has length at most $\sqrt 2$.

Answer 2

A nice and short proof of this statement is found the 1981 note of Spencer:

https://www.sciencedirect.com/science/article/pii/0097316581900339

He writes that the result had been known before the publication, although with no explicit reference. His proof is elegant, using the result for $n$ vectors, and then applying a probabilistic technique.