Integer Iterations on Circle III

Here is Problem #3 from the 1986 International Mathematical Olympiad:

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.

Here is an applet to play with. The applet generally displays five numbers that satisfy the conditions of the problem. You can modify them manually by clicking or dragging (when the box "Adjust numbers" is checked) the mouse next to each number's vertical midline. To perform the algorithmic step click on a negative number.

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Integer Iterations on Circle III

What if applet does not run?

A few words.

What if applet does not run?

According to [Engel, p. 6], this was the most difficult problem at the 1986 olympiad. Eleven participants solved the problem, with ten of them coming up with one solution and one following a completely different approach.

On solution was based on the behavior of the function

f(x) = f(x₁, x₂, x₃, x₄, x₅) = ∑(x_k - x_{k + 2})², x₆ = x₁, x₇ = x₂,

and the sum taken from k = 1 through k = 5.

Assume x₄ < 0 and consider what happens to f when the algorithm prescribed in the problem has been applied to x₄. Denote the new values y₁, ..., y₅:

	y₁	= x₁,
	y₂	= x₂,
	y₃	= x₃ + x₄,
	y₄	= -x₄,
	y₅	= x₅ + x₄.

We are going to compute

f(y) - f(x) = ∑(y_k - y_{k + 2})² - ∑(x_k - x_{k + 2})²

term by term using a² - b² = (a - b)(a + b):

	(y₁ - y₃)² - (x₁ - x₃)²	= -x₄(2x₁ - 2x₃ - x₄),
	(y₂ - y₄)² - (x₂ - x₄)²	= 4x₄x₂,
	(y₃ - y₅)² - (x₃ - x₅)²	= 0,
	(y₄ - y₁)² - (x₄ - x₁)²	= 4x₄x₁,
	(y₅ - y₂)² - (x₅ - x₂)²	= x₄(2x₅ + x₄ - 2x₂).

Summing up all five gives

f(y) - f(x) = 2x₄(x₁ + x₂ + x₃ + x₄ + x₅) < 0,

meaning that f is a strictly decreasing function: f(y) < f(x). Now, f being the sum of squares, is never negative and this is clearly impossible to construct an infinite decreasing sequence of its values, which shows that the iterations must stop, sooner or later.

This solution has been included into the The IMO Compendium. Another solution (by Bernard Chazelle from Princeton, NJ) tells us how soon.

Consider an infinite multiset S of all sums s(k, m), with m > k, where

s(k, m) = x_k + ... + x_{m - 1}, k = 1, ..., 5.

An iteration either does not change an element of S, or swaps it with another element; this with the exception of the element to which the iteration applies. The latter element changes its sign. So, from the point of view of set S, each iteration causes just one modification: a change of a sign in a single element. Assuming again that the iteration applies at x₄ < 0, the only element of S that undergoes a change is s(4, 5). Since the sum of all x's is positive, there is in S only a finite number of negative elements. Thus the iterations must stop after the number of steps equal to the initial number of negative elements of S.

This solution shows that the numbers need not be integers; it applies to real numbers as well.

The problem and its relation to state-of-th-art mathematical research in celluar automata are the topic of Stanislav Smirnov's chapter in An Invitation to Mathematics. Stanislav was one of the participants of the olympiad who did solve the problem.

References

D. Djukic et al, The IMO Compendium, Springer, 2011 (Second edition)
A. Engel, Problem-Solving Strategies, Springer, 1998
D. Schleicher, M. Lackmann, An Invitation to Mathematics, Springer, 2011

72088977