A Delightful Puzzle: From Russia with Love

Attention! This post contains spoilers for a past puzzle. If you want to give it a try before attempting this sequel, you can find it here.

*

*

*

*

*

In one of the past posts, we explored a very delightful and challenging mathematical puzzle involving a hungry little mouse and his cubic feast of cheese. We discovered that, through a clever coloring parity argument, the mouse’s dream of saving the central cheese chunk for his grand finale was, alas, just that—a dream. 

Perhaps he was so determined to end his journey there because the center cube was the only one made of Gruyère cheese out of a pile of Gouda chunks, and he wished to save the finest bite for last! As it happens, many two-dimensional puzzles can be solved easily by similar parity checks. Here’s one such challenge for you, coming directly from the USSR Olympiad Problem Book! For an extra challenge, try this puzzle before reading about the past cheesy one!

In chess, is it possible for the knight to go (by allowable moves) from the lower left-hand corner of the board to the upper right-hand corner and, in the process light exactly once on each square? If so, show how it can be done. If not, prove it impossible. (Consult a book on how to play chess if in doubt.) \(^{1}\)

Solution

To traverse the chessboard while stepping on each square exactly once, the knight must make \(63\) moves (one less than the total number of squares, of course). Now, at each move, the knight always moves from a square of one color to a square of another color. Notice what this means: after an even number of moves, the knight will find himself back on the same color as his starting square. After an odd number of moves, he must land on a square of the opposite color. Since \(63\) is odd, a knight's tour of this length would necessarily end on a square of the other color. However, on a chessboard, the two squares at opposite ends are the same color. Hence, the knight cannot arrive at the opposite end of the diagonal of the chessboard in \(63\) moves (i.e., such a path is impossible).

1. Adapted from Shklarsky, D. O., Chentzov, N. N., & Yaglom, I. M. (1962). The USSR Olympiad Problem Book (Problem 2).