Problem 5
Turbo the snail is in the top row of a grid with 2024 rows and 2023 columns and wants to get to the bottom row. However, there are 2022 hidden monsters, one in every row except the first and last, with no two monsters in the same column. 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 orthogonal neighbor. (He is allowed to return to a previously visited cell.) If Turbo 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 between attempts, 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 Turbo wins. Find the smallest integer such that Turbo has a strategy which guarantees being able to reach the bottom row in at most attempts, regardless of how the monsters are placed.
Step 2 of 5: First attempt reveals the row-2 monster
In plain words
Since row 2 has only one monster, walking all the way across it (accepting the eventual failure) is the cheapest way to learn exactly where that monster sits before committing to a real descent.
Detailed analysis
On the first attempt, Turbo walks along the entire second row until he reaches the monster located there; this attempt necessarily fails, but Turbo now knows the exact column of .