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 1 of 5: Two attempts are never enough
In plain words
Whichever cell Turbo first steps into on row 2 can simply contain a monster, and on the next attempt whichever new cell he first steps into on row 3 can again contain a monster, so no fixed strategy beats two failures.
Detailed analysis
On Turbo's first attempt, the moment he first steps into row , an adversary can have placed a monster there, ending the attempt. On the second attempt, Turbo must enter row at some column for the first time; the adversary can again have placed a monster there. This shows no strategy can guarantee success in fewer than attempts, so .