(Alibaba Contest Finals 2020/18) Let $a_1,a_2,...,a_n$ be positive reals whose squares sum to 1. Show that there exists a choice of $\varepsilon_i\in\{-1,1\}$ such that $$\left|\sum_{i=1}^n \varepsilon_i a_i\right| \le \frac{1}{a_1+a_2+...+a_n}$$

Remark. There’s a hint not to use probabilistic-style arguments: this inequality is tight for $n$ odd ($a_i$ all equal).

Motivation. We try something incredibly stupid: instead we set $\varepsilon_i\in [-1,1]$ and start from all zeroes, then we start shifting them while keeping $\sum\varepsilon_i a_i = 0$. As long as there are two things of the opposite sign we can keep “unsmoothing” $\varepsilon_i$’s to the endpoints. If your set was balanced (close to all equal) to begin with, you should end up with just one nonzero term: $$\left|\sum_{i=1}^n \varepsilon_i a_i\right| \le a_j$$ And in particular, you’re done if $a_j$ happens to be the smallest term! You want it to be the smallest one anyway, so this gives the idea of always starting to smooth the largest $a_i$ first.

Solution. So this is essentially the greedy algorithm: order $a_1\ge a_2\ge ...$ and decide on the sign by going towards 0: $\varepsilon_i$ should have the same sign as $-\sum_{j