To each vertex of a regular pentagon an integer is assigned in such a way that the sum of all of the 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: the numbers 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.
The answer says that it does come to an end after a finite number of steps.
Normally in these type of questions which involve transformations, one would look for an invariant, but I am having trouble in doing so. Is looking for an invariant/semi-invariant the right way to go? Or, is there any other way of looking at it ?
When the operation is performed the quantity decreases by $|x|+|z|−|x+y|−|y+z|$. The desired semi-invariant should include the absolute values of pairwise sums, sums of triples and foursomes as well. With a pentagon numbered $v,w, x, y, z$ and the semi-invariant defined by $$ S(v,w, x, y, z) = |v| + |w| + |x| + |y| + |z| + |v + w| + |w + x| + |x + y| + |y + z| + |z + v| + |v + w + x| + |w + x + y| + |x + y + z| + |y + z + v| + |z + v + w| + |v + w + x + y| + |w + x + y + z| + |x + y + z + v| + |y + z + v + w| + |z + v + w + x|, $$ it is evident that the operation reduced the value of $S$ by the expression $$ |z + v + w + x| − |z + v + w + x + 2y| = |s − y| − |s + y|,$$ where $$s = v + w + x + y + z $$ As $s > 0$ and $y < 0$, it is trivial that $$ |s − y| − |s + y| > 0$$ Thus $S$ is a semi-invariant with the required property. Using the semi-invariant, one can produce a proof by infinite descent.