IMO 1986 SL 12

Origin: GDR

Problem

To each vertex Pi (i = 1, . . . , 5) of a pentagon an integer xi is assigned, the sum s =  xi being positive. The following operation is allowed, provided at least one of the xi’s is negative: Choose a negative xi, replace it by −xi, and add the former value of xi to the integers assigned to the two neighboring vertices of Pi (the remaining two integers are left unchanged). This operation is to be performed repeatedly until all negative integers disappear. Decide whether this procedure must eventually terminate.

Solution

We define f(x1, . . . , x5) = 5 i=1(xi+1 −xi−1)2 (x0 = x5, x6 = x1). Assuming that x3 < 0, according to the rules the lattice vector X = (x1, x2, x3, x4, x5) changes into Y = (x1, x2 + x3, −x3, x4 + x3, x5). Then f(Y ) −f(X) = (x2 + x3 −x5)2 + (x1 + x3)2 + (x2 −x4)2 +(x3 + x5)2 + (x1 −x3 −x4)2 −(x2 −x5)2 −(x3 −x1)2 −(x4 −x2)2 −(x5 −x3)2 −(x1 −x4)2 = 2x3(x1 + x2 + x3 + x4 + x5) = 2x3S < 0. Thus f strictly decreases after each step, and since it takes only positive integer values, the number of steps must be finite. Remark. One could inspect the behavior of g(x) = 5 i=1 5 j=1 |xi+xi+1+ \cdot \cdot \cdot + xj−1| instead. Then g(Y ) −g(X) = |S + x3| −|S −x3| > 0.