24 1 Methods of Proof
Notice that the sum of the five numbers on the pentagon is preserved by the operation,
so it is natural to look at the sum of the absolute values of the five numbers. When the
operation is performed this quantity decreases by|x|+|z|−|x+y|−|y+z|. Although this
expression is not always positive, it suggests a new choice. The desired semi-invariant
should include the absolute values of pairwise sums as well. Upon testing the new
expression and continuing this idea, we discover in turn that the desired semi-invariant
should also include absolute values of sums of triples and foursomes. At last, with a
pentagon numberedv, w, x, y, zand 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|,wefind that the operation reduces the value ofSby the simple expression|z+v+w+
x|−|z+v+w+x+ 2 y|=|s−y|−|s+y|, wheres=v+w+x+y+z. Since
s>0 andy<0, we see that|s−y|−|s+y|>0, soShas the required property. It
follows that the operation can be performed only finitely many times.
Using the semi-invariant we produced a proof based on Fermat’s infinite descent
method. This method will be explained in the Number Theory chapter of this book. Here
the emphasis was on the guess of the semi-invariant. And now some problems.
77.A real number is written in each square of ann×nchessboard. We can perform
the operation of changing all signs of the numbers in a row or a column. Prove that
by performing this operation a finite number of times we can produce a new table
for which the sum of each row or column is positive.
78.Starting with an ordered quadruple of integers, perform repeatedly the operation(a,b,c,d)
T
−→(|a−b|,|b−c|,|c−d|,|d−a|).Prove that after finitely many steps, the quadruple becomes( 0 , 0 , 0 , 0 ).
79.Several positive integers are written on a blackboard. One can erase any two distinct
integers and write their greatest common divisor and least common multiple instead.
Prove that eventually the numbers will stop changing.
80.Consider the integer lattice in the plane, with one pebble placed at the origin. We
play a game in which at each step one pebble is removed from a node of the lattice
and two new pebbles are placed at two neighboring nodes, provided that those nodes
are unoccupied. Prove that at any time there will be a pebble at distance at most 5
from the origin.