# 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 $n$ numbers whose sum is 0.
Arrange them in a fixed order $(a_1,a_2,a_3,a_4...a_n)$ in a circular manner.

Show that there exists an integer m, such that $a_m, 1 \geq m \geq n$, and the sum of any number (1 to n) of consecutive terms starting with $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 $n$ numbers whose sum is 0.
Arrange them in a fixed order $(a_1,a_2,a_3,a_4...a_n)$ in a circular manner.

Show that there exists an integer m, such that $a_m, 1 \geq m \geq n$, and the sum of any number (1 to n) of consecutive terms starting with $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 $a_m$ would appear to be this:

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

$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 $s_i$ - that is greater than or equal to the rest. The last term which was reached to form this sum is the required $a_m$.

The proof depends upon the fact that $a_m = s_i - s_{i-1}$ and that the sum of $a_m$ followed by any number of clockwise terms will be $s_i - s_j$, for one of the other sums, $s_j$. And since $s_i$ is the greatest sum, $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 $a_m$ would appear to be this:

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

$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 $s_i$ - that is greater than or equal to the rest. The last term which was reached to form this sum is the required $a_m$.

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