5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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^*})$.

Graphical illustration of "good" rotation

$\endgroup$
  • $\begingroup$ I'm not sure I completely follow. $k^*$ is a value of $k$ that satisfies that $S_k$ is minimal. Why does that mean that the rotation would satisfy my condition? $\endgroup$ – Oria Gruber Apr 2 '15 at 18:14
  • $\begingroup$ If $S_{k*} \le S_k$ for all $k$ then the partial sums for the rotation $[a_{k^*+1}, a_{k^*+2}, \ldots,a_{k^*}]$ will all be non-negative. To see this, my suggestion is to draw a graph of $y=S_k$ for $k=1,\ldots,2n$, and then draw the line $y=S_{k^*}$ on the same graph. Now imagine that the origin of the coordinate system is moved to the point $(k^*, S_{k^*})$. You will then have a plot of the partial sums of the rotated array. $\endgroup$ – grand_chat Apr 2 '15 at 18:27
0
$\begingroup$

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] $$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.