Problem 7.5. A lame rook makes moves alternating between one and two squares, with the direction of the move being freely chosen (in any of the four directions). What is the maximum number of cells on a $6 \times 6$ board it can visit, if visiting the same cell twice is prohibited, but the starting cell and the first move can be chosen freely?
Answer: 34.

Solution. An example for 34 cells is shown in Fig. ??. The visited cells are numbered from 1 to 34.

| 5 | 2 | 4 | 3 | 13 | 10 |
| :---: | :---: | :---: | :---: | :---: | :---: |
| 6 | 1 | 7 | 8 | 14 | 9 |
| 28 | 31 |  | 34 | 12 | 11 |
| 27 | 32 |  | 33 | 15 | 16 |
| 29 | 30 | 20 | 19 | 21 | 18 |
| 26 | 25 | 23 | 24 | 22 | 17 |

Fig. 2: to the solution of problem $? ?$

We will show that it is impossible to visit 35 or more cells. For this, we divide the $6 \times 6$ square into nine $2 \times 2$ squares and color them in a checkerboard pattern (Fig. ??). This results in 20 black cells and 16 white cells. Each move of length 2 connects two cells of different colors, and the pairs of cells for different "long" moves do not overlap. Since there are 16 white cells, the number of long moves does not exceed 16. Due to the alternation, this guarantees that the total number of moves does not exceed 33, and thus the number of visited cells does not exceed 34.

## Kurchatov School Olympiad in Mathematics - 2019 Final Round.

## Criteria

One of the largest suitable criteria is used:

7 6. Any correct solution to the problem.

3 6. An example of traversing 34 cells is constructed.

3 6. It is proven that it is impossible to visit 35 cells.