K Kimoov A.B.

The King walked around the chessboard, visiting each square exactly once and returning to the starting square on the last move. (The King moves according to the usual rules: in one move, he can move horizontally, vertically, or diagonally to any adjacent square.) When his path was drawn, connecting the centers of the squares he visited in sequence, a closed broken line without self-intersections was obtained. What is the smallest and the largest length that this line can have? (The side of a square is one unit.)
King made 64 moves. Since the length of each move is either one (a straight move) or \(\sqrt{2}\) (a diagonal move), the total length of the path is at least 64. A path of length 64 is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_7e3e695203bdf41f05f0g-06.jpg?height=710&width=734&top_left_y=1188&top_left_x=645)

Difficulty: 4

\(\left[\begin{array}{l}\text { Chess coloring } \\ \text { [ Interior and exterior. Jordan's lemma ] }\end{array}\right.\)

\(\text { | }\)

[ Chessboards and chess pieces Geometry of a grid Classes: \(9,10,11\) ]

\(\text { }\)

\(\qquad\)

\(\text { }\)

#### Abstract

We will show that the length of the king's path cannot be greater than \(28 + 36 \sqrt{2}\). Consider two adjacent exits \(A\) and \(B\) of the king to the edge of the board. If these boundary squares are not adjacent, then the segment of the king's path between them divides the board into two parts, each containing whole squares. But then the king cannot move from one part to the other, which contradicts the condition. Therefore, the squares \(A\) and \(B\) are adjacent and, consequently, of different colors. Since the color of the square does not change during diagonal moves, there must be a straight move between any two adjacent exits to the edge. Since there are 28 boundary squares, there are also 28 exits to the edge, and thus at least 28 straight moves. The following figure shows that exactly 28 "straight" moves can be used.

 (```

\(\qquad\)
Proof
```

<!

<in

\(\qquad\)
-

3

![](https://cdn.mathpix.com/cropped/2024_05_06_7e3e695203bdf41f05f0g-07.jpg?height=689&width=694&top_left_y=16&top_left_x=682)

## Answer

The minimum length is 64, the maximum is \(28 + 36 \sqrt{2}\).