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. Consider the function\[f(x_1, x_2, x_3, x_4, x_5)=\displaystyle\sum_{i=1}^5(x_i-x_{i+2})^2, x_6=x_1, x_7=x_2.\]Clearly $f>0$ always and $f$ is integer valued. Suppose, WLOG, that $y=x_4<0$. Then $f_{\text{new}}-f_{\text{old}}=2Sx_4<0$ since $S>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$. 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]

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1986 IMO (Problems) • Resources
Preceded by
Problem 2
1 2 3 4 5 6 Followed by
Problem 4
All IMO Problems and Solutions
Invalid username
Login to AoPS