1986 IMO Problems/Problem 3

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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]