Olympiad Maths Prep

Track / Stage 10 / 4 of 40 #1964 of 2000

Problem 1964

Hardest shortlist tier
Combinatorics Difficulty 9.3 Prove it IMO2024 Shortlisted Problems · IMO

On a board with 20242024 rows and 20232023 columns, Turbo the snail tries to move from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then moves one step at a time to an adjacent cell sharing a common side. He wins if he reaches any cell in the last row. However, there are 20222022 predetermined, hidden monsters in 20222022 of the cells, one in each row except the first and last rows, such that no two monsters share the same column. If Turbo unfortunately 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.
Suppose Turbo is allowed to take nn attempts. Determine the minimum value of nn for which he has a strategy that guarantees reaching the last row, regardless of the locations of the monsters.
(Hong Kong)

Comment. One of the main difficulties of solving this question is in determining the correct expression for nn. Students may spend a long time attempting to prove bounds for the wrong value for nn before finding better strategies.
Students may incorrectly assume that Turbo is not allowed to backtrack to squares he has already visited within a single attempt. Fortunately, making this assumption does not change the answer to the problem, though it may make it slightly harder to find a winning strategy.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

First we demonstrate that there is no winning strategy if Turbo has 22 attempts.
Suppose that (2,i)(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)(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)(2, j), so we know jij \neq i. So it is possible that there is a monster on (3,j)(3, j), in which case Turbo also fails on his second attempt. Therefore Turbo cannot guarantee to reach the last row in 22 attempts.

Next, we exhibit a strategy for n=3n=3. On the first attempt, Turbo travels along the path
(1,1)(2,1)(2,2)(2,2023). (1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow \cdots \rightarrow (2,2023).
This path meets every cell in the second row, so Turbo will find the monster in row 22 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)(2, i) with 2i20222 \leqslant i \leqslant 2022), then Turbo takes the following two paths in his second and third attempts:
(1,i1)(2,i1)(3,i1)(3,i)(4,i)(2024,i).(1,i+1)(2,i+1)(3,i+1)(3,i)(4,i)(2024,i). \begin{aligned} & (1, i-1) \rightarrow (2, i-1) \rightarrow (3, i-1) \rightarrow (3, i) \rightarrow (4, i) \rightarrow \cdots \rightarrow (2024, i). \\ & (1, i+1) \rightarrow (2, i+1) \rightarrow (3, i+1) \rightarrow (3, i) \rightarrow (4, i) \rightarrow \cdots \rightarrow (2024, i). \end{aligned}
The only cells that may contain monsters in either of these paths are (3,i1)(3, i-1) and (3,i+1)(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
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)(2,1). Then, on the second attempt, Turbo takes the following path:
(1,2)(2,2)(2,3)(3,3)(2022,2023)(2023,2023)(2024,2023). (1,2) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (3,3) \rightarrow \cdots \rightarrow (2022,2023) \rightarrow (2023,2023) \rightarrow (2024,2023).

Figure 2
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)(i, j) be the first cell on which Turbo encounters a monster. We have that j=ij=i or j=i+1j=i+1. Then, on the third attempt, Turbo takes the following path:
(1,2)(2,2)(2,3)(3,3)(i2,i1)(i1,i1)(i,i1)(i,i2)(i,2)(i,1)(i+1,1)(2023,1)(2024,1). \begin{aligned} (1,2) & \rightarrow (2,2) \rightarrow (2,3) \rightarrow (3,3) \rightarrow \cdots \rightarrow (i-2, i-1) \rightarrow (i-1, i-1) \\ & \rightarrow (i, i-1) \rightarrow (i, i-2) \rightarrow \cdots \rightarrow (i, 2) \rightarrow (i, 1) \\ & \rightarrow (i+1,1) \rightarrow \cdots \rightarrow (2023,1) \rightarrow (2024,1). \end{aligned}
Now note that
- The cells from (1,2)(1,2) to (i1,i1)(i-1, i-1) do not contain monsters because they were reached earlier than (i,j)(i, j) on the previous attempt.
- The cells (i,k)(i, k) for 1ki11 \leqslant k \leqslant i-1 do not contain monsters because there is only one monster in row ii, and it lies in (i,i)(i, i) or (i,i+1)(i, i+1).
- The cells (k,1)(k, 1) for ik2024i \leqslant k \leqslant 2024 do not contain monsters because there is at most one monster in column 11, and it lies in (2,1)(2,1).
Therefore Turbo will win on the third attempt.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.