Results 1 to 3 of 3

Math Help - Arranging numbers in a circle

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    11

    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?

    Thanks in advance.
    Last edited by mr fantastic; April 18th 2009 at 02:06 PM. Reason: Restored the question deleted by the OP.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello LegendWayne
    Quote Originally Posted by LegendWayne View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    11
    Quote Originally Posted by Grandad View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. arranging numbers problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 15th 2011, 02:21 AM
  2. Numbers on a circle
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 26th 2011, 12:35 AM
  3. Arranging k out of n chairs in a circle
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 11th 2011, 05:30 PM
  4. Arranging numbers in a 3X9 grid
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 18th 2010, 07:41 AM
  5. Arranging numbers in a grid
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 21st 2010, 07:03 AM

Search Tags


/mathhelpforum @mathhelpforum