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
Let S be the sum of the absolute value of each set of adjacent vertices, so if the integers are a, b, c, d, e, then S = |a| + |b| + |c| + |d| + |e| + |a + b| + |b + c| + |c + d| + |d + e| + |e + a| + |a + b + c| + |b + c + d| + |c + d + e| + |d + e + a| + |e + a + b| + |a + b + c + d| + |b + c + d + e| + |c + d + e + a| + |d + e + a + b| + |e + a + b + c| + |a + b + c + d + e|. Then the operation reduces S, but S is a greater than zero, so the process must terminate in a finite number of steps. So see that S is reduced, we can simply write out all the terms. Suppose the integers are a, b, c, d, e before the operation, and a+b, -b, b+c, d, e after it. We find that we mostly get the same terms before and after (although not in the same order), so that the sum S' after the operation is S - |a + c + d + e| + |a + 2b + c + d + e|. Certainly a + c + d + e > a + 2b + c + d + e since b is negative, and a + c + d + e > -(a + 2b+ c + d + e) because a + b + c + d + e > 0.
S is not the only expression we can use. If we take T = (a - c)2 + (b - d)2 + (c - e)2 + (d - a)2 +(e - b)2, then after replacing a, b, c by a+b, -b, b+c, we get T' = T + 2b(a + b + c + d + e) < T. Thanks to Demetres Chrisofides for T
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
4 Sep 2002