14th European Girls' Mathematical Olympiad (EGMO 2025)

Problem 5 Let n > 1 be an integer. In a configuration of an n × n board, each of the n² cells contains an arrow, either pointing up, down, left, or right. Given a starting configuration, Turbo the snail starts in one of the cells of the board and travels from cell to cell. In each move, Turbo moves one square unit in the direction indicated by the arrow in her cell (possibly leaving the board). After each move, the arrows in all of the cells rotate 90^◦ counterclockwise. We call a cell good if, starting from that cell, Turbo visits each cell of the board exactly once, without leaving the board, and returns to her initial cell at the end. Determine, in terms of n, the maximum number of good cells over all possible starting configurations.

SOLUTION

If $n$ is odd, then color the board in chessboard manner, then there are more black square than white square, vice versa. That is no cycle exists.
Hence, consider even positive integer $n$ .
We claim that the answer is $\frac{n^2}{4}$ .
The construction is to construct a board with arrows forming cycles, then pick a square to start and then reverse the rotation to satisfy the condition.
Since, in every $4$ moves, the arrows return to its initial orientation, there are $\frac{n^2}{4}$ squares to start with. That is $\frac{n^2}{4}$ good cells.

Now, we are left to show that no board with more than $\frac{n^2}{4}$ good cells exists.
Suppose there exist some board with more good cells than $\frac{n^2}{4}$ . Since, each cycle can gives us at most $\frac{n^2}{4}$ good cells, there exist another cycles in such squares. Call these $2$ cycle, $C_1$ and $C_2$ . Suppose the good cells from cycles $C_1$ and $C_2$ are in squares of the same colors. Note that if at least one arrows when it is in the same orientation in both cycles, then the rest of the arrows in both cycles are same. For any arrow $A$ , let $f(A)$ denote the number of moves done when the arrow $A$ is used in modulo $4$ . Also, for any arrow $A$ in cycle $C_1$ in square $S$ at some moment, denote $-A$ as an arrow in $C_2$ in square $S$ in the exact same moment.
Hence, note that $f(A) \neq f(-A)$ and since both cycle have good cells of the same colors, we have $2 \mid f(A) - f(-A)$ Hence, $| f(A) - f(-A)| = 2$ That is $-A$ is the reflection of $A$ . So, we run into contradiction, since the squares in the corner will point out of the grids.
Hence, good cells in $C_1$ and $C_2$ are different colors. This mean $2 \nmid f(A) - f(-A)$ .
In this case, there are no edge $E$ such that Turbo travel through $E$ in both cycles $C_1$ and $C_2$ (By parity arguments of arrows). Hence, contradiction since, the corner square have only $2$ edges, which is inevitably used as edges to get in and get out of the squares. Hence, we are done. $\blacksquare$