The following solitaire game is played on an $m\times n$ rectangular board, $m,n\ge 2$, divided into unit squares. First, a rook is placed on some square. At each move, the rook can be moved an arbitrary number of squares horizontally or vertically, with the extra condition that each move has to be made in the $90^{\circ}$ clockwise direction compared to the previous one (e.g. after a move to the left, the next one has to be done upwards, the next one to the right etc). For which values of $m$ and $n$ is it possible that the rook visits every square of the board exactly once and returns to the first square? (The rook is considered to visit only those squares it stops on, and not the ones it steps over.)
Problem
Source: Baltic Way 2002
Tags: induction, combinatorics proposed, combinatorics
spanferkel
17.11.2010 22:36
Each time the rook visits a row or column, it marks two cells. So $m$ and $n$ must be even. By induction over $m$ it is easy to show that there is a solution for all even $m,n$. For $m=2$, take the following trip: $\begin{array}{cccccccccc} 2 &6& 10& ... &(2n-2)& (2n-1)& (2n-5)& ...&7& 3\\ 1& 5& 9& .... &(2n-3)&2n&(2n-4)& ... &8& 4\end{array}$ Suppose we have a closed trip on an $(m-2)\times n$ board. On an $m\times n$ board, start as below, the two lines visited being the first and the last line: $\begin{array}{cccccccccc} 4&8& ... &(2n-4)&\color{blue}{mn}&(2n-3)&(2n-7)&.... & 5&1\\ &&&& .\\\uparrow& \uparrow&&\uparrow& .& \downarrow& \downarrow&& \downarrow& \downarrow&&&&& .\\ 3&7& ...&(2n-5)&(2n-1) &(2n-2)&(2n-6)& ... &6&2\end{array}$ Between $2n-1$ and $mn$, we insert the $(m-2)\times n$ trip as follows: in this $n$th column, choose a vertical segment which belongs to the $(m-2)\times n$ trip. Note that by induction hypothesis, all vertical segments in this column go up. So we go from $2n-1$ up to the endpoint of this segment, then do the $(m-2)\times n$ trip and arrive at the bottom of this segment, from which we go up to the cell marked $\color{blue}{mn}$ and then right to $1$, and the trip is finished.