Ant Riddle
Adapted from 2024 IMO Problem 5
Prompt
An ant plays a game on a board with 1000 rows and 999 columns. There are trap doors in 998 of the cells. Initially, the ant does not know where any of the trap doors are, but it knows that there is exactly trap door in each row except the first row and the last row, and that each column contains at most one trap door. The ant makes a series of attempts to go from the first row to the last row. On each attempt, it chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (It is allowed to return to a previously visited cell.) If it reaches a cell with a trap door, its attempt ends and it is transported back to the first row to start a new attempt. The ant remembers whether or not each cell it has visited contains a trap door. If it reaches any cell in the last row, its attempt ends and the game is over. Determine the minimum value of n for which the ant has a strategy that guarantees reaching the last row on the nth attempt or earlier, regardless of the locations of the trap doors.
Answer guidance
The answer is 3, though some models find a very silly reason to think this. As of June, 2025, no model solves this correctly.
Answer : 999
Explanation
1. An upper bound – the ant can always succeed in at most 999 tries
There are 999 columns and at most one trap in any column, so one whole
column is completely free of traps.
Strategy of the ant
• Try the columns one after another.
• In the i-th attempt start in the first row of a column that has never been
tried, walk straight down that column and never leave it.
If the chosen column contains a trap the ant meets it and that attempt
finishes; the column is then known to be bad.
After the ant has eliminated 998 columns the only column that has not been
tried is the trap–free one, and the ant reaches the last row in the 999-th
attempt.
Hence the ant can be sure to arrive in 999 attempts.
2. A lower bound – no strategy can guarantee success in 998 (or fewer) tries
We show that, whatever
strategy the ant adopts, there is a fixed arrangement of the 998 traps that
forces it to fall through a trap on each of the first 998 attempts.
Fix the ant’s strategy.
We construct the board before the game begins, inductively over the
attempts.
• At the beginning no row (2 … 999) and no column is occupied by a trap.
• Suppose traps have already been put in the first t–1 attempts so that they
lie in t–1 different rows and t–1 different columns.
• Let the ant make its t-th walk (t ≤ 998) under the assumption that no
further traps exist. Because it starts in row 1 (which is safe) it must
step next into some cell of the still empty set of rows. Follow the walk
downward until it visits, for the first time, a row and a column that are
both still free of traps – call that cell (r_t , c_t). Such a cell must
appear because there are at least as many unused rows as unused columns
(998−(t−1) ≥ 999−(t−1)).
Place a trap in (r_t , c_t). It is the first trap met during this walk,
so the t-th attempt ends there. Moreover, row r_t and column c_t have now
become “used”, while all earlier traps keep their properties.
Repeating this for t = 1, 2, … , 998 we obtain
• exactly one trap in every row 2 … 999,
• the traps lie in 998 different columns,
• the ant is dropped through a trap in each of the first 998 attempts.
After those 998 traps have been placed only one column is still without a
trap; the ant has never set foot in that column, so it could not have
reached the last row earlier. Consequently no strategy can guarantee
success before the 999-th attempt.
3. Combining the two parts
The ant has a strategy that always finishes by the 999-th attempt, and
there is no strategy that is certain to finish earlier. Therefore
the least number n that can be guaranteed is
n = 999.Drag to resize
An elegant explanation of the solution:
Let $R=1000$ be the number of rows and $C=999$ be the number of columns. The cells are $(r,c)$ for $1 \le r \le R, 1 \le c \le C$.
There are 998 trap doors.
- Rows 1 and 1000 have no trap doors.
- Each row $r \in \{2, 3, \dots, 999\}$ has exactly one trap door.
- Each column has at most one trap door.
Since there are 998 rows with trap doors and 999 columns, the condition that each of these rows has one trap door and each column has at most one trap door implies that there are 998 distinct columns that contain one trap door each. This leaves exactly one column with no trap doors. Let's call this the "safe column".
The ant's goal is to find a path from row 1 to row 1000. If the ant knew the safe column, say $c_{safe}$, it could simply walk down that column from $(1, c_{safe})$ to $(1000, c_{safe})$ without hitting any trap doors. The core of the problem for the ant is to identify this safe column.
The ant only discovers a trap's location when it attempts to move to that cell, at which point the attempt ends. Each failed attempt reveals exactly one trap door.
Let's analyze the ant's knowledge. The ant can consider a column to be "unsafe" if it has found a trap door in it. To be certain which column is the safe one, the ant must identify all 998 unsafe columns.
Consider the number of attempts, $n$. We are looking for the minimum $n$ that guarantees success. This means we are looking for a strategy for the ant that works against any possible (worst-case) configuration of trap doors.
**Why n must be greater than 2:**
Let's see if the ant can guarantee a win on its second attempt ($n=2$).
For the ant to succeed on its first attempt, it must be lucky and choose the safe column to traverse. A strategy cannot rely on luck. So we must consider the case where the first attempt fails.
Attempt 1: The ant picks a path. To learn anything new, this path must enter a column it has not yet identified as unsafe. Let's say it starts by walking down column 1. In a worst-case scenario, the adversary has placed a trap in this path. For example, a trap at $(2,1)$. The attempt fails, and the ant now knows the location of one trap, say $(r_1, c_1)$.
Now it's time for Attempt 2. Can the ant choose a path that is *guaranteed* to be safe? A path is guaranteed to be safe only if it is safe for all possible configurations of the remaining 997 traps.
Let's call a cell "certified-safe" if it cannot be a trap, given the known information. After one trap at $(r_1, c_1)$ is known:
- Any cell $(r_1, c)$ with $c \ne c_1$ is certified-safe.
- For any row $r \ne r_1$ (and $r, r_1 \in \{2,..,999\}$), its trap can be in any column other than $c_1$. So, a cell $(r,c)$ with $r \ne r_1$ is not certified-safe if $c \ne c_1$.
The ant must build a path from row 1 to row 1000. Let's trace a path for Attempt 2. The path must cross all intermediate rows. Consider a row $r_2 \ne r_1$. Any path must visit a cell in this row, say $(r_2, c_2)$. For this cell to be on a guaranteed path, it must be certified-safe. Based on our rule, this requires $c_2 = c_1$.
This implies that for all rows $r \notin \{1, r_1, 1000\}$, a guaranteed path must stay strictly within column $c_1$.
So, a guaranteed path would have to look like this: travel down column $c_1$, somehow bypass the trap at $(r_1, c_1)$, and continue down column $c_1$.
To bypass $(r_1, c_1)$, the path must move sideways at row $r_1$ or $r_1-1$. For instance, from $(r_1-1, c_1)$ to $(r_1-1, c_2)$ for some $c_2 \ne c_1$. But the cell $(r_1-1, c_2)$ is not certified-safe, as the trap for row $r_1-1$ could be in column $c_2$.
Therefore, after finding only one trap, no fully certified-safe path from row 1 to row 1000 exists. The ant must take a risk. For any path it chooses in Attempt 2, the adversary can place a trap on its path. For example, if the ant tries to traverse column 2, the adversary can simply have placed the trap of some row on this path.
This means that no strategy can guarantee success on the second attempt. So, $n>2$.
**A strategy that guarantees success in 3 attempts:**
Let's show a strategy for $n=3$.
**Attempt 1:** The ant chooses to traverse column 1. It moves $(1,1) \to (2,1) \to (3,1) \to \dots$.
If this attempt succeeds, the game is over. If not, it's because there is a trap in column 1, say at $(r_1, 1)$. The ant now knows this trap's location.
**Attempt 2:** The ant chooses to traverse column 2. It moves $(1,2) \to (2,2) \to (3,2) \to \dots$.
If this succeeds, the game is over (in 2 attempts). If not, it's because there is a trap in column 2, say at $(r_2, 2)$, where $r_2 \neq r_1$.
**Attempt 3:** At this point, the ant knows two trap locations: $(r_1, 1)$ and $(r_2, 2)$. With this knowledge, the ant can for the first time construct a path that is guaranteed to be safe.
A cell $(r,c)$ is certified-safe if it cannot be a trap given that traps exist at $(r_1,1)$ and $(r_2,2)$.
- For any row $r \notin \{r_1, r_2\}$ (and $r \in \{2,..,999\}$), its trap can be in any column other than 1 or 2. So for such a row, cells $(r,1)$ and $(r,2)$ are certified-safe.
- For row $r_1$, any cell $(r_1, c)$ with $c \ne 1$ is certified-safe.
- For row $r_2$, any cell $(r_2, c)$ with $c \ne 2$ is certified-safe.
Assume without loss of generality $r_1 < r_2$. The ant can construct the following certified-safe path:
1. Start at $(1,2)$. Go down column 2 to $(r_1-1, 2)$. This part is safe because these rows are not $r_1$ or $r_2$ and column 2 is one of the "certified" columns.
2. At $(r_1-1, 2)$, move sideways to $(r_1-1, 1)$. This row is not $r_1$ or $r_2$, so moving within columns 1 and 2 is safe.
3. Move down to $(r_1, 1)$. This fails, the trap is there. Let's correct the path.
2. From $(r_1-1,2)$, move to $(r_1-1,c)$ for any c then to $(r_1, c)$, c must be different from 1. Let's use column 3 for an intermediate step. $(r_1-1,2) \to (r_1-1,3) \to (r_1,3)$. Cell $(r_1-1,3)$ is certified-safe because row $r_1-1$'s trap cannot be in column 1 or 2, but it CAN be in 3. So this cell is NOT certified safe.
Let's reassess the path with two known traps, $T_2=\{(r_1, c_1), (r_2, c_2)\}$.
Let's assume $c_1=1, c_2=2$ and $r_1<r_2$.
A certified-safe path:
1. Start at $(1,1)$. Descend to $(r_1-1, 1)$. These cells are of the form $(r,1)$ where $r \notin \{r_1,r_2\}$, so they are certified-safe.
2. At $(r_1-1, 1)$, move horizontally to $(r_1-1, 2)$. This is safe as $r_1-1 \notin \{r_1,r_2\}$.
3. From $(r_1-1, 2)$, move down to $(r_1, 2)$. This cell is safe as the trap for row $r_1$ is in column 1.
4. Now at $(r_1,2)$, descend along column 2 to $(r_2-1, 2)$. These cells are safe as their rows are not $r_1$ or $r_2$.
5. At $(r_2-1, 2)$, move horizontally to $(r_2-1, 1)$. This is safe.
6. From $(r_2-1, 1)$, move down to $(r_2, 1)$. This cell is safe as the trap for row $r_2$ is in column 2.
7. Now at $(r_2,1)$, descend along column 1 to $(1000, 1)$. These cells are safe.
This path consists entirely of certified-safe cells and takes the ant from row 1 to row 1000. Therefore, the third attempt is guaranteed to succeed.
The strategy is: test column 1, then column 2. If both attempts fail, the information gathered is sufficient to construct a path for a third attempt that is guaranteed to be successful. No matter where the traps are, this strategy ensures the ant reaches row 1000 on or before the third attempt.
Since $n>2$ and we have a strategy for $n=3$, the minimum value is $n=3$.Drag to resize
Alright, let's tackle this problem step by step. I'll start by trying to understand the scenario and then work towards finding the minimum number of attempts the ant needs to guarantee reaching the last row. ### Understanding the Problem We have a grid (board) with: - **1000 rows** (let's number them from 1 to 1000). - **999 columns** (number them from 1 to 999). **Trap Doors:** - **998 trap doors** in total. - Exactly **one trap door per row**, except for the first row (row 1) and the last row (row 1000), which have no trap doors. - So, rows where traps can be: rows 2 to 999 → 998 rows → 998 traps. - Each **column has at most one trap door**. This is crucial because it means no two traps are in the same column. **Ant's Movement:** - Starts any attempt on any cell of the first row (row 1). - Can move to adjacent cells (up, down, left, right) that share a side. - Can revisit cells. - If it steps on a trap (in rows 2-999), the attempt ends, and it's back to row 1 for a new attempt. - If it reaches any cell in the last row (row 1000), the game is over. **Knowledge:** - Initially, doesn't know where traps are. - After each attempt, remembers which visited cells have traps. **Goal:** Find the minimum number `n` such that the ant has a strategy guaranteeing it reaches row 1000 in `n` attempts or fewer, no matter how the traps are placed (given the constraints). ### Initial Observations 1. **Trap Distribution:** - 998 traps in rows 2-999, one per row. - Each column has at most one trap. So, traps are in distinct columns. - This means the traps form a "selection" where for each of the 998 rows, we pick one unique column. 2. **Columns:** - There are 999 columns, but only 998 have traps (since 998 traps in distinct columns). So, exactly one column has no trap in any row (from rows 2-999). 3. **Ant's Strategy:** - The ant can learn trap locations by stepping on them in previous attempts. - The idea is to systematically explore the grid to discover traps without getting caught too many times. ### Possible Strategies One common strategy in such problems is to use a "depth-first search" like approach where the ant tries to go as far as possible in each attempt, remembering the traps it hits to avoid them in future attempts. But given that columns have at most one trap, if the ant finds a trap in a column, it knows that whole column is safe below that row (but since each column has at most one trap, finding one in a column means no others in that column). Wait: each column has at most one trap in total (across all rows), so if a trap is found in a column, that column is entirely safe in all other rows (since no other traps there). ### Constructing the Strategy Here's a possible strategy: 1. **First Attempt:** - Start at column 1, row 1. - Move down to column 1, row 2. If no trap, move to row 3, etc., until reaching row 1000 or hitting a trap. - Suppose the trap is at (r1, 1). Then the ant hits it at row r1, and learns that column 1 has a trap at row r1. No trap elsewhere in column 1. 2. **Second Attempt:** - Start at column 2, row 1. - Move down column 2 until hitting a trap or reaching row 1000. - Suppose trap at (r2, 2), learns that. ... Repeat this for each column. Since there are 998 traps in 999 columns, one column has no trap. So, in the worst case, the ant tries 998 columns with traps (failing each time), and then the 999th column has no trap, so it can safely go all the way down. But wait: the ant doesn't know which column is safe. So it might have to try all 999 columns in the worst case (since the safe column could be the last one it tries). But we have only 998 traps, so at least one column is entirely safe (no traps in rows 2-999). So the ant can try columns one by one until finding the safe one. But is there a smarter way where the ant doesn't have to try all 999 columns? Alternatively, can the ant use the fact that in each attempt it can explore multiple columns? ### Better Strategy Instead of going down one column at a time, the ant can zigzag to explore multiple columns per attempt. Here's how: 1. In each attempt, the ant can choose a path that covers multiple columns. If it hits a trap, it knows that column's trap location and can avoid it in future attempts. 2. The idea is to maximize the number of new rows explored in each attempt until finding the safe column. But given that each column has at most one trap, if the ant hits a trap in a column, that column is "blocked" at that row, and the ant can't go past that row in that column in future attempts. Given that, one effective strategy is to try to construct a path that, when blocked by a trap, allows the ant to learn as much as possible to reduce the number of future attempts needed. ### Calculating the Minimal n A known approach in such problems is to realize that the ant can eliminate one potential trap per attempt (by finding one trap), except the last attempt where it finds the clear path. Given 998 traps and one clear column, the ant must discover all 998 traps, one per attempt, and then in the (998+1)th attempt, take the clear path. Thus, in the worst case, it would take 999 attempts: - First 998 attempts: each finds one trap (and fails). - 999th attempt: takes the remaining column which is clear, hence reaches the end. But can we do better? Probably not, because the traps could be arranged such that in each attempt, the ant only discovers one new trap (the most adversarial arrangement). For example: - The first attempt goes down column 1, finds trap at some row. - The second attempt tries column 2, finds trap there. - ... - The 998th attempt tries column 998, finds trap there. - The 999th attempt tries column 999, which has no trap, and succeeds. Any strategy that tries to cover multiple columns in one attempt could be thwarted by placing traps such that the ant only discovers one per attempt. Therefore, the minimal `n` is **999**. ### Verifying the Answer Let's think if `n = 999` is indeed necessary and sufficient: - **Necessary**: As shown, the worst-case trap arrangement can force the ant to try 998 columns with traps before finding the safe one, totaling 999 attempts. - **Sufficient**: With a strategy of trying one new column per attempt, the ant is guaranteed to find the safe column by the 999th attempt. Is there a way to do it in fewer attempts? Suppose the ant could learn multiple traps in one attempt, but since the ant can't see beyond its path and must physically move to discover traps, and traps are hidden until stepped on, it's hard to devise a strategy that consistently learns multiple trap locations per attempt without risking more failures. Thus, `n = 999` seems correct. ### Final Answer The minimum value of `n` for which the ant has a strategy guaranteeing to reach the last row on the `n`th attempt or earlier is **999**.
Drag to resize
The answer is n = 999. Sketch of why: 1. Number the columns 1,…,999. Between rows 2 and 999 there are exactly 998 traps, in 998 distinct columns. Hence there is exactly one “safe’’ column through which you can go straight from row 1 to row 1000. 2. On any attempt that doesn’t succeed you can learn at most one trap‐door location (you go down until you hit your first trap), and thereby eliminate one more column from contention. 3. To be certain which single column is the safe one you must eliminate all 998 trap‐columns, which in the worst case takes 998 failed attempts. Once those are known, the 999th attempt is simply “start in the one remaining column and go straight down’’—you will reach the last row. 4. You cannot do better, because before you have ruled out all 998 trap‐columns there will always be at least two columns that might still harbor the only completely trap‐free vertical path, so no earlier attempt can be guaranteed to succeed against an adversarial trap‐placement. Hence the minimum n for which you can force a win by the n-th attempt is n=999.
Drag to resize
## Step 1: Understand the problem and the constraints
The problem describes a game where an ant tries to navigate from the first row to the last row on a 1000x999 grid, with trap doors in 998 cells of each row except the first and last. The ant can move to adjacent cells and remembers the locations of trap doors it encounters.
## Step 2: Analyze the ant's movement and strategy
The ant can move in four directions (up, down, left, right) to adjacent cells. Since the ant knows that there's exactly one trap door in each row (except the first and last) and each column contains at most one trap door, it needs to devise a strategy that guarantees reaching the last row.
## Step 3: Consider the implications of the grid size and trap door distribution
Given that there are 1000 rows and 999 columns, and 998 trap doors in each of the 998 rows (excluding the first and last rows), the ant must navigate through the grid without knowing the exact locations of the trap doors initially.
## Step 4: Develop a strategy for the ant
To guarantee reaching the last row, the ant needs to systematically explore the grid. One possible strategy is for the ant to attempt to move through the grid in a systematic way, avoiding trap doors as it remembers their locations.
## Step 5: Understand that the ant can use its memory to avoid previously encountered trap doors
On each attempt, the ant learns more about the locations of the trap doors. The ant can use this information to plan its next attempt, avoiding cells it knows contain trap doors.
## Step 6: Recognize that the problem is asking for the minimum number of attempts required to guarantee success
The ant needs to find a path from the first row to the last row. Given the constraints, the ant can potentially use a strategy that involves trying different columns or paths until it finds one that is safe.
## Step 7: Consider a strategy involving attempting to cross the grid in different columns or paths
Since there are 999 columns and the ant starts from the first row, it can attempt to cross the grid. The presence of trap doors in 998 out of 999 columns in each row (except the first and last) means the ant has to find a column or a path that is safe.
## Step 8: Analyze the worst-case scenario and the ant's ability to learn from its attempts
In the worst case, the ant might need to try multiple paths. However, since it remembers the locations of trap doors, it can avoid them in subsequent attempts.
## Step 9: Determine the number of attempts required based on the grid's characteristics and the ant's learning
The ant has 999 columns to potentially use as a path. Since there's exactly one trap door per row (except the first and last), and at most one per column, the ant can systematically try paths.
## Step 10: Consider that the ant can guarantee success by trying all possible safe paths until it finds one that works
The key insight is that the ant can use its knowledge of trap door locations gained from previous attempts to inform its next attempt.
## Step 11: Realize that the ant needs to attempt to go through the grid in a way that covers all possibilities
Given that there are 998 rows with trap doors and 999 columns, the ant's strategy should involve exploring different paths until it succeeds.
## Step 12: Understand the solution involves a specific number of attempts that guarantees the ant will reach the last row
The ant's strategy should be based on the number of columns and the fact that it can remember and avoid trap doors.
## Step 13: Apply the strategy to the given grid size
For a grid with 1000 rows and 999 columns, and given the constraints on trap doors, the ant needs to strategize its path.
## Step 14: Calculate the minimum number of attempts needed based on the ant's strategy
Since the ant has to avoid trap doors and there are 998 trap doors in each of the middle 998 rows, the ant must find a path that avoids these. The ant can start by trying to go straight down a column. If it encounters a trap door, it learns that column has a trap door and can try another.
The final answer is: $\boxed{999}$Drag to resize
The ant must navigate a grid with 1000 rows and 999 columns, where 998 cells contain trap doors. These trap doors are located such that each row from 2 to 999 has exactly one trap door, and each column contains at most one trap door. The first row (row 1) and the last row (row 1000) have no trap doors. The ant starts each attempt from any cell in row 1 and moves to adjacent cells (up, down, left, right), with the attempt ending if it hits a trap door (resulting in a restart) or reaches any cell in row 1000 (ending the game). The ant remembers the status of visited cells.
The minimum \(n\) such that the ant has a strategy guaranteeing to reach row 1000 by the \(n\)th attempt, regardless of trap door locations, is 999. This is determined as follows:
- There are 999 columns and 998 trap doors, meaning one column has no trap door (the "clear" column).
- In the worst case, the ant may hit a trap door on each of the first 998 attempts by testing columns that contain trap doors. Each trap door hit reveals its location, allowing the ant to avoid that column in future attempts.
- After 998 failed attempts, the ant has identified all 998 trap doors and knows which column is clear.
- On the 999th attempt, the ant can traverse the clear column directly from row 1 to row 1000 without encountering any trap doors, guaranteeing success.
This strategy ensures success by the 999th attempt in the worst case. It is not possible to guarantee success by the 998th attempt because, after 997 trap door hits, one trap door and the clear column remain unknown. On the 998th attempt, the ant might hit the unknown trap door, requiring a 999th attempt to succeed. Thus, 999 is the{999}{999}{999}{999}Drag to resize
I need to find the minimum number of attempts that guarantees the ant can reach the last row regardless of trap door placement. Let me analyze the structure of this problem: **Board Setup:** - 1000 rows, 999 columns - 998 trap doors total - Exactly one trap door in each of rows 2, 3, ..., 999 (that's 998 rows) - No trap doors in row 1 or row 1000 - Each column has at most one trap door **Key Insight:** Since each of the 998 middle rows has exactly one trap door, and each column has at most one trap door, the trap doors form a partial matching between rows and columns. **Strategy Analysis:** Let me think about what the ant learns and how it can use that information. On each attempt, when the ant hits a trap door, it learns the location of that trap door. The ant needs to find a path from row 1 to row 1000 that avoids all trap doors. **Lower Bound:** Consider the worst-case scenario for the ant. The adversary (who places trap doors) wants to maximize the number of attempts needed. The key observation is that the ant must discover enough trap door locations to guarantee a safe path exists. **Critical Observation:** Since there are 999 columns and 998 trap doors (one per middle row), there is exactly one column that contains no trap doors. If the ant can identify this column, it can go straight down that column to reach row 1000. **Adversary's Strategy:** The adversary should place trap doors to make it as hard as possible for the ant to identify the safe column. **Ant's Optimal Strategy:** The ant should systematically explore columns to identify which one is safe. Let me work out the worst case: 1) The ant can try going straight down each column until it finds the safe one. 2) In the worst case, the safe column is the last one the ant tries. 3) When the ant goes down column $i$ and there's a trap door in that column, the ant will hit the trap door in some row $r$ (where $2 \leq r \leq 999$). This ends attempt number $i$. 4) The ant needs to try at most 999 columns to guarantee finding the safe one. **Detailed Analysis:** If the ant tries columns in order $1, 2, 3, \ldots$: - Attempt 1: Try column 1. If it has a trap door, the ant hits it and learns its location. - Attempt 2: Try column 2. If it has a trap door, the ant hits it and learns its location. - ... - Attempt $k$: Try column $k$. In the worst case, the safe column is column 999, so the ant would need 999 attempts. But wait, let me reconsider if the ant can do better. **Better Strategy:** Actually, the ant doesn't need to go all the way down each column. The ant could use a more sophisticated exploration strategy. However, the fundamental constraint remains: in the worst case, the ant needs to eliminate 998 columns as possibilities for the safe path. **Key Realization:** Since each column has at most one trap door, once the ant discovers a trap door in a column, that column is "bad" and the ant knows to avoid it completely. The worst case occurs when: - The safe column is the last one the ant checks - The ant must make one attempt per bad column to discover it's bad Therefore, the ant needs at most 999 attempts: 998 attempts to discover that columns 1 through 998 are bad (each containing exactly one trap door), and then attempt 999 succeeds by going down column 999. **Verification:** - After 998 attempts, the ant has identified 998 trap doors (one per column for 998 different columns) - This leaves exactly one column with no trap doors - On attempt 999, the ant can safely traverse this column from row 1 to row 1000 Therefore, $n = 999$.
Drag to resize