Maths Olympiad Prep

Library / /25 of 25

Combinatorics Difficulty 8.3 Shortlist Prove it European Girls' Mathematical Olympiad (EGMO)

Problem:

Let n>1n > 1 be an integer. In a configuration of an n×nn \times n board, each of the n2n^{2} 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 9090^{\circ} 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 nn, the maximum number of good cells over all possible starting configurations.

Solution

Solution:

We will show that the maximum number of good cells over all possible starting configurations is
n24if n is even and \frac{n^{2}}{4} \quad \text{if } n \text{ is even and}
0if n is odd. 0 \quad \text{if } n \text{ is odd.}

## Odd nn

First, we will prove that there are no good cells if nn is an odd number.
For Turbo to reach her goal, she must return to her initial cell after visiting every cell exactly once. Consider the chessboard coloring of the board. Without loss of generality, we assume that Turbo starts in a black cell. Since, at every step, Turbo moves to a cell of a different color; she will be in a white cell after n21mod2n^{2} \equiv 1 \mod 2 moves. Thus, it is impossible for Turbo to come back to her initial black cell on her n2n^{2}-th move, which is a contradiction. Thus there are no good cells.

## Lower bound for even nn

We will now construct a starting configuration with n24\frac{n^{2}}{4} good cells for even nn.
Let (i,j)(i,j) denote the cell in row ii and column jj. Consider the following cycle
(1,1)(1,2)(1,3)(1,n)(2,n)(2,n1)(2,2)(2i1,2)(2i1,3)(2i1,n)(2i,n)(2i,n1)(2i,2)(n,n)(n,n1)(n,2)(n,1)(n1,1)(2,1)(1,1).(1,1) \begin{array}{r l} & (1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow \ldots \rightarrow (1,n)\\ & \qquad \rightarrow (2,n)\rightarrow (2,n - 1)\rightarrow \ldots \rightarrow (2,2)\\ & \qquad \ldots\\ & \qquad \rightarrow (2i - 1,2)\rightarrow (2i - 1,3)\rightarrow \ldots \rightarrow (2i - 1,n)\\ & \qquad \rightarrow (2i,n)\rightarrow (2i,n - 1)\rightarrow \ldots \rightarrow (2i,2)\\ & \qquad \ldots\\ & \qquad \rightarrow (n,n)\rightarrow (n,n - 1)\rightarrow \ldots \rightarrow (n,2)\\ & \qquad \rightarrow (n,1)\rightarrow (n - 1,1)\rightarrow \ldots \rightarrow (2,1)\rightarrow (1,1). \end{array} \quad (1,1)

Figure 1

Note that the cycle returns to the initial cell after visiting every cell exactly once. To prove that (1,1)(1,1) is good, we need to find a starting configuration such that Turbo traverses this cycle.
Let cic_{i} be the (i1)(i - 1)-th cell on the cycle: so we have c0=(1,1)c_{0} = (1,1), c2=(1,2)c_{2} = (1,2), ..., cn21=(2,1)c_{n^{2} - 1} = (2,1). For every ii, we draw an arrow in cell cic_{i} pointing towards cell ci+1c_{i + 1} (or pointing towards c0c_{0} if i=n21i = n^{2} - 1) and then rotate this arrow ii times 9090^{\circ} in the clockwise direction. After ii moves, the arrow in cic_{i} will have rotated ii times 9090^{\circ} counterclockwise and be in the same direction as on the path defined above. Thus, Turbo will traverse the cycle c0,c1,c2,,cn21,c0c_{0}, c_{1}, c_{2}, \ldots , c_{n^{2} - 1}, c_{0} and (1,1)(1,1) is good.
Every four moves, all arrows point in the same direction as in the beginning. Moreover, the board will return to its initial configuration after traversing the full cycle, since n2n^{2}, the length of the cycle, is divisible by 4. Therefore Turbo can also start at any cic_{i} with 4i4 \mid i and follow the same route. Hence the cells c0,c4,c8,,cn24c_{0}, c_{4}, c_{8}, \ldots , c_{n^{2} - 4} are good and there are n24\frac{n^{2}}{4} of such cells.

## Upper bound for even nn

We will prove that for even nn and any start configuration there are at most n24\frac{n^{2}}{4} good cells.
Let a0a_{0} be a good cell. Let a0,a1,a2,,an21,an2=a0a_{0},a_{1},a_{2},\ldots ,a_{n^{2} - 1},a_{n^{2}} = a_{0} be the sequence of cells that Turbo visits when she starts at a0a_{0}. Now suppose there is another good cell b0b_{0} and let b0,b1,b2,,bn21,bn2=b0b_{0},b_{1},b_{2},\ldots ,b_{n^{2} - 1},b_{n^{2}} = b_{0} be the sequence of cells that Turbo visits when she starts at b0b_{0}.
Note that, since 4n24\mid n^{2}, the arrows are back to their initial configuration after n2n^{2} steps. Thus, if Turbo keeps walking after returning to her initial cell, she would just traverse the same cycle over and over again.
Consider the upper left corner of the board. With standard row and column numbering, the corner cell is (1,1)(1,1). This cell has only two neighbours, so both the aa-route and the bb-route must have cells (2,1),(1,1),(1,2)(2,1),(1,1),(1,2) in that order or (1,2),(1,1),(2,1)(1,2),(1,1),(2,1) in that order. Without loss of generality, ai1=(2,1)a_{i - 1} = (2,1), ai=(1,1)a_{i} = (1,1) and ai+1=(1,2)a_{i + 1} = (1,2) for some ii. Let jj be such that bj=(1,1)b_{j} = (1,1). If bj1=(2,1)=ai1b_{j - 1} = (2,1) = a_{i - 1} then the arrow in cell (2,1)(2,1) must be pointed in the same direction after i1i - 1 steps and after j1j - 1 steps, so ij(mod4)i\equiv j \pmod{4}. But then the arrow in cell bj=(1,1)=aib_{j} = (1,1) = a_{i} must also be pointed in the same direction after ii and after jj steps, so Turbo moves to bj+1=ai+1b_{j + 1} = a_{i + 1} in both cases, and again finds the arrow pointed in the same direction in both cases. Continuing, we find that the bb-route is actually identical to a4t,a4t+1,,an2=a0,a1,,a4t1,a4ta_{4t},a_{4t + 1},\ldots ,a_{n^{2}} = a_{0},a_{1},\ldots ,a_{4t - 1},a_{4t} for some tt, as any other starting point would have the arrows in the wrong direction initially.

Now suppose instead that bj+1=(2,1)=ai1b_{j + 1} = (2,1) = a_{i - 1}. Considering the aa-route, the arrows in the upper left corner after i1i - 1 steps must be like this:

Figure 2

Considering the bb-route instead, the arrows after j1j - 1 steps must be like this:

Figure 3

From the arrows in cell (1,1)(1,1) we see that ij+1(mod4)i\equiv j + 1 \pmod{4}. However, for the cells (2,1)(2,1) and (1,2)(1,2) this gives a contradiction.
We conclude that the only possible good cells are a4ta_{4t} for t=0,1,,n241t = 0,1,\ldots ,\frac{n^{2}}{4} - 1, which gives at most n24\frac{n^{2}}{4} good cells.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.