IMO 2024 · 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^{\text{th}}\) attempt or earlier, regardless of the locations of the monsters.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{n=3}. \]

Solution

Put \(m=2023\). Number the rows \(1,\ldots,m+1\) from top to bottom and the columns \(1,\ldots,m\) from left to right. Denote a cell by \((r,c)\).

Two attempts cannot suffice. Consider any proposed strategy. On its first attempt, let \((2,c)\) be the first cell Turbo enters in row \(2\). Place the monster of row \(2\) there, ending this attempt.

On the second attempt, Turbo must eventually enter row \(3\) to succeed. If he hits the known monster again, or never enters row \(3\), the proposed guarantee already fails. Otherwise, let \((3,d)\) be his first cell in row \(3\). He must enter it from \((2,d)\), so \(d\ne c\). Place the monster of row \(3\) at \((3,d)\), ending his second attempt.

Complete the placement by putting the monsters of rows \(4,\ldots,m\) in distinct columns other than \(c,d\). This is possible because there are \(m-3\) such rows and \(m-2\) available columns. These choices describe a single fixed legal placement: before either prescribed collision, Turbo has visited only cells whose contents have already been specified, so completing the placement does not change his actions. Thus no strategy guarantees success within two attempts.

Three attempts suffice. On his first attempt, Turbo starts at \((1,1)\), moves to \((2,1)\), and walks right along row \(2\) until he encounters its monster, say at \((2,c)\). He now knows that all other cells of row \(2\), and all other cells of column \(c\), are safe.

First suppose \(1<c<m\). On his second attempt, Turbo follows \[ (1,c-1),\quad (2,c-1),\quad (3,c-1). \] The only possible collision is at \((3,c-1)\). If that cell is safe, he moves right to \((3,c)\) and then straight down column \(c\) to the last row.

If instead \((3,c-1)\) contains a monster, then on his third attempt he follows \[ (1,c+1),\quad (2,c+1),\quad (3,c+1),\quad (3,c), \] and then goes straight down column \(c\). This route is safe: the monster in row \(2\) is at column \(c\), the monster in row \(3\) is at column \(c-1\), and column \(c\) has no further monster.

It remains to handle \(c=1\) or \(c=m\). By reflecting the board horizontally if necessary, we may assume \(c=1\).

On his second attempt, Turbo starts in column \(m\) and descends to row \(2\), which is safe there. He then processes rows \[ r=3,4,\ldots,m \] in order. In row \(r\), he enters at column \(m\), walks left through columns \[ m,m-1,\ldots,r, \] and, if he survives, returns to column \(m\) before proceeding to the next row.

We claim that whenever he reaches the scan of row \(r\), he knows that the monsters in all preceding monster rows are at \[ (2,1),(3,2),\ldots,(r-1,r-2). \] For \(r=3\), this is precisely what the first attempt established. Suppose it holds for some \(r\). Columns \(1,\ldots,r-2\) already contain monsters, so the monster in row \(r\) must be in one of columns \(r-1,\ldots,m\). If the scan through columns \(r,\ldots,m\) is safe, the monster must therefore be at \((r,r-1)\). This proves the claim inductively.

If all these scans are safe, Turbo reaches \((m,m)\) and steps down to \((m+1,m)\), succeeding on his second attempt.

Otherwise, suppose the second attempt ends at a monster \((r,d)\). By the scanning rule, \(d\ge r\), and all earlier monsters are at the positions in the displayed list. On his third attempt, Turbo follows the horizontal and vertical segments \[ (1,m) \longrightarrow (r-1,m) \longrightarrow (r-1,d-1) \longrightarrow (r,d-1) \longrightarrow (r,1) \longrightarrow (m+1,1), \] moving one cell at a time along each segment. Every segment is safe:

  • In rows \(2,\ldots,r-1\), the monsters lie in columns \(1,\ldots,r-2\), so the initial descent in column \(m\) is safe.
  • The monster in row \(r-1\) is at column \(r-2\). Since \(d-1\ge r-1\), the horizontal segment in that row avoids it.
  • The monster in row \(r\) is at column \(d\). Entering that row at column \(d-1\) and walking left to column \(1\) avoids it.
  • Column \(1\) contains its only monster in row \(2\), so the final descent from row \(r\ge3\) is safe.

Thus Turbo always succeeds by his third attempt. Together with the lower bound, this proves that the minimum is \(3\).

The solution was checked against the official IMO shortlist solutions.