A pawn is placed on a square of a $ n \times n$ board. There are two types of legal moves: (a) the pawn can be moved to a neighbouring square, which shares a common side with the current square; or (b) the pawn can be moved to a neighbouring square, which shares a common vertex, but not a common side with the current square. Any two consecutive moves must be of different type. Find all integers $ n \ge 2$, for which it is possible to choose an initial square and a sequence of moves such that the pawn visits each square exactly once (it is not required that the pawn returns to the initial square).
Problem
Source: Final Round Grade 11 Pro 5
Tags: rotation, combinatorics unsolved, combinatorics
30.07.2008 23:50
For odd $ n = 2k + 1$, color the board black and white in a checkerboard fashion, and let the squares be named $ (i,j)$, where $ 1 \le i \le n$ denotes the row and $ 1 \le j \le n$ denotes the column. Then move (a) causes the pawn to move to a square of an alternate color, while move (b) causes the pawn to move to a square of the same color. Note that from any square of a color, either the move before or after (but not both) must be to another adjacent square of the same color. Suppose a sequence exists where the starting and ending points are not opposite corners; then we rotate the board such that the starting point and ending points are not on the first row. WLOG let the corners be all black. The only black square next to corner $ (1,1)$ is $ (2,2)$, and similarly to $ (1,2k + 1)$ is $ (2,2k)$. Then, in our sequence, we must have somewhere \begin{align*} \mathrm{white} - (1,1) & \leftrightarrow (2,2) - \mathrm{white} \\ \mathrm{white} - (1,2k + 1) & \leftrightarrow (2,2k) - \mathrm{white} \tag{*} \end{align*}Since we have already traversed through $ (2,2)$, then the only available black square adjacent to $ (1,3)$ is $ (2,4)$. Repeating this argument, the only black square adjacent to black square $ (1,2m + 1)$ is $ (2,2m + 2)$, and so the only black square adjcent to $ (1,2k - 1)$ is $ (2,2k)$, contradicting $ (*)$. If a sequence exists where the starting and ending points are opposite corners, WLOG let the starting point be $ (1,1)$, and use a similar contradiction based upon the black squares in the first row and first column. For $ \boxed{\mathrm{even}\ n}$, we can repeat the following sequence: [asy][asy]int row = 8, col = 2; for(int i = 0; i < row + 1; ++i) draw((2i,0)--(2i,2*col)); for(int j = 0; j < col + 1; ++j) draw((0,2j)--(2*row,2j)); for(int i = 1; i < row/2; ++i){ draw((4i+1,1)--(4i+3,3)); draw((4i+1,3)--(4i+3,1)); } for(int i = 1; i < row/2; ++i){ draw((4i-1,1)--(4i+1,1)); draw((4i-1,3)--(4i+1,3)); } dot((1,1)); draw((1,1)--(1,3)--(3,1)); draw((2*row-1,1)--(2*row-1,3));[/asy][/asy]