Advanced book on Mathematics Olympiad

1.5 Invariants and Semi-Invariants 23

73.In the squares of a 3×3 chessboard are written the signs+and−as described in

Figure 11(a). Consider the operations in which one is allowed to simultaneously

change all signs in some row or column. Can one change the given configuration

to the one in Figure 11(b) by applying such operations finitely many times?

(a) (b)

Figure 11

74.The number 99...99 (having 1997 nines) is written on a blackboard. Each minute,

one number written on the blackboard is factored into two factors and erased, each

factor is (independently) increased or decreased by 2, and the resulting two numbers

are written. Is it possible that at some point all of the numbers on the blackboard

are equal to 9?

75.Four congruent right triangles are given. One can cut one of them along the altitude

and repeat the operation several times with the newly obtained triangles. Prove that

no matter how we perform the cuts, we can always find among the triangles two

that are congruent.

76.For an integern≥4, consider ann-gon inscribed in a circle. Dissect then-gon

inton−2 triangles by nonintersecting diagonals. Prove that the sum of the radii of

the incircles of thesen−2 triangles does not depend on the dissection.

In some cases a semi-invariant will do. Asemi-invariantis a quantity that, although
not constant under a specific transformation, keeps increasing (or decreasing). As such
it provides a unidirectional obstruction.
For his solution to the following problem from the 27th International Mathematical
Olympiad, J. Keane, then a member of the US team, was awarded a special prize.

Example.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 numbersx, y, z, respectively, andy<0, then the following operation is allowed:
the numbersx, y, zare replaced byx+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.The answer is yes. The key idea of the proof is to construct an integer-valued
semi-invariant whose value decreases when the operation is performed. The existence
of such a semi-invariant will guarantee that the operation can be performed only finitely
many times.