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
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.
What if applet does not run? |
|Contact| |Front page| |Contents| |Algebra| |Store|
Copyright © 1996-2017 Alexander Bogomolny
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
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_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = ∑(x_{k} - x_{k + 2})², x_{6} = x_{1}, x_{7} = x_{2},
and the sum taken from k = 1 through k = 5.
Assume x_{4} < 0 and consider what happens to f when the algorithm prescribed in the problem has been applied to x_{4}. Denote the new values y_{1}, ..., y_{5}:
y_{1} | = x_{1}, | |
y_{2} | = x_{2}, | |
y_{3} | = x_{3} + x_{4}, | |
y_{4} | = -x_{4}, | |
y_{5} | = x_{5} + x_{4}. |
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_{1} - y_{3})² - (x_{1} - x_{3})² | = -x_{4}(2x_{1} - 2x_{3} - x_{4}), | |
(y_{2} - y_{4})² - (x_{2} - x_{4})² | = 4x_{4}x_{2}, | |
(y_{3} - y_{5})² - (x_{3} - x_{5})² | = 0, | |
(y_{4} - y_{1})² - (x_{4} - x_{1})² | = 4x_{4}x_{1}, | |
(y_{5} - y_{2})² - (x_{5} - x_{2})² | = x_{4}(2x_{5} + x_{4} - 2x_{2}). |
Summing up all five gives
f(y) - f(x) = 2x_{4}(x_{1} + x_{2} + x_{3} + x_{4} + x_{5}) < 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) = 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
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
|Contact| |Front page| |Contents| |Algebra| |Store|
Copyright © 1996-2017 Alexander Bogomolny
61181999 |