1. Joined
    25 Aug '06
    Moves
    0
    20 Jun '08 15:341 edit
    The vertices of a polygon are labeled with real numbers, the sum of which is positive. At any time, you may change the sign of a negative label, but then the new value is subtracted from both neighbors' values.
    Example: if three consecutive labels are 1, -2, 0, then you may change in one move the -2 to 2, the 1 to -1 and the 0 to -2.
    Prove that:
    1. No matter which labels are flipped, the process will terminate after finitely many flips, when all labels will be non-negative. The process cannot go on forever.
    2. Moreover, for given initial labels, the process terminates in exactly the same number of moves regardless of choices.
    3. The final configuration is independent of choices as well.
  2. Joined
    12 Sep '07
    Moves
    2668
    20 Jun '08 16:411 edit
    Let S be the sum of the numbers on all vertices. Suppose we flip a the vertices a, -b and c, where -b is negative. The new values are now a-b, b and c-b. Let k be the sum of all the vertices not inculding a, b and c. Before out flip, the sum S=a+b+c+k. After the flip the sum S1=a-b+c+k. Clearly S1 < S as b is strictly less than 0.

    Therefore, after every flip, the sum S decreases. Since there are only a finite number of possible sums S, S will eventually be able to decrease no further, meaning no furthur moves are possible.

    EDIT: Um... are there only a finite number of possible S? Hm... I'm sure that's true, but how to prove it?
  3. Joined
    07 Sep '05
    Moves
    35068
    20 Jun '08 19:32
    Originally posted by Dejection
    Let S be the sum of the numbers on all vertices. Suppose we flip a the vertices a, -b and c, where -b is negative. The new values are now a-b, b and c-b. Let k be the sum of all the vertices not inculding a, b and c. Before out flip, the sum S=a+b+c+k. After the flip the sum S1=a-b+c+k. Clearly S1 < S as b is strictly less than 0.
    Surely the sum both before and after is a - b + c + k?
  4. Joined
    12 Sep '07
    Moves
    2668
    20 Jun '08 23:14
    You're right, of course. Silly me.
  5. Joined
    12 Sep '07
    Moves
    2668
    21 Jun '08 02:211 edit
    Um. Are you sure that it is always finite? It seems that you can make the number of moves as large as you want, by having three vertices n+1, -n and 0. This takes 2n moves to become 1, 0, 0.

    EDIT: Oh of course. Arbitrarily large is not the same as infinitely large. Hm...
Back to Top