A game is played on a 2001 x 2001 board as follows. The first player's piece is the policeman, the second player's piece is the robber. Each piece can move one square south, one square east or one square northwest. In addition, the policeman (but not the robber) can move from the bottom right to the top left square in a single move. The policeman starts in the central square, and the robber starts one square diagonally northeast of the policeman. If the policeman moves onto the same square as the robber, then the robber is captured and the first player wins. However, the robber may move onto the same square as the policeman without being captured (and play continues). Show that the robber can avoid capture for at least 10000 moves, but that the policeman can ultimately capture the robber.
Solution
Color the squares with three colors as follows:
0 1 2 0 1 2 0 ... 2 1 2 0 1 2 0 1 ... 0 2 0 1 2 0 1 2 ... 1 0 1 2 0 1 2 0 ... 2 1 2 0 1 2 0 1 ... 0 ... 2 0 1 2 0 1 2 ... 1The middle square is color 2 (moving 999+1 squares E from the top left increases the color by 1, then moving 999+1 S increases it by another 1) and the square immediately NE of it is also 2. So both P and R start on color 2. Note that any move increases the color by 1 mod 3, except for P's special move which changes the color from 1 to 0.
Until P has made this move, after each move of P, P's color is always 1 more than R's color (mod 3), so P cannot win (irrespective of the moves made by either player). Immediately after he makes the special move for the first time, P is on color 0 and R is on color 1, so immediately after his move P's color is now 1 less than R's color mod 3. Again P cannot win. But after P has made the special move for the second time, P's color is the same as R's (mod 3) immediately after P's move.
Note that it takes P at least 2001 moves to complete his special move for the first time and at least 6002 moves (in total) to complete his special move for the second time. This solves the first part of the question. Suppose R just moves down to the bottom right and then moves in small circles (one move NW, one move S, one move E) waiting for P. It takes P at least 6002 + 3999 (moving from top left to the capture square, one square short of the bottom right) = 10001 to capture him, so R makes at least 10000 moves before being captured.
We claim that P wins if he can get into any of the positions shown below relative to R, with R to move (*):
x P x x x P x x P x x x R x x x P x x P x x x P xIf follows that P can also win from the four positions below (**):
x x x P x x x x x x x x x x x x x x x x x P x x R x x P x x x x x x x x x x x x x x x x x P x x xFor in each case at least one of R's possible moves allow P to move immediately into one of the winning positions at (*). But R can only make the other moves a limited number of times before running into the border. [That is obvious if the other two moves are E and S. If they are NW and E, then every NW move takes R closer to the top border, but his total number of E moves can never exceed his total number of NW moves by more than 2000 because of the right border. Similarly, for NW and S.]
Now let d be the number of rows plus the number of columns that R and P are apart. It is easy to check that the positions in (*) and (**) represent the only possibilities for d = 2 and 3. We show that P can always get to d = 2 or 3. For P can always copy R's move, so he can certainly move so that d never increases. But one of R's moves will always allow P to decrease d by 1 or 2. There are three cases to consider:
Case 1. If P is east of R and R moves E, then P moving NW will decrease d by 1 or 2. That is not possible if P is in the top row, but then moving S will decrease d by 2 unless R is also in the top row. If both are in the top row, then P moves S. Now after R's next move, P moves NW which reduces d by 2.
Case 2. If P is south of R and R moves S, then a similar argument, shows that P can always decrease d by 1 or 2 in one or two moves.
Case 3. If P is not south or east or R, and R moves NW, then P can always decrease d by 1 or 2 by moving S or E.
But repeated decreases by 1 or 2 must bring d ultimately to 2 or 3 and hence to one of (*) or (**). So P can always win.
It remains to prove the claim that (*) are winning positions. The reason is that in each case R has one move blocked off, so must make one of the other two. P then copies R's move, so next turn R has the same move blocked off. Repeated use of the other two moves will bring him ultimately to one of the sides.
We start with the easiest case: in the two following positions. R cannot move to z, so he must move east or south on each move. Hence he will (after at most 4000 moves) reach the bottom right corner. He then loses moving out of it.
x P x P z x x x RThe other cases of (*) are slightly more complicated. Starting from either of the two positions below, we show that R must eventually reach the extreme left column.
w x P x x R z x x y x PR cannot move to z, so he can only make NW and S moves. But his total number of S moves can never exceed his total number of NW moves by more than 2000 because he cannot move off the bottom of the board, so he must eventually reach the extreme left column. [If he reaches the bottom row at y, then P can always move to z to preserve the configuration. If R reaches the top row by moving to w, then P can always move to z to preserve the configuration.]
Having reached the extreme left column he is forced to move south. Eventually moving to y will take him to the corner. P then moves to z and R is captured on his next move.
The final case to consider is the two positions below. R cannot move to z, so must move E or NW. A similar argument to the previous case shows that he must eventually reach the top row. Having reached it at w, P moves to z. So R is forced to move right along the top row. When he reaches the corner at y, P moves to z and R is captured when he moves out of the corner.
w x x x R y P z x x x P
© John Scholes
jscholes@kalva.demon.co.uk
19 Oct 2002