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]

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

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

Page

Toolbox

Search

1986 IMO Problems/Problem 3

Problem

Solution

See Also