Proposer's note: this is inspired by the property of isotonic regression (monotone smoothing), cf. https://link.springer.com/article/10.1007/BF01580873.

There exists $y_1$ and $y_2,\cdots y_n\ge 0$ such that $x_k=\sum\limits_{i=1}^k y_i$. Let $\sum b_i^2=\sum a_i^2=T$. The expression becomes $\sum (x_i-b_i)^2=\sum b_i^2+\sum x_i^2-2\sum x_ib_i=T+\sum x_i^2-2\sum(y_1+\cdots+y_i)b_i$. This is equal to $T+\sum x_i^2-2\sum (b_i+\cdots+b_n)y_i=T+\sum x_i^2+2\sum (b_1+\cdots+b_{i-1})y_i$. (note $y_1$ is not in the last sum). Since all $y_{\ge 2}$ are non-negative, if $b_1+\cdots+b_{i-1}\ge 0$ then the sum is at least $T$, attainable when all $y_i=0$. This shows one direction. Suppose $b_1+\cdots+b_k<0$. Let it be $-c$ for $c>0$. We take all $y_i=0$ except $y_{k+1}=Y$. This gives $T+(n-k)Y^2-2cY$. Taking $Y$ sufficiently small (and positive) we can make it $<T$, finishing the proof.

Official Solution: Solution: Here we show that the two conditions are equivalent. Observe that by looking at $x_1=\cdots = x_n=0$ we have $S(\sigma) \le \sum a_i^2$ for all permutations $\sigma$. Suppose $b_1+\cdots + b_k < 0$ for some $k$, then choosing $y_1=\cdots = y_k=-1$ and $y_{k+1}+\cdots + y_n=0$ yields $b_1y_1+\cdots + b_ny_n = -(y_1+\cdots + y_k)>0$. In addition, we may choose This gives $S(\sigma)\le \sum a_n^2 - \frac{(b_1+\cdots + b_k)^2}{k} < \sum a_i^2$. On the other hand, suppose that $b_1 + \cdots + b_k\ge 0$ for all $k\ge 1$. Notice that such permutation exists: for example, take $\sigma$ such that $b_1\ge \cdots \ge b_n$. We will show that $b_1y_1 + \cdots + b_ny_n\le 0$ for all $y_1\le \cdots \le y_n$. Since $\sum b_i=0$, replacing $(y_1, \cdots, y_n)$ with $(y_1 - c, \cdots, y_n-c)$ for any $c$ will still yield the same sum $\sum b_iy_i$. We now choose $c=y_n$; all the $y_i$'s are now nonpositive. Iteratively, let $k$ be the largest index with $y_k < 0$, while $y_{k+1}=\cdots = y_n=0$. We replace $y_1, \cdots, y_k$ with $y_1-y_k, \cdots, y_k-y_k$, the cross term $\sum_{i=1}^n b_iy_i$ is now increased by $-y_k\sum_{i=1}^k b_i \ge 0$. The new sequence $y_1', \cdots, y_k', y_{k+1}, \cdots, y_n$ is still nondecreasing. We now end up with $y_1=\cdots=y_n=0$. Since the sum $\sum b_iy_i$ never decreases throughout the iteration, it follows that it has to be nonpositive to start with. Finally, what we established implies the other condition: for all $x_1\le \cdots \le x_n$ we then have $\sum (x_i-b_i)^2=\sum a_i^2 + x_i^2 - 2b_ix_i\ge \sum a_i^2 - 2\sum b_ix_i\ge \sum a_i^2$. $\blacksquare$