IMO 1986 P3: To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=\sum x_i>0$. If $x,y,z$ are numbers assigned to three 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. (Most difficult problem of the IMO).
How can we use the following monovariant for solving the above question?
$g(x)$$=$$\sum_{i=1}^{5}$$\sum_{j=1}^{5}$$|x_i+x_{i+1}.........x_{j-1}|$
I tried my best, but I am not able relate the following function with the question.
Let $S = \{v,w,x,y,z\}$ denote the ordered set of 5 integers on the pentagon vertices. We are allowed to perform one operation on $S$, which is to take three numbers $x,y,z$ on any three consecutive vertices, and replace them by $x+y, -y, z+y$. If $\rho$ denotes an operation, we denote the result of this operation as $\rho \cdot S$.
The key property of $g(S)$ is that no matter what operation $\rho$ we perform, $g(S)$ is strictly decreasing, i.e. $g(\rho \cdot S) < g(S)$. To show this, one just needs to calculate it out and see that if $v,w,x,y,z$ are the numbers on the vertices, $y < 0$, and we do the operation on the three integers $x,y,z$, then $$g(S) - g(\rho \cdot S) = |v+w+x+z| - |v+w+x+z+2y| $$ and this quantity is strictly positive since $y < 0$.
Thus, $g(S)$ can only decrease finitely many times before reaching zero, which implies that only finite many operations can be performed on $S$.