
C2. Fix an integer $n \geq 2$. A fairy chess piece leopard may move one cell up, or one cell to the right, or one cell diagonally down-left. A leopard is placed onto some cell of a $3 n \times 3 n$ chequer board. The leopard makes several moves, never visiting a cell twice, and comes back to the starting cell. Determine the largest possible number of moves the leopard could have made.

## Russia, Dmitry Khramtsov


Solution. The required maximum is $9 n^{2}-3$. We first show that the number of visited cells is divisible by 3 . To this end, refer to a coordinate frame whose axes point upward and rightward, respectively, so that the centres of the cells have integral coordinates in the range 1 through $3 n$. Assign each cell $(i, j)$ the residue of $i+j$ modulo 3 . Notice that equally many cells are assigned each residue, since this is the case for every $3 \times 1$ rectangle. Any move of the leopard is made from a cell assigned residue $r$ to one assigned residue $r+1$ modulo 3. Hence, the residues along any path of the leopard are $\cdots \rightarrow 0 \rightarrow 1 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow \cdots$. Consequently, every cyclic path contains equally many cells assigned each residue, so the total number of cells along the cycle is divisible by 3 .

Next, we show that the leopard cannot visit all cells. Argue indirectly. The leopard's cycle forms a closed non-self-intersecting polyline enclosing some region along whose boundary the leopard moves either clockwise or counter-clockwise. On the other hand, the cell $(3 n, 1)$ may be visited only as $(3 n-1,1) \rightarrow(3 n, 1) \rightarrow(3 n, 2)$, while the cell $(1,3 n)$ may be visited only as $(1,3 n-1) \rightarrow(1,3 n) \rightarrow(2,3 n)$ - see the left figure below. The region bounded by the leopard's cycle lies to the left of the path in the former case, but to the right of the path in the latter case. This is a contradiction.

The argument above shows that the number of visited cells does not exceed $9 n^{2}-3$. The figure in the middle below shows that this bound is indeed achieved.

![](https://cdn.mathpix.com/cropped/2024_06_04_1105870bb241d4c1b2cbg-11.jpg?height=485&width=1591&top_left_y=1395&top_left_x=234)

Remarks. (1) Variations of the argument in the second paragraph above may equally well work. For instance, consider the situation around the cell $(1,1)$. The cycle comes to that cell from $(2,2)$, and leaves it to, say, $(1,2)$. The previous part of the cycle should then look like $(i, 2) \rightarrow(i-1,1) \rightarrow(i-1,2) \rightarrow(i-2,1) \rightarrow \cdots \rightarrow(2,2) \rightarrow(1,1) \rightarrow(1,2)$, say with a maximal $i$. Then the cell $(i, 1)$ could only be visited as $(i+1,2) \rightarrow(i, 1) \rightarrow(i+1,1)$; again, the two parts have opposite orientations with respect to the interior region.

(2) The problem becomes more symmetric under an affine transformation mapping the square lattice to the honeycomb illustrated in the right figure above.
