1986 IMO Problems/Problem 3

Problem

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

Solution

The algorithm always stops. Indeed, consider the five numbers on the vertices of the pentagon as forming a $5$-tuple $\mathbf{x} = (x_1, x_2, x_3, x_4, x_5) \in \mathbb{Z}^5$. The sum of the five entries of this $5$-tuple is positive (by assumption), and stays unchanged through the entire process (since our operation does not change the sum); thus, it is always positive. Now, define the function $f : \mathbb{Z}^5 \to \mathbb{Z}$ by $$f(x_1, x_2, x_3, x_4, x_5)=\sum_{i=1}^5(x_i-x_{i+2})^2, \text{ where } x_6=x_1 \text{ and } x_7=x_2.$$ Clearly, $f \geq 0$ always. Now, let $\mathbf{x}_{\text{old}} = (x_1, x_2, x_3, x_4, x_5)$ and $\mathbf{x}_{\text{new}}$ be two consecutive $5$-tuples obtained in this process. Thus, $\mathbf{x}_{\text{new}}$ is obtained from $\mathbf{x}_{\text{old}}$ by applying our operation once. Suppose, WLOG, that $y=x_4<0$, and that the last three entries $x_3, x_4, x_5$ of $\mathbf{x}_{\text{old}}$ are replaced by $x_3 + x_4, -x_4, x_5 + x_4$ in $\mathbf{x}_{\text{new}}$. Let $S = x_1 + x_2 + x_3 + x_4 + x_5$ be the sum of all entries of $\mathbf{x}_{\text{old}}$ (or $\mathbf{x}_{\text{new}}$). Then, a straightforward computation shows that $f(\mathbf{x}_{\text{new}}) - f(\mathbf{x}_{\text{old}}) = 2Sx_4 < 0$ (since $S>0$ and $x_4 < 0$). Thus, if the algorithm does not stop, we can find an infinite decreasing sequence of nonnegative integers $f_0>f_1>f_2>\cdots$ (by applying $f$ to each of the $5$-tuples). This is impossible, so the algorithm must stop. $\Box$

This solution was posted and copyrighted by tc1729. The original thread for this problem can be found here: [1]