I'm currently stuck on a problem from my computer theory class homework. The question asks me to prove, using induction, that any chessboard of size $n \times 3$, where $n$ is even and $\geq 10$, will have a closed knight's tour. I've worked on the problem for a couple hours but can't seem to find any insight into the solution. I can't even figure out the tour for what I think is the base case, $n = 10$. Any tips or hints as to how I might go about proving this?
The question itself comes with a hint, saying that there will be two base cases. At first I thought this meant that I would have to show a closed knight's tour for one value of $n < 10$, which might give me a helpful property during the induction step, but having checked the Wiki article on closed knight's tours I understand now that there is no value of $n < 10$ for which a closed knight's tour is possible. In that case, maybe one base case chessboard can be broken down into subchessboards in one way that reveals a closed knight's tour, that extends to some values of $n$, while another can be broken down in a different way that extends to some other values of $n$? I'm not really sure how to interpret the hint and since I can't even figure out a single closed knight's tour I'm effectively stumped.
Some definitions that come with the question:
In chess, a knight’s move consists of travelling two squares in one direction (horizontally or vertically, but not diagonally) and then one square at 90 degrees to these.
A closed knight’s tour is a sequence of knight moves that touch upon every square on the board exactly once and end on a square from which one is a knight’s move away from the beginning square.
I don't want the full solution to the problem, but would appreciate some help as to how I should go about approaching it, since I'm currently completely stuck.
Best Answer
Once you figure out the base cases $n=10$ and $n=12$ you should prove the induction step which is: if there is a closed knight's tour on the board of the size $n\times 3$ there is one on the board of the size $(n+4)\times 3$. This suffices to prove the claim for all even $n\geq 10$ since it holds for both of the base cases.
Hint: Assume you have a closed knight's tour on the board of the size $n\times 3$. In this tour there is a move from the square $(n-1,3)$ to the square $(n,1)$ (I'm using the convention that the leftmost upper corner square is called $(1,1)$ and the rightmost lower corner square is called $(n,3)$). Now remove this move from the tour and imagine there is a $4\times 3$ board added to the right of your original board.
The task is to visit all the squares of this new $4\times 3$ board starting from the square $(n-1,3)$ and ending to such a square that you can move to $(n,1)$. The first move is obvious: it is from $(n-1,3)$ to $(n+1,2)$. There are two possibilities where the last move must land so that you can move to $(n,3)$: they are $(n+1,3)$ and $(n+2,2)$. When you succeed at this task you have managed to replace the move $(n-1,3)\to(n,1)$ in the original tour with a string of moves which cover the added piece of board. The result is a closed knight's tour on the board of size $(n+4)\times 3$ and the induction step is completed.