Vertex of a pentagon-Does the algorithm always stop?

Question

To each vertex of a pentagon,we assign an integer $x_{i}$ with sum $s=\sum x_{i}>0$. If x,y,z are the numbers assigned to 3 successive vertices and if $y<0$,then we replace $(x,y,z)$ by $(x+y,-y,y+z)$.This step is repeated as long as there is a y<0.Decide if the algorithm always stops.

Answer 1

This is IMO 1986 Q3.

Consider the monovariant $S=\sum_{i=1}^{5}{(x_{i+2}-x_i)^2}$, where $x_6=x_1, x_7=x_2$.

WLOG suppose we perform an operation to get from $(x_1, x_2, x_3, x_4, x_5)$ to $(x_1+x_2, -x_2, x_2+x_3, x_4, x_5)$, and $S$ changes to $S'$. Then

\begin{align} S-S' &=(x_3-x_1)^2+(x_4-x_2)^2+(x_5-x_3)^2+(x_1-x_4)^2+(x_2-x_5)^2 \\ & -(x_3-x_1)^2-(x_4+x_2)^2-(x_5-x_2-x_3)^2-(x_1+x_2-x_4)^2-(-x_2-x_5)^2 \\ &=-2x_2(x_1+x_2+x_3+x_4+x_5) \\ & <0 \end{align}

since $s=\sum{x_i}>0$ and $x_2<0$.

Now $S$ is clearly a non-negative integer, and is strictly decreasing in each step, so the algorithm will always stop.

There is another solution using a different monovariant here.