# Permutation that gives a sequence of non-negative partial sums

Given a sequence $(a_i)_1^n$ of real numbers that sum to $0$. There are $n$ circular permutations.

$\begin{array}{}\sigma_1 = &(a_1 &a_2 &\cdots &a_{n-1} &a_n)\\ \sigma_2 = &(a_2 &a_3 & \cdots &a_n &a_1)\\\sigma_3 = &(a_3& a_4& \cdots &a_1 &a_2)\\\vdots&\vdots\\\sigma_n = &(a_n& a_1& \cdots &a_{n-2} &a_{n-1})\end{array}$

Define $s_i(k)$ to be the sum of the first $k$ terms of permutation $\sigma_i$. Obviously, $s_i(n) = 0$.

Question: Does there always exist at least one permutation $\sigma_{p}$ such that the sequence $s_p(1), s_p(2), \cdots s_p(n-1)$ is non-negative?

Example 1: $(-10, 7, -8, 11)$

We find that there exists $\sigma_p = \sigma_4$ that gives a non-negative sequence of partial sums.

$\begin{array}{rrrrr|rrrr}\text{Index}&1&2&3&4&s(1)&s(2)&s(3)&s_(4)\\\hline\\\sigma_1:&-10&7&-8&11&-10&-3&-11&0\\\sigma_2:&7&-8&11&-10&7&-1&10&0\\\sigma_3:&-8&11&-10&7&-8&3&-7&0\\\sigma_{\color{green}{4}}:&11&-10&7&-8&\color{green}{11}&\color{green}{1}&\color{green}{8}&0\end{array}$

Example 2: $(1, 1, 1, 1, 8, 11, -29, 3, -7, 2, 1, 4, 4, -1)$

Here $\sigma_p = \sigma_{10} = (2, 1, 4, 4, -1, 1,1,1,1, 8, 11, -29, 3, -7)$ meets the requirement.

I feel that the property is true in general, but have no idea how to prove it.

Note: This question came to my mind while trying to understand the essence of this problem.

UPDATE: Here's an expansion of Daniel Fischer's answer.

Let the minimum $s_1(m) = -A \text{ for some } A \in \mathbb{R_{\ge 0}}$.

(1) Then the trailing terms $a_{m+1}, a_{m+2}, \cdots ,a_n$ contribute non-negative partial sums $a_{m+1}, a_{m+1} + a_{m+2}, \cdots$

Assume for some $1\le q \le n-m$, a negative partial sum $a_{m+1} + a_{m+2} + \cdots + a_{m+q}$. Then $s_1(m+q) = s_1(m) + a_{m+1} + a_{m+2} + \cdots + a_{m+q} < s_1(m)$ contra minimum $s_1(m)$.

Note that $a_{m+1} + a_{m+2} + \cdots + a_{n} = 0 - s_1(m) = A$

(2) For $1\le m' \le m$, we have by definition $s_1(m') \ge s_1(m)$.

$\begin{eqnarray}\implies a_{m+1} + a_{m+2} + \cdots + a_{n} + a_1 + a_2 + \cdots + a_{m'} &= &A + s_1(m')\\&\ge &A + s_1(m)\\&=&A -A\\&=& 0\end{eqnarray}$

Thus, from (1) and (2), we get the answer that $\sigma_{m+1}$ satisfies the required property.

Consider the finite sequence of partial sums $\bigl(s_1(k)\bigr)_{1 \leqslant k \leqslant n}$. There is at least one $m$ with
$$s_1(m) = \min \left\{ s_1(k) : 1 \leqslant k \leqslant n\right\}.$$
Then the cyclic permutation $\sigma_{m+1}$ (with the identification $\sigma_{n+1} = \sigma_1$ if $m = n$) has the desired property.