Hamilton cycle on chessboard

Question

Suppose we have $8 \times 8$ chessboard such that two squares are adjacent iff they share a common side. In one move pawn can move to adjacent square. Prove that the pawn made a different number of vertical and horizontal moves if it crossed each field exactly once and returned to the starting field. Any help would be greatly appreciated.

Answer 1

The question posed is (almost) exactly Problem $6$ of the $1999$ Tournament of Cities.

Translated to English, the problem read

The rook, making moves vertically and horizontally to the adjacent square, went around all the squares of the $8 \times 8$ chessboard in $64$ moves and returned to the original square. Prove that the number of vertical moves is not equal to the number of horizontal moves.

The solution, translated to English, is as follows:

It suffices to prove that the number of horizontal moves of the rook when divided by $4$, gives a remainder of $2$ (from this it will immediately follow that the number of horizontal moves is not equal to $32$, and, consequently, the number of horizontal moves is not equal to the number of vertical moves). Let the trajectory of the centre of the rook bound the polygon $P$ (we assume that the centre of the rook is always placed in the centre of the cell). That part of the marking of the chessboard on the fields, which is entirely inside $P$, forms a certain graph $G$ (see the figure, in the figure, $P$ is highlighted in red, $G$ is blue), the vertices of this graph are the nodes of the chess marking. It is easy to see that $G$ is a tree. Let us introduce a coordinate system with the origin in the centre of the field a$1$ of the chessboard and axes parallel to the horizontals and verticals of the board (see figure). Then all the vertices of $P$ have integer coordinates and the sides are parallel to the axes.

Lemma: Let $P$ be a polygon with vertices at integer points, with sides parallel to the axes, such that the corresponding graph $G$ (obtained by joining the centres of adjacent cells of $P$) is a tree. Further, let $A$ be the number of integer points on the boundary of $P$ whose $x$-coordinate is even, $B$ the number of integer points on the boundary of $P$ whose $x$-coordinate is odd. Then the sum of the lengths of the horizontal sides $P$ is comparable to $A – B+2 \bmod{4}$.

Proof: Let us prove the lemma by induction on the area $P$. The base (the area $P$ is equal to $1$, $P$ consists of one cell) is trivial. The transition is carried out by cutting off from $P$ a cell corresponding to a leaf of the tree G. A cell can adjoin $P$ along a horizontal segment, or along a vertical segment. In the first case, the sum of the lengths of the horizontal sides $P$ does not change, while $A-B$ does not change either. In the second case, both the sum of the lengths and $A–B$ change by $2$. For the polygon $P$ bounded by the trajectory of the rook's centre, $A=32$, $B=32$, therefore, the number of horizontal moves of the rook is comparable to $A–B+2 \equiv 2 \bmod{4}$.

You may find the problem and solution in Russian here and here.

For a more intuitive solution, see this masterpiece on puzzling.SE.

Additional Links:

• Hobbled rook tour – Hamiltonian cycle on square grid
• The Erasmus rook tour