IMO2024 Shortlisted Problems

First we demonstrate that there is no winning strategy if Turbo has $2$ attempts. Suppose that $(2,i)$ is the first cell in the second row that Turbo reaches on his first attempt. There can be a monster in this cell, in which case Turbo must return to the first row immediately, and he cannot have reached any other cells past the first row.

Next, suppose that $(3,j)$ is the first cell in the third row that Turbo reaches on his second attempt. Turbo must have moved to this cell from $(2,j)$, so we know $j\ne i$. So it is possible that there is a monster on $(3,j)$, in which case Turbo also fails on his second attempt. Therefore Turbo cannot guarantee to reach the last row in $2$ attempts.

Next, we exhibit a strategy for $n=3$. On the first attempt, Turbo travels along the path $$(1,1)\to (2,1)\to (2,2)\to \cdots \to (2,2023).$$ This path meets every cell in the second row, so Turbo will find the monster in row $2$ and his attempt will end.

If the monster in the second row is not on the edge of the board (that is, it is in cell $(2,i)$ with $2⩽i⩽2022$), then Turbo takes the following two paths in his second and third attempts: $$\begin{array}{rl}& (1,i-1)\to (2,i-1)\to (3,i-1)\to (3,i)\to (4,i)\to \cdots \to (2024,i).\\ & (1,i+1)\to (2,i+1)\to (3,i+1)\to (3,i)\to (4,i)\to \cdots \to (2024,i).\end{array}$$ The only cells that may contain monsters in either of these paths are $(3,i-1)$ and $(3,i+1)$. At most one of these can contain a monster, so at least one of the two paths will be successful.

Figure 1: Turbo's first attempt, and his second and third attempts in the case where the monster on the second row is not on the edge. The cross indicates the location of a monster, and the shaded cells are cells guaranteed to not contain a monster.

If the monster in the second row is on the edge of the board, without loss of generality we may assume it is in $(2,1)$. Then, on the second attempt, Turbo takes the following path: $$(1,2)\to (2,2)\to (2,3)\to (3,3)\to \cdots \to (2022,2023)\to (2023,2023)\to (2024,2023).$$

Figure 2: Turbo's second and third attempts in the case where the monster on the second row is on the edge. The light gray cells on the right diagram indicate cells that were visited on the previous attempt. Note that not all safe cells have been shaded.

If there are no monsters on this path, then Turbo wins. Otherwise, let $(i,j)$ be the first cell on which Turbo encounters a monster. We have that $j=i$ or $j=i+1$. Then, on the third attempt, Turbo takes the following path: $$\begin{array}{rl}(1,2)& \to (2,2)\to (2,3)\to (3,3)\to \cdots \to (i-2,i-1)\to (i-1,i-1)\\ & \to (i,i-1)\to (i,i-2)\to \cdots \to (i,2)\to (i,1)\\ & \to (i+1,1)\to \cdots \to (2023,1)\to (2024,1).\end{array}$$ Now note that - The cells from $(1,2)$ to $(i-1,i-1)$ do not contain monsters because they were reached earlier than $(i,j)$ on the previous attempt. - The cells $(i,k)$ for $1⩽k⩽i-1$ do not contain monsters because there is only one monster in row $i$, and it lies in $(i,i)$ or $(i,i+1)$. - The cells $(k,1)$ for $i⩽k⩽2024$ do not contain monsters because there is at most one monster in column $1$, and it lies in $(2,1)$. Therefore Turbo will win on the third attempt.