Advanced book on Mathematics Olympiad

356 Methods of Proof

(a, 0 , 0 , d), (a, 0 , 0 , a), (a, 0 ,a, 0 ), (a, 0 ,c,a),

and their cyclic permutations.
At the third step these quadruples become

(a, 0 ,d,|d−a|), (a, 0 ,a, 0 ), (a, a, a, a), (a, c,|c−a|, 0 ).

The second and the third quadruples become( 0 , 0 , 0 , 0 )in one and two steps, respectively.
Now let us look at the first and the last. By our discussion, unless they are of the form
(a, 0 ,a, 0 )or(a, a, 0 , 0 ), respectively, the semi-invariant will decrease at the next step.
So unless it is equal to zero,Scan stay unchanged for at most five consecutive steps. If
initiallyS=m, after 5msteps it will be equal to zero and the quadruple will then be
( 0 , 0 , 0 , 0 ).

79.Ifa, bare erased andc<dare written instead, we havec≤min(a, b)andd≥
max(a, b). Moreover,ab= cd. Using derivatives we can show that the function
f(c)=c+abc is strictly decreasing on( 0 ,a+ 2 b), which impliesa+b≤c+d. Thus the
sum of the numbers is nondecreasing. It is obviously bounded, for example byntimes
the product of the numbers, wherenis the number of numbers on the board. Hence the
sum of the numbers eventually stops changing. At that moment the newly introducedc
anddshould satisfyc+d=a+bandcd=ab, which means that they should equala
andb. Hence the numbers themselves stop changing.
(St. Petersburg City Mathematical Olympiad, 1996)

80.To a configuration of pebbles we associate the number

S=

∑ 1

2 |i|+|j|

,

where the sum is taken over the coordinates of all nodes that contain pebbles. At one
move of the game, a node(i, j )loses its pebble, while two nodes(i 1 ,j 1 )and(i 2 ,j 2 )gain
pebbles. Since either the first coordinate or the second changes by one unit,|ik|+|jk|≤
|i|+|j|+1,k= 1 ,2. Hence

1

2 |i|+|j|

=

1

2 |i|+|j|+^1

+

1

2 |i|+|j|+^1

≤

1

2 |i^1 |+|j^1 |

+

1

2 |i^2 |+|j^2 |

,

which shows thatSis a nondecreasing semi-invariant. We will now show that at least one
pebble is inside or on the boundary of the squareRdetermined by the linesx±y=±5.
Otherwise, the total value ofSwould be less than

∑

|i|+|j|> 5

1

2 |i|+|j|

= 1 + 4

∑∞

i= 1

∑∞

j= 0

1

2 i+j

−

∑

|i|+|j|≤ 5

1

2 |i|+|j|