Show that, in a chessboard it is possible to traverse to any given square from another given square using a knight.

Question

Show that, in a chessboard it is possible to traverse to any given square from another given square using a knight.

This was asked in a high school math competition.

Answer 1

I need to admit that I originally misread the question. I think the easiest way to prove the statement is to show that given any square and any adjacent square there exists a sequence of moves such that the knight moves from the first to the second.

My feeling is that is enough (via some symmetry arguments) that starting on $a1$ the square $a2$ can be reached. I admit that I haven't thought this in detail, but it should be sufficient. And this can be done via the route $a1-b3-c1-a2$.

Answer 2

There are no calculations necessary here, math is not all calculations. What you need to do is provide a proof (an irrefutable explanation) for why it's possible.

One possible proof (only works on an 8x8 board):

There is a knight's tour on the 8x8 board (a cycle of knight moves that reaches all squares):

[Insert knight's tour here]

To get from square A to square B, the knight can just start at A and follow the tour until he's at square B.

Another possible proof (using an intermediate step, but works on any board size 4x4 or greater and does not require knowing a knight's tour):

Claim: It is always possible for the knight to reach the top left square.

If the claim is true, then a square can go from square A to square B by navigating from square A to the top left square, then from that square to square B by moving backwards along the path from B to the top left square.

Proof that the claim is true:

The knight can always go up-up-left or up-up-right until he reaches the top two rows. Then, while staying within those top two rows, the knight can go left-left-up or left-left-down to reach the left two columns. Now the knight is in one of the four squares in the top left corner.

From those squares, it's easy to reach the top left square, using the paths shown in the following image: