# Arranging numbers in a circle

• Apr 12th 2009, 09:13 AM
LegendWayne
Arranging numbers in a circle
Here's a question I found from a Chinese book, (which contains no answers), and I found it to be very interesting.

Suppose we have $\displaystyle n$ numbers whose sum is 0.
Arrange them in a fixed order $\displaystyle (a_1,a_2,a_3,a_4...a_n)$ in a circular manner.

Show that there exists an integer m, such that $\displaystyle a_m, 1 \geq m \geq n$, and the sum of any number (1 to n) of consecutive terms starting with $\displaystyle a_m$ is non-negative. (Clockwise direction)

It seems that it is true, after trying with a few numbers.
How do you actually prove it?

• Apr 13th 2009, 01:23 AM
(Evilgrin)Hello LegendWayne
Quote:

Originally Posted by LegendWayne
Here's a question I found from a Chinese book, (which contains no answers), and I found it to be very interesting.

Suppose we have $\displaystyle n$ numbers whose sum is 0.
Arrange them in a fixed order $\displaystyle (a_1,a_2,a_3,a_4...a_n)$ in a circular manner.

Show that there exists an integer m, such that $\displaystyle a_m, 1 \geq m \geq n$, and the sum of any number (1 to n) of consecutive terms starting with $\displaystyle a_m$ is non-negative. (Clockwise direction)

It seems that it is true, after trying with a few numbers.
How do you actually prove it?

I don't have a formal proof for you (it wants tidying up a bit!), but the algorithm for finding $\displaystyle a_m$ would appear to be this:

Starting at $\displaystyle a_n$, and moving anti-clockwise, form consecutive sums consisting of $\displaystyle 1, 2, ..., n$ terms:

$\displaystyle s_1=a_n,\quad s_2=a_n + a_{n-1},\quad s_3= a_n + a_{n-1} + a_{n-2},\quad ...,\quad s_n= a_n+ a_{n-1}+\, ... +a_1=0$

Then there is at least one of these consecutive sums - call it $\displaystyle s_i$ - that is greater than or equal to the rest. The last term which was reached to form this sum is the required $\displaystyle a_m$.

The proof depends upon the fact that $\displaystyle a_m = s_i - s_{i-1}$ and that the sum of $\displaystyle a_m$ followed by any number of clockwise terms will be $\displaystyle s_i - s_j$, for one of the other sums, $\displaystyle s_j$. And since $\displaystyle s_i$ is the greatest sum, $\displaystyle s_i - s_j$ will never be negative.

• Apr 13th 2009, 02:20 AM
LegendWayne
Quote:

(Evilgrin)Hello LegendWayneI don't have a formal proof for you (it wants tidying up a bit!), but the algorithm for finding $\displaystyle a_m$ would appear to be this:

Starting at $\displaystyle a_n$, and moving anti-clockwise, form consecutive sums consisting of $\displaystyle 1, 2, ..., n$ terms:

$\displaystyle s_1=a_n,\quad s_2=a_n + a_{n-1},\quad s_3= a_n + a_{n-1} + a_{n-2},\quad ...,\quad s_n= a_n+ a_{n-1}+\, ... +a_1=0$

Then there is at least one of these consecutive sums - call it $\displaystyle s_i$ - that is greater than or equal to the rest. The last term which was reached to form this sum is the required $\displaystyle a_m$.

The proof depends upon the fact that $\displaystyle a_m = s_i - s_{i-1}$ and that the sum of $\displaystyle a_m$ followed by any number of clockwise terms will be $\displaystyle s_i - s_j$, for one of the other sums, $\displaystyle s_j$. And since $\displaystyle s_i$ is the greatest sum, $\displaystyle s_i - s_j$ will never be negative.