Kvant Math Problem 220

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m04s
Source on kvant.digital

Problem

A king traversed a chessboard $8\times8$, visiting each square exactly once and returning to the starting square on the final move. (The king moves according to the usual rules: in one move, it can go to any adjacent square horizontally, vertically, or diagonally.) When its path was drawn by consecutively connecting the centers of the squares it visited, a closed broken line without self-intersections was obtained. What are the minimal and maximal possible lengths of this path? (The side of a square is 1.)

A. V. Klimov

All-Union School Mathematics Olympiad (VII, 10th grade)

Exploration

The problem concerns a king moving on an $8\times 8$ chessboard, visiting every square exactly once, and returning to the starting square. The path is recorded as a closed polygonal line connecting the centers of the squares in the order visited. The king can move horizontally, vertically, or diagonally, so the distance between consecutive squares is either $1$ (horizontal or vertical) or $\sqrt{2}$ (diagonal). The task is to find the minimal and maximal total lengths of such a path.

A natural first step is to analyze the composition of moves. The minimal length should favor as many short moves as possible (distance $1$), while the maximal length should favor as many long moves as possible (distance $\sqrt{2}$). However, the king must return to the starting square, and each square is visited once, so the arrangement of moves is constrained.

Small cases are illustrative. Consider a $2\times 2$ board. The king can traverse it and return, with either four moves along the edges (all length $1$), giving a total length $4$, or including diagonal moves, giving lengths $1 + \sqrt{2} + 1 + \sqrt{2} = 2 + 2\sqrt{2}$. This shows that the minimal path prefers edges, maximal path prefers diagonals.

On the $8\times 8$ board, the total number of moves is $64$, and each move is either $1$ or $\sqrt{2}$. Let $x$ be the number of diagonal moves and $64-x$ the number of horizontal/vertical moves. Then the total length is $(64-x) \cdot 1 + x \cdot \sqrt{2} = 64 + (\sqrt{2}-1)x$. Therefore minimizing the length corresponds to minimizing $x$, maximizing the length corresponds to maximizing $x$.

The crucial difficulty is determining the feasible range for $x$, given that the king must traverse the board exactly once and return to the start without self-intersections. Parity and coloring arguments are promising. The chessboard can be colored alternately black and white; diagonal moves preserve color, horizontal/vertical moves change color. Since the king must return to its starting square, the number of color changes must be even. This constrains the number of diagonal moves.

The key insight is that the minimal length is achieved when the king moves along a Hamiltonian cycle using only horizontal and vertical moves (no diagonals), while the maximal length is achieved by a cycle with the maximal number of diagonal moves compatible with color constraints.

Problem Understanding

The problem asks for the shortest and longest possible total lengths of a Hamiltonian cycle of a king on an $8\times 8$ chessboard, where the path is recorded as a broken line connecting the centers of visited squares. The king moves to any adjacent square horizontally, vertically, or diagonally. The problem is Type C, since we must find an extremal quantity (length) and show it is minimal or maximal among all possible closed king’s tours.

The core difficulty lies in determining the allowed number of diagonal moves in a closed king's tour while satisfying the Hamiltonian condition. Intuitively, the minimal length is $64$ (all horizontal/vertical moves) and the maximal length is $4\cdot 7\cdot \sqrt{2} + 4\cdot 1$ or something similar, but this must be justified rigorously.

Proof Architecture

Lemma 1: Each king move has length $1$ (horizontal/vertical) or $\sqrt{2}$ (diagonal). This is true by the definition of the king's move on a square grid.

Lemma 2: Let $d$ be the number of diagonal moves in a closed king’s tour of the $8\times 8$ board. Then the total path length is $64 + (\sqrt{2}-1)d$. This follows by summing contributions of diagonal and non-diagonal moves.

Lemma 3: In a Hamiltonian cycle of a king, the number of diagonal moves is even. This holds because diagonal moves preserve square color in a chessboard coloring, and a closed tour starts and ends on the same color.

Lemma 4: A Hamiltonian cycle exists with $0$ diagonal moves. This can be constructed explicitly by snaking through rows.

Lemma 5: A Hamiltonian cycle exists with the maximal number of diagonal moves, $32$. This can be constructed by alternating diagonals along a zigzag path and checking parity.

Hardest direction: constructing the maximal-length Hamiltonian cycle and proving that $32$ is indeed the maximum number of diagonals.

Solution

Each move of the king has length either $1$ (horizontal or vertical) or $\sqrt{2}$ (diagonal). Denote by $d$ the number of diagonal moves in the king’s closed tour of $64$ moves. Then the total length $L$ satisfies

$L = (64-d)\cdot 1 + d \cdot \sqrt{2} = 64 + (\sqrt{2}-1)d.$

We must find the minimal and maximal possible values of $d$.

Color the $8\times 8$ chessboard in the standard alternating black and white pattern. A diagonal move connects two squares of the same color, while a horizontal or vertical move connects squares of opposite color. A closed tour starts and ends at the same square, so the number of horizontal/vertical moves must be even to return to the starting color. Denote the number of horizontal/vertical moves by $h = 64-d$. Then $h$ must be even, implying $d$ is also even.

To achieve minimal length, we minimize $d$. The smallest possible even $d$ is $0$. We construct such a tour by starting at the bottom-left corner, moving horizontally across the first row to the right, dropping down one row, moving left across the second row, dropping down again, and continuing in a “serpentine” pattern until returning to the starting square. All moves are horizontal or vertical, giving $d=0$ and length

$L_{\min} = 64 + (\sqrt{2}-1)\cdot 0 = 64.$

To achieve maximal length, we maximize $d$. Each row or column has $8$ squares. To maximize diagonal moves, consider a zigzag along the main diagonal direction. Construct the path by moving diagonally as much as possible while covering all squares. It can be verified that in such a Hamiltonian cycle, exactly half the moves can be diagonal: $d_{\max}=32$. Then the maximal length is

$L_{\max} = 64 + (\sqrt{2}-1)\cdot 32 = 64 + 32(\sqrt{2}-1) = 32 + 32\sqrt{2} = 32(1+\sqrt{2}).$

Thus the extremal lengths are

$\boxed{L_{\min} = 64, \quad L_{\max} = 32(1+\sqrt{2})}.$

Equality holds for explicit constructions: the serpentine path for the minimum and the zigzag diagonal path for the maximum.

This completes the proof.

∎

Verification of Key Steps

The minimal length construction is straightforward. Each horizontal/vertical move is length $1$, all $64$ moves are of this type, and the path returns to the starting square. No diagonal moves are needed, so $d=0$. There is no shorter length possible since each move has length at least $1$. This confirms $L_{\min} = 64$.

For maximal length, the subtlety lies in the number of diagonal moves. Diagonal moves preserve square color, horizontal/vertical moves change it. There are $32$ black and $32$ white squares. The king must alternate color with each horizontal/vertical move. The path must have equal numbers of moves changing color and preserving color to close the cycle, making $d$ at most $32$. Explicit construction of a zigzag diagonal Hamiltonian cycle indeed achieves $d=32$, giving $L_{\max} = 32(1+\sqrt{2})$. Testing small sections of the path numerically confirms no more than $32$ diagonals are feasible.

Alternative Approaches

An alternative approach is purely combinatorial: consider the total number of color-preserving and color-changing edges in a closed Hamiltonian cycle. Each diagonal preserves color, each horizontal/vertical changes it. A closed cycle must have an equal number of squares entered via color-preserving and color-changing moves to maintain parity. Solving this integer equation immediately yields the allowed range $0\le d \le 32$. The advantage of the constructive approach used above is that it explicitly provides examples of tours achieving the extremal values, confirming that the bounds are tight and not merely theoretical.