Arranging numbers in a circle

**LegendWayne** · April 12th 2009, 09:13 AM

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?

Thanks in advance.

**Grandad** · April 13th 2009, 01:23 AM

Hello LegendWayne

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?

Thanks in advance.

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.

Grandad

**LegendWayne** · April 13th 2009, 02:20 AM

Originally Posted by Grandad

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.

Grandad

Yep it makes sense to me.

At first I was thinking about all the sums being negative, until I realized this cannot be so.

Thread: Arranging numbers in a circle

LinkBack

Thread Tools

Display

Arranging numbers in a circle

Similar Math Help Forum Discussions

arranging numbers problem

Numbers on a circle

Arranging k out of n chairs in a circle

Arranging numbers in a 3X9 grid

Arranging numbers in a grid

Search Tags