Putnam 2005, Problem A-2

Let $\mathbf{S} = \{(a,b) \mid a = 1,2,\ldots,n, b = 1,2,3\}$. A rook tour of $\mathbf{S}$ is a polygonal path made up of line segments connecting points $p_1, p_2, \ldots, p_{3n}$ in sequence such that  
(i) $p_i \in \mathbf{S}$,  
(ii) $p_i$ and $p_{i+1}$ are a unit distance apart, for $1 \leq i < 3n$,  
(iii) for each $p \in \mathbf{S}$ there is a unique $i$ such that $p_i = p$.  
How many rook tours are there that begin at $(1,1)$ and end at $(n,1)$?  
(An example of such a rook tour for $n=5$ was depicted in the original.)

Solution:
We will assume \(n \geq 2\) hereafter, since the answer is 0 for \(n = 1\).

First solution: We show that the set of rook tours from \((1,1)\) to \((n,1)\) is in bijection with the set of subsets of \(\{1,2,\ldots,n\}\) that include \(n\) and contain an even number of elements in total. Since the latter set evidently contains \(2^{n-2}\) elements, so does the former.

We now construct the bijection. Given a rook tour \(P\) from \((1,1)\) to \((n,1)\), let \(S = S(P)\) denote the set of all \(i \in \{1,2,\ldots,n\}\) for which there is either a directed edge from \((i,1)\) to \((i,2)\) or from \((i,3)\) to \((i,2)\). It is clear that this set \(S\) includes \(n\) and must contain an even number of elements. Conversely, given a subset \(S = \{a_1,a_2,\ldots,a_{2r} = n\} \subset \{1,2,\ldots,n\}\) of this type with \(a_1 < a_2 < \cdots < a_{2r}\), we notice that there is a unique path \(P\) containing \((a_i,2 + (-1)^i),(a_i,2)\) for \(i = 1,2,\ldots,2r\). This establishes the desired bijection.

Second solution: Let \(A_n\) denote the set of rook tours beginning at \((1,1)\) and ending at \((n,1)\), and let \(B_n\) denote the set of rook tours beginning at \((1,1)\) and ending at \((n,3)\).

For \(n \geq 2\), we construct a bijection between \(A_n\) and \(A_{n-1} \cup B_{n-1}\). Any path \(P\) in \(A_n\) contains either the line segment \(P_1\) between \((n-1,1)\) and \((n,1)\), or the line segment \(P_2\) between \((n,2)\) and \((n,1)\). In the former case, \(P\) must also contain the subpath \(P_1'\) which joins \((n-1,3)\), \((n,3)\), \((n,2)\), and \((n-1,2)\) consecutively; then deleting \(P_1\) and \(P_1'\) from \(P\) and adding the line segment joining \((n-1,3)\) to \((n-1,2)\) results in a path in \(A_{n-1}\). (This construction is reversible, lengthening any path in \(A_{n-1}\) to a path in \(A_n\).) In the latter case, \(P\) contains the subpath \(P_2'\) which joins \((n-1,3)\), \((n,3)\), \((n,2)\), \((n,1)\) consecutively; deleting \(P_2'\) results in a path in \(B_{n-1}\), and this construction is also reversible. The desired bijection follows.

Similarly, there is a bijection between \(B_n\) and \(A_{n-1} \cup B_{n-1}\) for \(n \geq 2\). It follows by induction that for \(n \geq 2\),
\[
|A_n| = |B_n| = 2^{n-2}(|A_1| + |B_1|).
\]
But \(|A_1| = 0\) and \(|B_1| = 1\), and hence the desired answer is \(|A_n| = 2^{n-2}\).

Remarks: Other bijective arguments are possible: for instance, Noam Elkies points out that each element of \(A_n \cup B_n\) contains a different one of the possible sets of segments of the form \((i,2),(i+1,2)\) for \(i = 1,\ldots,n-1\). Richard Stanley provides the reference: K.L. Collins and L.B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29–38. This problem is Theorem 1 of that paper; the cases of \(4 \times n\) and \(5 \times n\) grids are also treated. The paper can also be found online at the URL kcollins.web.wesleyan.edu/vita.htm.