Integer Iterations on Circle IIIHere 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.
 |Contact| |Front page| |Contents| |Algebra| |Store| Copyright © 1996-2012 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
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(x1, x2, x3, x4, x5) = ∑(xk - xk + 2)², x6 = x1, x7 = x2, and the sum taken from k = 1 through k = 5. Assume x4 < 0 and consider what happens to f when the algorithm prescribed in the problem has been applied to x4. Denote the new values y1, ..., y5:
We are going to compute f(y) - f(x) = ∑(yk - yk + 2)² - ∑(xk - xk + 2)² term by term using a² - b² = (a - b)(a + b):
Summing up all five gives f(y) - f(x) = 2x4(x1 + x2 + x3 + x4 + x5) < 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) = xk + ... + xm - 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
|Contact| |Front page| |Contents| |Algebra| |Store| Copyright © 1996-2012 Alexander Bogomolny |
| 41143662 |
