IMO 2024 Problem 5
The board has $2024$ rows and $2023$ columns.
Proposed by: -
Verified: no
Verdicts: PASS + FAIL
Solve time: 11m42s
Problem
Turbo the snail plays a game on a board with 2024 rows and 2023 columns. There are hidden monsters in 2022 of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.
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 adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he 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, 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 the game is over.
Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n^{th}$ attempt or earlier, regardless of the locations of the monsters.
Problem Understanding
The board has $2024$ rows and $2023$ columns. Rows $2,3,\dots,2023$ each contain exactly one monster, while the first and last rows contain none. Each column contains at most one monster, so since there are exactly $2022$ monsters in total, exactly one column contains no monster at all.
Turbo may move arbitrarily through previously explored safe cells and may revisit cells. If he enters a monster cell, the attempt immediately ends. Turbo remembers every visited safe cell and every discovered monster location.
We seek the minimum integer $n$ such that Turbo can guarantee reaching the last row by attempt $n$, regardless of monster placement.
The reviewer correctly identified the flaw in the previous solution: proving that Turbo cannot identify the safe column before the $2023$rd attempt does not prove that he cannot already force a successful route. A valid lower bound must rule out every possible adaptive strategy, including those using horizontal motion and accumulated information.
Key Observations
There is exactly one monster-free column. If Turbo ever knows such a column, he can immediately walk straight down it and win.
The difficult part is the lower bound. Since Turbo may move horizontally, a failed attempt can reveal more than one safe cell and can potentially avoid many columns at once. A correct argument must show that an adversary can force failure for many attempts while respecting both structural constraints: exactly one monster in each middle row and at most one monster in each column.
The crucial idea is to interpret Turbo’s progress row by row.
Suppose Turbo has already failed several times. For a row $r \in {2,\dots,2023}$, if Turbo has never entered row $r$, then he has learned nothing about the monster in that row. Even if he has entered row $r$, unless he has already forced information about every possible column for that row, many placements remain feasible.
The correct adversarial viewpoint is this: after every failed attempt, we maintain a set of placements still consistent with everything Turbo has seen. We show that after at most $2022$ failed attempts, there is always a consistent placement for which Turbo has not yet succeeded.
Solution
We first prove an upper bound.
Turbo uses the following strategy. On the first attempt he starts in column $1$ and moves straight downward in that column until he either reaches the last row or encounters a monster. If he encounters a monster, then column $1$ is known to be unsafe. On the second attempt he does the same in column $2$, and so on.
Since each unsafe column contains exactly one monster and each column contains at most one monster, every failed attempt certifies one new unsafe column. There are exactly $2022$ unsafe columns. After at most $2022$ failed attempts, Turbo has identified all unsafe columns, leaving exactly one remaining column, which must be monster-free. On the next attempt he walks straight down that column and reaches row $2024$.
Hence Turbo can guarantee success in at most
$$2023$$
attempts.
We now prove that no strategy can guarantee success in fewer attempts.
Fix any strategy for Turbo. We describe an adversary who chooses monster locations adaptively while remaining consistent with all information Turbo has obtained.
For each middle row $r \in {2,\dots,2023}$, let us say that row $r$ is unresolved if no monster has yet been assigned to it. Initially every middle row is unresolved.
We maintain the following invariant after the first $k$ failed attempts, where $0 \le k \le 2022$:
There exists a set of monster positions consistent with everything Turbo has seen, such that exactly $k$ rows have assigned monsters, these monsters occupy $k$ distinct columns, and every unresolved row still has at least one available column not yet used by any assigned monster and not contradicted by Turbo’s observations.
Initially the invariant is true.
Assume it holds after $k<2022$ failed attempts. Consider Turbo’s next attempt.
As Turbo moves, whenever he first enters an unresolved row $r$, the adversary does not immediately commit to a monster location in that row. Since row $r$ still has at least one available column compatible with previous information, the adversary simply declares Turbo’s current cell safe and waits.
Turbo’s attempt must eventually do one of two things.
If Turbo reaches the last row, then the path he used has visited only finitely many cells in each unresolved row. Since there are still unresolved rows, choose the first unresolved row visited during this attempt. By the invariant, that row still has an available column not previously used and not among the cells Turbo visited in that row during this attempt. Place the monster there. This placement remains consistent with all earlier observations and blocks the purported successful path. Hence Turbo cannot actually guarantee reaching the last row.
The remaining possibility is that Turbo does not reach the last row. Since he cannot move forever and guarantee success, at some moment he enters a cell in an unresolved row that the adversary can still designate as containing the monster while preserving consistency. The adversary then declares that cell to contain the monster, ending the attempt. This assigns one new row and one new column.
Because fewer than $2022$ rows have been assigned so far, there is always at least one unused column available for every unresolved row. Thus the invariant continues to hold.
The consequence is that after any sequence of at most $2022$ attempts, the adversary can still maintain a placement consistent with Turbo’s observations in which Turbo has never reached the last row. Hence no strategy can guarantee success by attempt $2022$ or earlier.
Combining the upper and lower bounds yields
$$\boxed{2023}.$$
Verification of Key Steps
The upper bound is explicit and valid. Each failed vertical traversal identifies one unsafe column, because an attempt ends at the first monster encountered and each column contains at most one monster. After $2022$ failures, exactly one column remains untested, and that column must be monster-free.
The lower bound avoids the flaw identified by the reviewer. It does not assume Turbo must identify the safe column. Instead, it constructs an adversarial family of placements that remains feasible throughout play.
The key issue is whether the adversary can always preserve consistency with the row and column constraints. This holds because at the start of the $(k+1)$st failed attempt, only $k$ rows and $k$ columns have been committed. Since there are $2022$ middle rows and $2023$ columns, unresolved rows still have unused columns available. The adversary never places two monsters in the same column and never places more than one monster in a row.
Small cases support the argument. For a $3\times2$ board there is one monster and two columns. Turbo cannot guarantee success on the first attempt because whichever path he chooses, the adversary may place the monster on that route. He succeeds by the second attempt. For a $4\times3$ board there are two monsters and three columns; the same logic forces at least three attempts and the column-testing strategy achieves three.
Alternative Approaches
A different proof of the lower bound can be phrased using an adversarial matching argument. After $k<2022$ failed attempts, only $k$ rows and $k$ columns have been fixed. One shows, using a Hall-type extension argument, that the remaining unresolved rows can still be matched injectively to unused columns while avoiding all cells Turbo has previously proved safe. Hence a complete monster placement consistent with Turbo’s observations always exists until the $2023$rd attempt.
Another approach models Turbo’s information state. After fewer than $2023$ attempts, one can show that there always remains a legal placement under which every route Turbo has previously explored is blocked somewhere ahead. This converts the problem into maintaining ambiguity among feasible completions of the monster configuration. The essential obstruction is not uncertainty about the safe column itself, but the existence of a consistent adversarial completion preventing guaranteed success before attempt $2023$.