IMO 2024 Problem 5

Many people think that this problem was chose by mistake, as it is too easy, even as P1 or P4 for IMO. It turns out to have an interesting corner case that I did not recognized!

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.

================================

Solution:

For simplicity we ignore the first and last rows, and denote by $(r, c)$ the cell in the $r$-th row and $c$-th column where $1\le r\le 2022, 1\le c\le 2023$.

The answer is $n=3$. To show that we could not do better, note that in the first attempt it is always possible to hit the monster in the first row. Then, with this information it is still possible to hit the monster in the second row. Therefore we cannot do better than $n=3$.

The following strategy guarantees a successful third attempt. In the first attempt locate the monster in the first row. Two cases arise.

[Case 1] The monster in the first row is not in the leftmost nor rightmost cell.

In the second attempt locate the monster in the second row, which is either to the lower right or lower left of the monster in the first row. Thus in the third attempt, with these information we can always go to the cell right below the monster in the first row, which cannot contain a monster. Then we go down to the last row.

[Case 2] The monster in the first row is in the leftmost or rightmost cell.

Without loss of generality suppose it is in the rightmost cell $(1,2023)$. We go to the leftmost cell of the second row, then go right until hitting a monster or until we get to $(2,2021)$ safely. In the latter case, we know that $(2,2022)$ has a monster so we move back to the leftmost cell in the second row, go down to the third row, and again go right until hitting a monster or until we get to $(3,2020)$ safely. In the latter case we know that $(3,2021)$ has a monster, so again we move back to the left end and go down to the next row, and then go right until hitting a monster etc. In essence, for any $2\le r\le 2022$, in row $r$ we start from the left end to go right until hitting a monster or reaching $(r,2023-r)$. In the latter case we know that $(r,2024-r)$ has a monster, so we increase $r$ by $1$ if $r<2022$ or claim the second attempt successful if $r=2022$. Anytime we hit a monster at $(r,c)$ in this attempt, in the next attempt we can go from $(1,c+1)$ to $(r,c+1)$ to $(r,2023)$ to $(2022,2023)$.

$\square$