The Art and Craft of Problem Solving

104 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

Now we define two sequences. For r = 2,3, ... , define

Lr := max{Ji : i > tr-t} and tr := min{t > tr-J : fr = Lr}.

(In our example, L2 = 5, t2 = 6 and L 3 = 4, t 3 = 8.) As above, we assert that as long

as Lr > 1, if t > fr, then fr < Lr (for each r 2 I).

Therefore, the sequence LJ ,L2, '" is strictly decreasing, hence one of the Lr will

equal 1 , so eventually, fm = 1 for some m. _

We will conclude the chapter with a wonderfully imaginative use of monovariants,

John Conway's famous "Checker Problem."

Example 3.4. 16 Put a checker on every lattice point (point with integer coordinates)

in the plane with y-coordinate less than or equal to zero. The only legal moves are hor­

izontal or vertical "jumping." By this we mean that a checker can leap over a neighbor,

ending up two units up, down, right, or left of its original position, provided that the

destination point is unoccupied. After the jump is complete, the checker that was

jumped over is removed from the board. Here is an example.

·.....

:"· 'O. 'O. O. 'O. " '�.

:

···

0

·

0

· 'O

"

'�

·.....

:

"

'O'O'O'O

"

'�

·.....

:

"

'O'O'O'O"'�

·.....

. ......... ..... ....... ...... ........
hefore jump

:·····:·····:··· 0 ···:·····:

·.....

:"· 'O. 'O. " 'f". 'O". ':.

:"

'

O

'O

"

'

f"

'

O"

'

·.... [.

i" 'O'O'O'

O"

'�

·.....

i

"

'O'O'O'O

"

'�

·.....

'0 ••••••••. •••••••••••••••••••••....

after jump

Is it possible to make a finite number of legal moves and get a checker to reach the line

y=5?

Solution: After experimenting, it is pretty easy to get a checker to y = 2, and a

lot more work can get a checker to y = 3. But these examples shed no light on what is

and what isn't possible.

The key idea: define a monovariant that assigns a number to each configuration of

checkers, one that moves in one direction as we approach our goal.

Without loss of generality, let the destination point be C = (0,5). For each point

(x,y) in the plane, compute its "taxicab distance" (length of the shortest path that

stays on the lattice grid lines) to C. For example, the distance from (3,4) to (0,5) is

3 + 1 = 4. Assign to each point at a distance d from C the value /;d, where

/;

= -1+ 0

2

.