IMO 2024 Shortlist C4
On a board with 2024 rows and 2023 columns, Turbo the snail tries to move from the first row to the last row. On each at...
Category: Combinatorics
Problem
On a board with 2024 rows and 2023 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 2022 predetermined, hidden monsters in 2022 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 n attempts. Determine the minimum value of n for which he has a strategy that guarantees reaching the last row, regardless of the locations of the monsters. (Hong Kong)