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 respectively, and , then the following operation is allowed: are replaced by 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 -tuple . The sum of the five entries of this -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 by Clearly, always. Now, let and be two consecutive -tuples obtained in this process. Thus, is obtained from by applying our operation once. Suppose, WLOG, that , and that the last three entries of are replaced by in . Let be the sum of all entries of (or ). Then, a straightforward computation shows that (since and ). Thus, if the algorithm does not stop, we can find an infinite decreasing sequence of nonnegative integers (by applying to each of the -tuples). This is impossible, so the algorithm must stop.
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.
See Also
1986 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |