The Art and Craft of Problem Solving

3.4 INVARIANTS 105

There are three crucial things about S'. First of all, it satisfies

S'^2 +S' - 1 =0.

Also, it is positive. And finally, S' < 1.

(2)

For any (infinite) configuration of checkers, add up all the values assigned to each
checker on the board. Let us call this the "Conway sum." This, we claim, is our
monovariant. We need to check a number of things.
First of all, does this sum exist? Yes; we have infinitely many infinite geometric
series to consider,^6 but luckily, they will converge. Let us compute the Conway sum
for the starting configuration. The checkers on the y-axis (directly below C) have

the values S's, S'^6 ,. ... In general, the checkers on the line x = ±r have the values

S'S+r, S'^6 +r, .... Hence the Conway sum for the whole "half-plane" is

(^00) rS 00 rS+r

(S's+S'^6 + ... )+^2 �(S's+r +S'^6 +r + ... ) = -'='-+2 � -'='-

r=1 1 -S' r=1 1 -S'

_ 1 ( s 2S'^6 )

• 1-S'

S'+

I -S'

= _

1

_

(S'S(1-S') +2S'^6 )

1-S' 1-S'

= _

1 (S'S+S'^6 )

.

1 -S' 1-S'

Using (2), we observe that 1 - S' = S'^2. Therefore the expression above simplifies to

S's � S'^6

= S' + S'^2 = 1.

Thus, the starting configuration has Conway sum 1, and all other configurations will
have computable Conway sums.
Next, we must show that the Conway sum is a monovariant. Consider a horizontal
move that moves a checker away from the destination point C. For example, suppose
we could jump a checker from (9,3), which has value S'll, to (11,3). What happens
to the Conway sum? We remove the checkers at (9,3) and (10, 3) and create a checker
at (1 1,3). The net change in the Conway sum is

• S'^11 - S'^12 + S'^13 = S' II ( - (^1) - S' + S'^2 ).

But -1-S' + S'^2 = -2S', by (2). Consequently, the net change is negative; the sum

decreases. Clearly this is a general situation (check the other cases if you are not sure):
whenever a checker moves away from C, the sum decreases.
On the other hand, if the checker moves toward C, the situation is different. For
example, suppose we went from (9,3) to (7,3). Then we remove the checkers at (9,3)
and (8,3) and create a checker at (7,3), changing the sum by

• S'^11 - S'1O + S'^9 = S'^9 (1 -S' - S'^2 ) = o.

(^6) See page 160 for infonnation about infinite geometric series.