Problem 5.
Turbo the snail plays a game on a board with 2024 rows and 2023 columns. There are hidden monsters in 2022 of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.

Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.

Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n$-th attempt or earlier, regardless of the locations of the monsters.
Proposed by Chu Cheuk Hei, HKG

 

Solution

Renumber the rows to start with $0$, so the first row with monsters is row $1$. Impose a coordinate system $(\text{row},\text{col})$ in the obvious way.

To see that at least $3$ attempts are required, suppose that Turbo first move out of the zeroth row is onto $(1,n)$. It could be the case that he encounters a monster there. In this case, if Turbo could win for $n=2$ then his next attempt must remain within either row $1$ or column $n$, since he could bump into another monster the instant he steps out. But since $(1,n)$ is occupied this is clearly impossible.

For a strategy for at least $3$ attempts, Turbo moves onto $(1,2)$ and then moves right until $(1,2022)$. If he encounters a monster on $(1,n)$, then his next attempts are $(0,n-1) \to (1,n-1) \to (2,n-1) \to (2,n) \to (2023,n)$ and $(0,n+1) \to (1,n+1) \to (2,n+1) \to (2,n) \to (2023,n)$, and one of these must work. Otherwise Turbo moves onto $(1,1)$ and then $(1,2023)$ if possible; one of these must have a monster on it; WLOG $(1,1)$ since both actually give the same amount of information.

Turbo's next move repeats the following procedure for $k=2,3,\ldots$: he moves onto $(k,k+1)$, then moves rightwards until $(k,2023)$. If Turbo doesn't encounter a monster during the process for $k$, then he gains the knowledge that there must be a monster on $(k,k)$ since there's nowhere else for it to go (by induction). If Turbo encounters a monster at some point, then he knows that there is no monster on $(k,k)$, but a monster on $(k-1,k-1)$. Then on his third and final attempt he can move to $(k,k) \to (k,k-1) \to (2023,k-1)$. If Turbo never encounters a monster then he eventually ends up on $(2022,2023)$, and can win by moving down.