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]

Solution 2 (Semi-Invariants)

The key idea of this proof is to create an positive integer valued semi-invariant that decreases (strictly) as we preform the operation. Then the existence of the semi-invariant would guarantee the finiteness (note that the integer valued condition is needed).

We see that the sum of all five integers is a invariant, so we see if the sum of the absolute values work. Unfortunately, as the operation is performed, the sum of the absolute values decrease by $|x|+|z|-|x+y|-|y+z|$ after each operation (which is not always positive). This suggest we use pairwise sums as well. Upon testing that, we note that sums of triples and quadriples should be included as well. We see the semi-invariant

$S=|v|+|w|+|x|+|y|+|z|+|v+w|+|w+x|+|x+y|+|y+z|+|v+w+x|+|w+x+y|+|x+y+z|+|y+z+w|+|z+v+w|+|v+w+x+y|+|w+x+y+z|+|x+y+z+v|+|y+z+v+w|+|z+v+w+x|$

is reduced by $|(v+w+x+y+z)-y|-|(v+w+x+y+z)+y|$ after the operation, and that is positive. (Note that not all sums appeared in the semi-invariant) The result follows.

Typed by Ddk001.

Note that J. Keane, a former member of the US team, was awarded a special prize for this solution.

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

Contents

Problem

Solution

Solution 2 (Semi-Invariants)

See Also