there exist a sequence of $b_i$ such that $0 \le \sum_{i=1}^k b_i \le \sqrt{n}$, with $b_i = \pm a_i$ with fixed $a_i$ and $\sum_{i=1}^k a_i^2 = n$ Use the Chernoff bound/Chebyshev's inequality to prove that given fixed $a_i$ with $\sum_{i=1}^k a_i^2 = n$, there exist a sequence of numbers $b_1, \cdots, b_k$ with $b_i\in \{-a_i, a_i\}$ such that $0 \le \sum_{i=1}^k b_i \le \sqrt{n}$.
My idea is that every $b_i$ is Bernoulli distribution with some $p_i$, if I can construct some $p_i$ for $1 \le i \le k$ such that
$$P\left(\sum_{i=1}^k b_i < 0\right) + P\left(\sum_{i=1}^k b_i >\sqrt{n}\right) < 1$$ then the claim is proven.
 A: This is an application of the probabilistic method: if a random variable satisfies something with positive probability, then there exists a realization of that random variable which satisfies this thing.
For every $1\leq i\leq k$, let $B_i$ be uniform on $\{-a_i,a_i\}$, with $B_1,\dots,B_k$ mutually independent. Then, for all $i$,
$$
\mathrm{Var}[B_i] = a_i^2
$$
so that $B := \sum_{i=1}^k B_i$ has expectation $0$ and variance
$$
\sum_{i=1}^k \mathrm{Var}[B_i] = n
$$
By Chebychev's inequality, it follows that
$$
\Pr[ |B| > \sqrt{n} ] < \frac{\mathrm{Var}[B]}{\sqrt{n}^2} = 1
$$
i.e., $\Pr[ |B| \leq \sqrt{n} ] > 0$. This implies there exists some realization of $B_1,\dots, B_k$ such that $\left|\sum_{i=1}^k B_i\right| \leq \sqrt{n}$, call this $b'_1,\dots, b'_k$. Then taking $b_1,\dots, b_k$ to be either this $b'_1,\dots, b'_k$ or its negation $-b'_1,\dots, -b'_k$ (depending on the sign of the sum) works.
A: Setting $a_i=b_i=\sqrt{\frac nk}$ gives $\sum_{i=1}^k b_i=\sqrt{kn}$. Taking the antipodal point $b_i=-\sqrt{\frac nk}$ results in the negative value for the sum.
The sum is a continuous function on the sphere $\sum_{i=1}^k b_k^2=n$, so following any big circle connecting the antipodal points there will exist points with $\sum_{i=1}^k b_i=c$ for any of the desired $c\in[0,\sqrt{n}]$ by the intermediate value theorem.
Examples are

*

*$b_1=\sqrt{n}$, $b_i=0$ for $i>1$, for a sum of $\sqrt n$, or

*$b_1=-b_2=\sqrt{n/2}$, $b_i=0$ for $i>2$, for a zero sum. Another variant is

*$b_i=(-1)^{i-1}\sqrt{n/k}$, $i=1,...,k$, with a sum of $\sqrt{n/k}$ or zero.

