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 5 of 5: Conclusion
In plain words
Every case above resolves within three attempts, matching the lower bound already shown, so three is both necessary and sufficient.
Detailed analysis
In every case (Steps 3 and 4), Turbo reaches the bottom row within attempts, matching the lower bound of Step 1. Hence the smallest such is .