Knight defeated
The knight's move on a chess board is 2 steps in one direction and one step in the other direction. Prove that a knight cannot visit every square on the board once and only (a tour) on a 2 by n board for any value of n. How many ways can a knight do this on a 3 by 4 board?
Age
14 to 16
Challenge level
Problem
You do not need to be able to play chess to solve this problem.
The standard move for a knight on a chess board is $2$ steps in one direction and one step in the other direction. A knight's tour is a sequence of moves in which the knight visits every square on the board once and only once and a circuit is a tour in which the knight returns to the starting point.
Prove that a knight cannot make a tour on a $2$ by $n$ board for any value of $n$.
How many different tours can you find on a $3$ by $4$ rectangular board?
Image
Prove that a knight cannot make a circuit on a $3$ by $4$ rectangular board.
Getting Started
For the $2$ by $n$ board, if there is a tour then it must pass through the corner square. Is this possible?
It might help to think of the squares as vertices of a graph. Then there is an edge joining two vertices if and only if there is a knight's move between the corresponding squares.
Eight of the vertices are of degree two (only one path in and one out of that square). To construct a tour you are forced to visit these vertices in a particular order.
Student Solutions
Christina sent us her solution:
A knight can't make a tour on a $2\times n$ board, for any $n$, because it must go into and out of a corner square, and it can't do this without going back on itself.
On the $3\times 4$ grid, we must use a path from the loop JAGIBHJ and a path from the loop KDFLCEK. But they only link up between J and C, and between B and K. So the path must start at a neighbour of J, B, K or C, follow round that loop, switch to the other loop and follow round that. Obviously the path can go round the loop in either direction. So there are $16$ possible tours:
HJAGIBKDFLCE
HJAGIBKECLFD
HBIGAJCEKDFL
HBIGAJCLFDKE
AGIBHJCEKDFL
AGIBHJCLFDKE
IGAJHBKECLFD
IGAJHBKDFLCE
ECLFDKBIGAJH
ECLFDKBHJAGI
EKDFLCJHBIGA
EKDFLCJAGIBH
DFLCEKBIGAJH
DFLCEKBHJAGI
LFDKECJAGIBH
LFDKECJHBIGA
Since it's not possible to get from the finish directly back to the start in any of these tours, there is no circuit.