Exercise 7. Let $n \geqslant 2$ be an integer. Clara has a $3 n \times 3 n$ board, similar to a chessboard. She has just invented a new piece, the leopard, which she can move as follows: one square up, one square to the right, or one square diagonally, down and to the left. Clara placed her leopard on one of the squares of the board, then moved it so that it never passes through the same square twice, until it returns to its starting square.

What is the maximum number of moves Clara could have made in this way?
Solution to Exercise 7 First, Clara can perform $9 \mathrm{n}^{2}-3$ as illustrated below in the case where $n=3$.

![](https://cdn.mathpix.com/cropped/2024_06_04_da0d7660f6bfece41d9bg-8.jpg?height=640&width=646&top_left_y=731&top_left_x=705)

Now let's show that she cannot do better. First, we identify each cell in row $i$ (from the bottom) and column $j$ (from the left) with the pair $(i, j)$, where $1 \leqslant i, j \leqslant 3 n$. Then we color the cells of the board with three colors $C_{0}, C_{1}$, and $C_{2}$, assigning the color $C_{i+j}(\bmod 3)$ to the cell $(i, j)$. Each move of the leopard consists of moving by a vector $(0,1), (1,0)$, or $(-1,-1)$. Consequently, it always moves from a cell of color $C_{k}$ to a cell of color $C_{k+1(\bmod 3)}$. Therefore, it has made a number of moves divisible by 3, and it suffices to show that it has not passed through all the cells.

To this end, note that its path describes a planar graph consisting of a single cycle, which therefore contains an internal face (finite) and an external face. If the leopard has passed through the cell $(1,3 n)$, it must have used the edge $(1,3 n) \rightarrow (2,3 n)$, thus circling its internal face clockwise. But similarly, if it has passed through the cell $(3 n, 1)$, it must have used the edge $(3 n, 1) \rightarrow (3 n, 2)$, thus circling its internal face counterclockwise. Therefore, it could not have passed through both of these cells during the same path, which concludes the proof.