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.
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?
Originally posted by DejectionSurely the sum both before and after is a - b + c + k?
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.
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...