If $\sum_{i=1}^n a_n=0$ then you can find a "good" ordering of $a_i$.

Question

I'm trying to prove (or disprove, but I think it's true and I'll be surprised if someone would manage to disprove it) a small theorem.

Given an array of real numbers $A=[a_1,a_2,...,a_n]$ such that $\sum_{i=1}^n a_i=0$, I want to prove that there is a reordering (via rotation only, not permutation) of the elements in the array, such that we will never get a negative temporary sum.

It's a bit difficult and english is not my native tongue, I'll try to explain with an example.

Let's look at the array $A=[1,-6,2,3]$. if we sum the elements we get $1+(-6)+2+3=0$. But $1+(-6)=-5$. So this is not a good ordering. Because while summing all of the elements, we had a temporary sum that is negative.

However, if we rotate the array to $A'=[2,3,1,-6]$ then we have $2+3+1+(-6)=0$. And nowhere in this summation did we have a negative sum.

Very important note:

When I say reordering I don't mean permutation. I mean rotation only. if our original array was $A=[1,-6,2,3]$ then $A'=[3,2,1,-6]$ is not a valid reordering because we can't rotate $A$ and get to $A'$. I mean circular rotation only. Not permutation.

What I tried to do:

The first thing that came to mind is induction. It is simple to see that if $a_1+a_2=0$ then we have $3$ options: $a_1=a_2=0$ in which case any rotation will do, or $a_1>0>a_2$ or $a_2>0>a_1$. In any case it is possible to find a rotation that there will be no negative temporary sum.

But how do we generalize it? Suppose I can find a good arrangement for an array with $k$ elements. Why does that mean I can find a good arrangement for an array with $k+1$ elements?

Another idea would be to assume there is no such arrangement and then we hope to reach a contradiction to the total sum being zero. I failed to reach such a contradiction.

Answer 1

Define $S_0=0$ and consider the partial sums $S_k:=\sum_{i=1}^k a_i$. Let $k^*$ be any value of $k$ where $S_k$ is minimum. If $k^*=n$, set $k^*=0$. Then the rotation $[a_{k^*+1}, a_{k^*+2}, \ldots,a_{k^*}]$ should satisfy your criterion.

To see this graphically, create a second copy of $[a_1,\ldots,a_n]$ and append it to the original, then plot $S_k$ vs $k$ for this new sequence having $2n$ elements: we will have $S_0=S_n=S_{2n}=0$. The rotation defined above corresponds to moving the horizontal axis to the line $y=S_{k^*}$, with the origin moving to $(k^*, S_{k^*})$.

Answer 2

By induction let $A=[a_1,\cdots,a_{n+1}]$

1. If for each $i$ we have $a_i\leq 0$ or $a_i+a_{i+1}\leq 0$ (with the notation $a_{n+2}=a_1$) then you can prove that for all $i$ $a_i=0$ or $a_i+a_{i+1}=0$:
   • if there exists some $i_0$ such that $a_{i_0}=0$ then you can apply induction on the rest because a difference by $0$ does not change anything
   • Otherwise $i$ $a_i\neq 0$ then $a_i+a_{i+1}=0$ for every $i$ and this implies that $a_i=(-1)^ia_1$ and you can just start by a positive term and you're done.
2. Otherwise there exist an index $i_0$ such that $a_{i_0}\geq 0$ and $a_{i_0}+a_{i_0+1}\geq 0$ in this cas apply induction hypothesis on: $$\left[a_1,\cdots,a_{i_0-1},a_{i_0}+a_{i_0+1},a_{i_0+2},\cdots, a_{n+1}\right] $$