Methods of Proof 351the sum of the squares of the numbers in a triple is invariant under the operation. The
sum of squares of the first triple is^92 and that of the second is 6+ 2√
2, so the first triple
cannot be transformed into the second.
(D. Fomin, S. Genkin, I. Itenberg,Mathematical Circles, AMS, 1996)
68.Assign the valueito each white ball,−ito each red ball, and−1 to each green ball.
A quick check shows that the given operations preserve the product of the values of the
balls in the box. This product is initiallyi^2000 =1. If three balls were left in the box,
none of them green, then the product of their values would be±i, a contradiction. Hence,
if three balls remain, at least one is green, proving the claim in part (a). Furthermore,
because no ball has value 1, the box must contain at least two balls at any time. This
shows that the answer to the question in part (b) isno.
(Bulgarian Mathematical Olympiad, 2000)
69.LetIbe the sum of the number of stones and heaps. An easy check shows that the
operation leavesIinvariant. The initial value is 1002. But a configuration withkheaps,
each containing 3 stones, hasI=k+ 3 k= 4 k. This number cannot equal 1002, since
1002 is not divisible by 4.
(D. Fomin, S. Genkin, I. Itenberg,Mathematical Circles, AMS, 1996)
70.The quantityI=xv+yudoes not change under the operation, so it remains equal to
2 mnthroughout the algorithm. When the first two numbers are both equal to gcd(m, n),
the sum of the latter two isgcd^2 (m,n)mn =2 lcm(m, n).
(St. Petersburg City Mathematical Olympiad, 1996)
71.We can assume thatpandqare coprime; otherwise, shrink the size of the chessboard
by their greatest common divisor. Place the chessboard on the two-dimensional integer
lattice such that the initial square is centered at the origin, and the other squares, assumed
to have side length 1, are centered at lattice points. We color the chessboard by the Klein
four groupK={a, b, c, e|a^2 =b^2 =c^2 =e, ab=c, ac=b, bc=a}as follows: if
(x, y)are the coordinates of the center of a square, then the square is colored byeif both
xandyare even, bycif both are odd, byaifxis even andyis odd, and bybifxis odd
andyis even (see Figure 55). Ifpandqare both odd, then at each jump the color of
the location of the knight is multiplied byc. Thus afternjumps the knight is on a square
colored bycn. The initial square was colored bye, and the equalitycn=eis possible
only ifnis even.
If one ofpandqis even and the other is odd, then at each jump the color of the square
is multiplied byaorb. Afternjumps the color will beakbn−k. The equalityakbn−k=e
impliesak=bn−k, so bothkandn−khave to be even. Therefore,nitself has to be
even. This completes the solution.
(German Mathematical Olympiad)
72.The invariant is the 5-colorability of the knot, i.e., the property of a knot to admit a
coloring by the residue classes modulo 5 such that