AoPS - Problem

LLL2019

17.07.2024 15:56

. This was initially proposed to our Test 1, which is very easy, but our coach told him to propose it IMO instead, resulting in most of our team being trolled by it.

chronondecay

17.07.2024 16:01

Could you please spoiler the answer? This is the first place that many people are going to see the question, and putting the answer right there completely robs them of the experience. (I'm not a fan of the title either.)

v_Enhance

17.07.2024 16:16

Surprisingly the answer is $n = 3$ for any grid size $s \times (s-1)$ when $s \ge 4$. We prove this in that generality. Proof that at least three attempts are needed. When Turbo first moves into the second row, Turbo could another a monster $M_1$ right away. Then on the next attempt, Turbo must enter the third row in different column as $M_1$, and again could encounter a monster $M_2$ right after doing so. This means no strategy can guarantee fewer than three attempts. Strategy with three attempts. On the first attempt, we have Turbo walk through the entire second row until he finds the monster $M_1$ in it. Then we get two possible cases. Case where $M_1$ is not on the edge. In the first case, if that monster $M_1$ is not on the edge of the row, then Turbo can trace two paths below it as shown below. At least one of these paths works, hence three attempts is sufficient. [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); int n = 6; for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); label((2.5,4.5), "$M_1$", red); dotfactor *= 2; dot((1.5,4.5), deepgreen); dot((3.5,4.5), deepgreen); draw((1.5,4.5)--(1.5,3.5)--(2.3,3.5)--(2.3,0.2), deepgreen+1.2, EndArrow(TeXHead)); draw((3.5,4.5)--(3.5,3.5)--(2.7,3.5)--(2.7,0.2), deepgreen+1.2, EndArrow(TeXHead)); [/asy][/asy] Case where $M_1$ is on the edge. WLOG, $M_1$ is in the leftmost cell. Then Turbo follows the green staircase pattern shown in the top figure below. If the staircase is free of monsters, then Turbo wins on the second attempt. Otherwise, if a monster $M_2$ is encountered on the staircase, Turbo has found a safe path to the left of $M_2$; then Turbo can use this to reach the column $M_1$ is in, and escape from there. This is shown in purple in the figure on the bottom. [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); int n = 6; for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); label((0.5,4.5), "$M_1$", red); dotfactor *= 2; dot((1.5,4.5), deepgreen); draw((1.5,4.5)--(2.5,4.5)--(2.5,3.5)--(3.5,3.5)--(3.5,2.5) --(4.5,2.5)--(4.5,1.5)--(5.5,1.5)--(5.5,0.2), deepgreen+1.2, EndArrow(TeXHead)); [/asy][/asy] [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); int n = 6; for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); label((0.5,4.5), "$M_1$", red); label((4.5,2.5), "$M_2$", red); dotfactor *= 2; dot((1.5,4.5), deepgreen); draw((3.5,2.5)--(4.5,2.5)--(4.5,1.5)--(5.5,1.5)--(5.5,0.2), deepgreen+dashed); draw((1.5,4.5)--(2.5,4.5)--(2.5,3.5)--(3.5,3.5)--(3.5,2.5)--(0.5,2.5)--(0.5,0.2), purple+1.5, EndArrow(TeXHead)); [/asy][/asy] Thus the problem is solved in three attempts, as promised.

Here are some additional comments on the problem, where I will try to give a description of the space of possible strategies, although this needs a bit of notation. The happy triangle. For simplicity, we use $s$ even only in the figures below. We define the happy triangle as the following cells: All $s-1$ cells in the first row (which has no monsters). The center $s-3$ cells in the second row. The center $s-5$ cells in the third row. \dots The center cell in the $\frac s2$th row. For $s=12$, the happy triangle is the region shaded in the thick border below. [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); void setup(int n) { for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); path p = (0,n); for (int i=0; i<n/2; ++i) { p = p--(i,n-1-i)--(i+1,n-1-i); } for (int i=(n+1)#2; i<n; ++i) { p = p--(i,i)--(i+1,i); } p = p--(n,n)--cycle; filldraw(p, invisible, blue+1.8); } setup(11); [/asy][/asy] Given a cell, define a shoulder to be the cell directly northwest or northeast of it. Hence there are two shoulders of cells outside the first and last column, and one shoulder otherwise. Description of some solutions. Then solutions roughly must distinguish between these two cases: Inside happy triangle: If the first monster $M_1$ is found in the happy triangle, and there is a safe path found by Turbo to the two shoulders (marked $\bigstar$ in the figure), then one can finish in two more moves by considering the two paths from $\bigstar$ that cut under the monster $M_1$; one of them must work. This slightly generalizes the easier case in the solution above (which focuses only on the case where $M_1$ is in the first row). [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); void setup(int n) { for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); path p = (0,n); for (int i=0; i<n/2; ++i) { p = p--(i,n-1-i)--(i+1,n-1-i); } for (int i=(n+1)#2; i<n; ++i) { p = p--(i,i)--(i+1,i); } p = p--(n,n)--cycle; filldraw(p, invisible, blue+1.8); } setup(7); label((2.5,4.5), "$M_1$", red); label((1.5,5.5), "$\bigstar$", deepgreen); label((3.5,5.5), "$\bigstar$", deepgreen); draw((1.5,5.5)--(1.5,3.5)--(2.3,3.5)--(2.3,0.2), deepgreen+1.2, EndArrow(TeXHead)); draw((3.5,5.5)--(3.5,3.5)--(2.7,3.5)--(2.7,0.2), deepgreen+1.2, EndArrow(TeXHead)); [/asy][/asy] Outside happy triangle Now suppose the first monster $M_1$ is outside the happy triangle. Of the two shoulders, take the one closer to the center (if in the center column, either one works; if only one shoulder, use it). If there is a safe path to that shoulder, then one can take a staircase pattern towards the center, as shown in the figure. In that case, the choice of shoulder and position guarantees the staircase reaches the bottom row, so that if no monster is along this path, the algorithm ends. Otherwise, if one encounters a second monster along the staircase, then one can use the third trial to cut under the monster $M_1$. [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); void setup(int n) { for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); path p = (0,n); for (int i=0; i<n/2; ++i) { p = p--(i,n-1-i)--(i+1,n-1-i); } for (int i=(n+1)#2; i<n; ++i) { p = p--(i,i)--(i+1,i); } p = p--(n,n)--cycle; filldraw(p, invisible, blue+1.8); } setup(9); label((1.5,3.5), "$M_1$", red); label((2.5,4.5), "$\bigstar$", deepgreen); draw((2.5,4.5)--(2.5,3.5)--(3.5,3.5)--(3.5,2.5)--(4.5,2.5)--(4.5,1.5)--(5.5,1.5)--(5.5,0.2), deepgreen+1.2, EndArrow(TeXHead)); [/asy][/asy] \qquad [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); void setup(int n) { for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); path p = (0,n); for (int i=0; i<n/2; ++i) { p = p--(i,n-1-i)--(i+1,n-1-i); } for (int i=(n+1)#2; i<n; ++i) { p = p--(i,i)--(i+1,i); } p = p--(n,n)--cycle; filldraw(p, invisible, blue+1.8); } setup(9); label((1.5,3.5), "$M_1$", red); label((2.5,4.5), "$\bigstar$", deepgreen); draw((2.5,4.5)--(2.5,3.5)--(3.5,3.5)--(3.5,2.5)--(4.5,2.5)--(4.5,1.5)--(5.5,1.5)--(5.5,0.2), deepgreen+dashed, EndArrow(TeXHead)); label((5.5,1.5), "$M_2$", red); draw((2.5,4.5)--(2.5,3.5)--(3.5,3.5)--(3.5,2.5)--(4.5,2.5)--(4.5,1.5)--(1.5,1.5)--(1.5,0.2), purple+1.5, EndArrow(TeXHead)); [/asy][/asy] Assertion that the staircase shape is necessary. We will prove the following proposition: in any valid strategy for Turbo, in the case where Turbo first encounters a monster upon leaving the happy triangle, the second path must outline the same staircase shape. The monsters pre-commit to choosing their pattern to be either a NW-SE diagonal or NE-SW diagonal, with a single one-column gap; see figure below for an example. Note that this forces any valid path for Turbo to pass through the particular gap. [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); void setup(int n) { for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); path p = (0,n); for (int i=0; i<n/2; ++i) { p = p--(i,n-1-i)--(i+1,n-1-i); } for (int i=(n+1)#2; i<n; ++i) { p = p--(i,i)--(i+1,i); } p = p--(n,n)--cycle; filldraw(p, invisible, blue+1.8); } setup(11); for (int i=0; i<7; ++i) { label((i+0.5,9.5-i), "$M$", red); } for (int i=7; i<10; ++i) { label((i+1.5,9.5-i), "$M$", red); } [/asy][/asy] We may assume without loss of generality that Turbo first encounters a monster $M_1$ when Turbo first leaves the happy triangle, and that this forces an NW-SE configuration. Then the following is true: Proposition: The strategy of Turbo on the second path must visit every cell in ``slightly raised diagonal'' marked with $\clubsuit$ in the figure below in order from top to bottom, until it encounters a second Monster $M_2$ (or reaches the bottom row and wins anyway). It's both okay and irrelevant if Turbo visits other cells above this diagonal, but the marked cells must be visited from top to bottom in that order. [asy][asy] usepackage("amssymb"); unitsize(0.7cm); pen gr = grey+linetype("4 2"); void setup(int n) { for (int i=0; i<=n-1; ++i) { draw((0,i)--(n,i), gr); } for (int i=0; i<=n; ++i) { draw((i,0)--(i,n-1), gr); } draw(box((0,-1), (n,0)), black); draw(box((0,n-1), (n,n)), black); draw(box((0,-1), (n,n)), black); label((n/2,n-0.5), "Starting row"); label((n/2,-0.5), "Goal row"); path p = (0,n); for (int i=0; i<n/2; ++i) { p = p--(i,n-1-i)--(i+1,n-1-i); } for (int i=(n+1)#2; i<n; ++i) { p = p--(i,i)--(i+1,i); } p = p--(n,n)--cycle; filldraw(p, invisible, blue+1.8); } setup(13); label((0.5,11.5), "($M$)", red+fontsize(9pt)); label((1.5,10.5), "($M$)", red+fontsize(9pt)); label((2.5,9.5), "($M$)", red+fontsize(9pt)); label((3.5,8.5), "$M_1$", red); label((4.5,7.5), "X", brown); label((11.5,1.5), "$M_2$", red); for (int i=1; i<=6; ++i) { label((11.5-i,1.5+i), "$\clubsuit$", deepgreen); } [/asy][/asy] Proof. If Turbo tries to sidestep by visiting the cell southeast of $M_1$ (marked X in the Figure), then Turbo clearly cannot finish after this (for $s$ large enough). Meanwhile, suppose Turbo tries to ``skip'' one of the $\clubsuit$, say in column $C$, then the gap could equally well be in the column to the left of $C$. This proves the proposition. $\blacksquare$ Remark: [Memories of safe cells are important, not just monster cells] Here is one additional observation that one can deduce from this. We say a set $\mathcal S$ of revealed monsters is called obviously winnable if, based on only the positions of the monsters (and not the moves or algorithm that were used to obtain them), one can identify a guaranteed winning path for Turbo using only $\mathcal S$. For example, two monsters in adjacent columns which are not diagonally adjacent is obviously winnable. Then no strategy can guarantee obtaining an obviously winnable set in $2$ moves (or even $k$ moves for any constant $k$, if $s$ is large enough in terms of $k$). So any valid strategy must also use the memory of identified safe cells that do not follow just from the revealed monster positions.

popop614

17.07.2024 16:21

Buh ?

carefully

17.07.2024 16:27

This must be the most troll problem ever, even more troll than APMO 2019 P4.

Blast_S1

17.07.2024 16:33

Redacted

Kingsbane2139

17.07.2024 16:34

Not suitable for IMO. No mathematical beauty. WHAT IS THE PSC DOING???

hotmonkey1

17.07.2024 16:37

second year in a row guessing the answer to a p5 combi wrong and completely failing it!!!!!!

kingu

17.07.2024 16:39

This problem is a cook. The title should be changed, it is not inadequate

ABCDE

17.07.2024 16:50

Notably, the fifth problem of this IMO is the same as the fifth round of Squid Game, which is this problem on a $37\times2$ grid with one monster in every other row.

IAmTheHazard

17.07.2024 17:08

The answer is $3$. Renumber the rows to start with $0$, so the first row with monsters is row $1$. Impose a coordinate system $(\text{row},\text{col})$ in the obvious way. To see that at least $3$ attempts are required, suppose that Turbo first move out of the zeroth row is onto $(1,n)$. It could be the case that he encounters a monster there. In this case, if Turbo could win for $n=2$ then his next attempt must remain within either row $1$ or column $n$, since he could bump into another monster the instant he steps out. But since $(1,n)$ is occupied this is clearly impossible. For a strategy for at least $3$ attempts, Turbo moves onto $(1,2)$ and then moves right until $(1,2022)$. If he encounters a monster on $(1,n)$, then his next attempts are $(0,n-1) \to (1,n-1) \to (2,n-1) \to (2,n) \to (2023,n)$ and $(0,n+1) \to (1,n+1) \to (2,n+1) \to (2,n) \to (2023,n)$, and one of these must work. Otherwise Turbo moves onto $(1,1)$ and then $(1,2023)$ if possible; one of these must have a monster on it; WLOG $(1,1)$ since both actually give the same amount of information. Turbo's next move repeats the following procedure for $k=2,3,\ldots$: he moves onto $(k,k+1)$, then moves rightwards until $(k,2023)$. If Turbo doesn't encounter a monster during the process for $k$, then he gains the knowledge that there must be a monster on $(k,k)$ since there's nowhere else for it to go (by induction). If Turbo encounters a monster at some point, then he knows that there is no monster on $(k,k)$, but a monster on $(k-1,k-1)$. Then on his third and final attempt he can move to $(k,k) \to (k,k-1) \to (2023,k-1)$. If Turbo never encounters a monster then he eventually ends up on $(2022,2023)$, and can win by moving down. $\blacksquare$

circlethm

17.07.2024 17:13

Rough writeup because I'm retired. Cute problem but idk what the committee was thinking Strategy. We want a strategy that works in the 'worst case'. So start by assuming we hit a monster in Row 1 (start on leftmost cell, move right until we get the monster). Case 1. Hit it at the first or last cell. WLOG say monster at (1, 1). Then ideally we'd start at (2, 1), and we could try to go around it with (2, 2), (2, 3), (1, 3), and straight up to the top.Worst case we then hit a monster at one of (2, 2) or (2, 3). If we hit it at (2, 2), we keep having the problem of needing to take right steps and going up. So let's preempt that loop by just trying that strategy: we go (2, 1), (2, 2), (3, 2), etc. Worst case this fails at some step. If the step was an upward step, then we now have a cleared row so we can go back along to the original monster's column and go up, done. If the step was a rightward step, then we can retrace our steps until we are again beside the monster, but then go along that row until the column of the first monster. Go up, done Case 2. Hit it somewhere in the middle. We try go around it on the right as before, if this fails we can just go in the other direction and it works. This works in 3 moves. Optimal. To see 3 is optimal, suppose we start at (k, 1). We place a monster at (k, 1). That's one attempt gone. Then they must go upwards at some point, and they only know a monster cannot be at column k, so when they eventually do move up to (l, 2), we can have placed a monster there already.

Chus

17.07.2024 18:05

OMGGG that's my problem... Sorry for trolling y'all More about the backstory in a bit..

To be honest I really didn't find this problem to be that hard - I was just playing around with different conditions on Turbo's movement/the monsters and trying to see if I could figure out optimal strategies, and I also solved it (in its current setting) in quite a short time without knowing beforehand the exact bound (or even whether such a bound is easy to find...) tho back at that time I was just using the 6x6 board and not the 2024x2023 one right now. That said I don't think this should be a major factor(?) coz when solving this everyone prolly should have experimented with smaller boards first anyways (and would have found the O(1) strat) so I definitely expected this to be a P1/4 if this appeared on the IMO at all... One point though after discussing with my teammates (obviously very frustrated at me lol, my bad ) is it could have been an easy solve for everyone should this just appeared in a easy selection test/an easier position coz most people prolly thought a P5 problem should be more complicated than this. Also some pointed out that 2023/5 could mislead people into thinking the answer is something like log(2024) (but again I feel like these kinds of problems should always be approached first by testing out small examples rather than making wild guesses about the answer... would love to hear more about where people got stuck/misled/trolled on ) From what I heard about the jury meetings apparently the PSC really liked my problem (for some reason lol) and there was also a lot of support/cheering for Turbo among the team leaders when it got voted in leaders of some (traditionally) stronger teams did try to replace/change it tho (understandable coz obviously people are gonna get trolled) tho I guess this problem is pretty "populist" in some sense (not my intention) so it was always gonna make it onto the paper - in all honesty though after trying both days I felt like either P2 should be harder or P3 should be tuned down for this to make a balanced paper as a whole and not screw up the cutoffs idkkk (I guess we'll see the stats in a few days!)

Anyways hope everyone still enjoyed the problem nevertheless : ) ps i think this broke the record for imo problem with the most words wow pps turbo beats ai (at least for now) letsgoooooo

kingu

17.07.2024 18:09

Don't be! It is enjoyable and fun (tho yeah...)

TheStrayCat

17.07.2024 18:14

carefully wrote: This must be the most troll problem ever, even more troll than APMO 2019 P4. Hard to beat IMO 2010/5.

Sammy27

17.07.2024 18:29

The answer is $\boxed{n=3}$. Claim: $n\geq 3$. Proof. It is easy to see that $n=1$ does not guarantee victory: There may be a monster hiding in any cell in the second row, and if the first cell in the second row we move to has a monster, then the attempt is over. To see why $n=2$ does not guarantee victory, suppose we failed in our first attempt by falling victim to the monster at $(2, i)$ for some $i\in[1, 2023]$. Hence, the second row except the cell $(2, i)$ is now safe. The safe $(3, i)$ cell is inaccessible from here, and any accessible cell in the third row may hide a monster in it. The first cell in the third row we move to could contain a monster, and that would end the attempt there. $\blacksquare$ We proceed to show that $n=3$ is sufficient. Use the first attempt to scan the second row. Case 1: The monster in the second row is at $(2, 1)$ or $(2, 2023)$. WLOG, say it is hiding in the cell $(2, 1)$. In our second attempt, we go along the path $$(1,2)\to(2,2)\to(2,3)\to\text{P}\to(2024,2023)$$where a 'staircase' path $\text{P}$ is defined by $$(3,3)\to(3,4)\to(4,4)\to(4,5)\to\cdots\to(2022,2023)\to(2023,2023).$$If path $\text{P}$ is safe, then we are done. Otherwise, suppose we encounter a monster in path $\text{P}$ at $(k,k)$ or $(k,k+1)$ for some $k\in[3,2023]$. Either way, in our third attempt, we first go along the path $$(1,2)\to(2,2)\to(2,3)\to\cdots\to(k-1,k-1)\to(k,k-1)$$and then along the path $$(k,k-1)\to(k,k-2)\to\cdots\to(k,1)\to(k+1,1)\cdots\to(2024,1),$$which finishes the game. Case 2: The monster in the second row is at $(2,i)$ where $i\in[2,2022]$. Define paths $\text{P}_1$ and $\text{P}_2$ as $$(1,i-1)\to(2,i-1)\to(3,i-1)\to(3,i)\to(4,i)\to(2024,i)$$and $$(1,i+1)\to(2,i+1)\to(3,i+1)\to(3,i)\to(4,i)\to(2024,i)$$respectively. Notice that only one of the two cells $(3, i-1)$ and $(3,i+1)$ may hide a monster. Consider the worst-case scenario, where one of them indeed does. WLOG, suppose we go along path $\text{P}_1$ in our second attempt and encounter a monster. Then $\text{P}_2$ must be safe, and we go along $\text{P}_2$ in our third attempt to finish. $\blacksquare$

gghx

17.07.2024 18:41

I'm getting PTSD

David-Vieta

17.07.2024 18:44

The answer is $3$ for every $(m+1,m)$ board, where $m\ge 3$. First prove that Turbo can't win in $2$ steps. Let the first step Turbo steps into the second row and the first step into the third row be a monster. Then we will give a strategy. Let $(i,j)$ be the $i$th row and the $j$th column. First, Turbo will explore $(2,2),(2,3),...,(2,m-1)$. If there is a monster at $(2,j)$, WLOG $j < m-1$, then explore $(3,j-1)$, if being safe then go back to column $j$, otherwise go to $(3,j+1)$ and turn left to $(3,j)$. Moving down then the problem is done. Thus assuming that $(2,2),(2,3),...,(2,m-1)$ are safe. Next Turbo will explore $(3,2),(3,3),...,(3,m-1)$. Case 1: If there exists a monster at $(3,3),...,(3,m-2)$, in the same way we are done. Case 2: If there exists no monster, then explore $(4,2),(4,3),...,(4,m-1)$. There must exist a monster because the first and $m$'th column's monsters hide in row $2$ and $3$. Grids $(4,2),(4,m-1)$ can't be both monsters, choose a safe one to turn into $(4,1)$ or $(4,m)$ and moves down, by that may we are down. Case 3: So the only case is that there exists a monster in $(3,2)$ WLOG. Then Turbo will explore $(2,m)$, if existing monsters then move from $(3,3)$ to $(3,m)$ and moves down. Then explore $(4,4),..,(4,m),(5,5),...,(5,m),...,(m,m)$ row by row. If all are safe then move to $(m+1,m)$. Otherwise there exists a monster at $(i,j),4\le i \le j \le m$, then first go to $(i-1,i-1)$ as it's safe, then move to $(i,i-1)$ as row $i$th monster has been found. Move to $(i,2)$ next, then moving down.$\blacksquare$

GuvercinciHoca

17.07.2024 20:15

The biggest disappointment I've seen in imo...

carefully

22.07.2024 16:06

andychang wrote: See

Seems like we should add another definition to that entry.

JuanOrtiz

22.07.2024 21:55

Neat problem!

.

I think it is reasonable to, at first, expect $X=n$ or $\frac{n}{2}$ (perhaps cutting the board in half and using symmetry). Maybe using two symmetries it could be ${X=2024}/{4}$, or perhaps a more extravagant answer like $X=O(\sqrt{n})$ or $X=O(\log n)$. In fact, $\log_2(n)$ doesn't seem crazy. From an Information Theory perspective, we can think of each attempt as giving us a bit of information (either it worked or it didn't), and perhaps we need at least $n$ bits of information to guarantee a safe path. However, our first realization is that each attempt gives us a lot more than one bit of data. Indeed, each path uses at least $n$ squares, and there are $\ge n$ possible results, because we also discover exactly where the monster is on that path. The second clue is that Turbo can go backwards and revisit squares. Immediately we know this is either useless, or it must be a key part of our strategy. If it's useless, we should be able to prove that any strategy that works can be adapted to a strategy that also works but never goes backwards (this could even be a Lemma that gives 1/2 points if this were the solution). I spent some time trying to prove this and didn't get anywhere; this made me suspect going backwards must actually be used in the solution. In fact, without going backwards, you always have at most $3$ new squares to visit. But with going backwards, you in fact have $P$ new squares you can visit, where $P$ is the "perimeter" of the region of squares you have currently visited (i.e. the set of squares you haven't visited but are adjacent to one you have). The extra flexibility makes the number of different possible paths to victory VERY large, roughly $O((n^2)^n)$, because "most of the time" $P\approx O(n)$. Now, each strategy can be thought of as a directed tree of depth $X$ with an extra terminal "winning" node. Each node is a path (an attempt at winning). If a node's path visits $s$ squares, then it has $s+1$ children: either we won and the edge arrives at the winning node, or we fail and we get $s$ new nodes depending on which square the monster was on. Thus, each node has at least $O(n)$ children but can have as many as $O(n^2)$ children if we start going backwards. Thus, the number of nodes is between $O(n^{X-1})$ and $O(n^{2(X-1)})$. Thus, even for small $X$, we get an absurd number of nodes. Specially compared to the number of possible configurations of monsters: there are roughly $(n+1)!$. In fact, the number of possible configurations should greatly exceed the number of nodes for an optimal tree: almost any given serious "candidate path" will work for many different configurations, e.g. just using one column works for $n!$ configurations. Thus we'd only need roughly $\frac{(n+1)!}{n!}=n+1$ nodes, not $n^n$ or even $n^{\log n}$. All of this hints at $X=O(1)$.

Consider the pyramid $P$ comprised of the middle $n-1$ squares of the first row, the middle $n-3$ squares of the second row, and so on, until we have the middle square of the $\frac{n}{2}$-th row. On our first try, we can (try to) traverse $P$; the exact order won't matter as long as we go row-by-row. Case 1: We die before completing $P$. Assume we die on the $i$-th row, $1\le i\le \frac{n}{2}$, on square $S$. If we reach the square below $S$, i.e. $S+(1,0)$, we win, because that column only has one monster (on $S$), so we can use it to safely descend. (The remainder of the proof for this case will assume, for linguistic convenience, that $i>1$, but the case $i=1$ is identical). Now, by construction, we can reach $S+(-1,-1), S+(-1,0), S+(-1,1)$ safely using $P$. Next, we can attempt to go around $S$ to the right $S+(-1,1) \to S+(0,1) \to S(1,1) \to S+(1,0)$ or similarly the left. At most one of these attempts will fail, since only one of $S(1,1)$ and $S(1,-1)$ can have a monster in it. Thus, using 2 more tries, we can win. Case 2: We complete $P$. We're now at the middle square of row $\frac{n}{2}$ having died zero times; call this square $M$. Walk the entirety of this row until we find a monster and die. WLOG it is on square $S$ to the left of $M$. On our second try, we traverse $P$ again to reach $M$. Now, consider the following staircase $Q$: starting at $M$, draw the diagonal going right-and-down, and the horizontal line going right; these define an angle of $45^\circ$, which along with the right edge of the board defines the limits of $Q$. It has $\frac{n}{2}+1$ squares on the row of $M$, $\frac{n}{2}$ squares on the next row, and so on, and it has $0$ squares on the last (monster-free) row. We now (try to) traverse $Q$ row-by-row. We won't die on the first row of $Q$ because the monster on that row is to the left of $M$. If we succeed in traversing $Q$, when we reach its last square, we've won. Otherwise, we die at some point. Assume we die on $T = M + (i, j)$, where $j\ge i \ge 1$. Then, on our third try: 1. Traverse $P$ to reach $M$ 2. Traverse $Q$ until you reach $T+(-1, -1)$. 3. You can now safely walk $T +(-1,-1) \to T+(0,-1) \to T+(0,-2) \to \ldots \to T+(0,-k)$, where $k$ is such that $T+(0,-k)$ is on the same column as $S$. This is because $T$ has a monster, so the rest of its row is vacant. 4. Since $S$ has a monster and is above $T+(0,-k)$, the rest of that column is vacant. Thus, we can safely traverse $T+(0,-k) \to T+(1,-k) \to \ldots \to T+(\ell, -k)$ such that the last square is on the last row. We've won!

v_Enhance

23.07.2024 13:27

EthanWYX2009 wrote: My main question is: Does anyone know who translated the problems? Because seems like in other languages it is "Turbo the snail", but in Chinese version, it is wrote as "Mr Beans", making the problem even more funny Team leaders do the translations.

v_Enhance

23.07.2024 13:51

I've added some extended comments in https://aops.com/community/p31218951 (post #4) about some partial classification on the space of possible algorithms to this problem.

Jack_w

25.07.2024 08:28

Goofy problem. We claim the answer is $\boxed{\bf{n = 3}}$. $\underline{\text{Construction}}$ Index the rows ${1, 2, \dots, 2022}$ (Turbo starts in row 0) and the columns ${1, 2, \dots, 2023}$. We denote a cell by $(\text{row}, \text{column})$. The idea is to locate the monster in the first row; then, if Turbo can get into the same column past it, he can move straight forward and win. On the first attempt, Turbo enters the first row at $(1, 1)$ and moves right, scanning the whole first row until he finds the monster. Let the monster be in cell $(1, m)$. If $m \notin \{1, 2023\}$, Turbo tries to go from $(1, m-1) \rightarrow (2, m-1) \rightarrow (2, m)$ and forward. The only way this could fail is if there is a monster in $(2, m-1)$; then, there is not a monster in $(2, m+1)$ so Turbo goes from $(1, m+1) \rightarrow (2, m+1) \rightarrow (2, m)$ and forward to win on attempt 3. The other case is where the monster in the first row is on the end, i.e. $m \in \{1, 2023\}$. WLOG, $m = 1$ by symmetry. Turbo can now win by attempting the silly zigzag path $(1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4) \dots (2021, 2022) \rightarrow (2021, 2023) \rightarrow (2022, 2023)$ and forward to win. If Turbo encounters a monster while going from $(n-1, n+1)$ to $(n, n+1)$, then he knows the $n$th row is clear to the left, so he can repeat the zigzag but instead go from $(n-1, n)$ to $(n, n)$, left to the first column (since the $n$th row is clear), and forward to win on attempt 3. Similarly, if Turbo encounters a monster while going right from $(n, n+1)$ to $(n, n+2)$, repeat the same path but instead go from $(n, n+1)$ left to $(n, 1)$ and forward to win on attempt 3. $\underline{\text{Necessity}}$ It suffices to show there is a configuration of monsters where Turbo fails on the second attempt. Suppose Turbo begins his first attempt by going to $(1, x)$. There exists a configuration with a monster in $(1, x)$, so it's possible for Turbo to hit a monster immediately. If so, all rows except the first are unknown. In particular, Turbo has no knowledge about the location of the monster in the second row besides the fact that it's not in the $x$th column. Now consider his next attempt. Suppose the first cell Turbo touches which is not in the first row is $(2, y)$. It follows that $x \neq y$ because the monster on $(1, x)$ blocks a direct path to $(2, x)$. For all $1 \leq x, y \leq 2023$ with $x \neq y$, there exists some configuration with monsters in $(1, x)$ and $(2, y)$. Therefore it's always possible for Turbo to die immediately upon entering both the first and second rows, regardless of his strategy. So $n = 2$ is impossible.

TurboTheSnail

25.07.2024 14:29

Easy, solved it in 3 tries

kingafan

26.07.2024 05:40

I initially thought the answer was O(log n), but then my friend reminded me that this is a high school math competition. That's when I realized the answer had to be a constant, and I solved it in five minutes.

jerrome2685

26.07.2024 17:22

Actually, log n bound also appears frequently in IMO (for example, see IMO 2023/5)

ryanbear

26.07.2024 22:21

note that n=2 doesn't work, since the first time the snail enters the second row, it could hit a monster, and then the first time it enters the third row, it could hit another monster n=3 works

Attachments:

john0512

02.08.2024 00:23

The answer is $3$. A death on the first row is unavoidable, and after that happens, a death on the second row is also unavoidable, as Turbo must enter the second row on a column that has not had a monster yet. Thus at least $3$ attempts are needed. The strategy is as follows. Take a death on the first row (e.g. by trying to visit every cell). If the monster on the first row is not on the edge, then try to go to the cell beneath it from both directions, at least one will succeed, thus winning in at most $3$ attempts. Now, assume WLOG that the leftmost cell has the monster (it is actually symmetric to the right since Turbo knows where the monster is). Call the $k$th row good if it has a monster on the $k$th cell. We know that the first row is good. Main Claim: For $1\leq n\leq 2022$, If Turbo knows that the first $n$ rows are all good, Turbo can employ a strategy to either die on row $n+1$ and win on the next attempt, or learn that row $n+1$ is also good without dying. Turbo can simply visit cells $n+2$ through $2023$ of row $n+1$. If the row is not good, then he dies, but he can win on the next attempt by going back there and using cell $(n+1,n+1)$ to sneak under row $n$'s monster and win. Otherwise, he does not die and learns that row $n+1$ is also good. Thus, by employing this strategy, if any row is not good, Turbo will die on the first non-good row and win on the third attempt. Otherwise, if all rows are good, he does not die at all during this process, and wins on his second attempt.

Warideeb

06.08.2024 19:33

Wow, just took 10 mins to solve

mathismyfriend24

21.08.2024 04:11

By: mathismyfriend24 According to my foremost calculations, The answer is n = 3. Solution First we demonstrate that there is no winning strategy if Turbo has 2 attempts. Suppose that (2, i) is the first cell in the second row that Turbo reaches on his first attempt. There can be a monster in this cell, in which case Turbo must return to the first row immediately, and he cannot have reached any other cells past the first row. Next, suppose that (3, j) is the first cell in the third row that Turbo reaches on his second attempt. Turbo must have moved to this cell from (2, j), so we know j ≠ i. So it is possible that there is a monster on (3,j ), in which case Turbo also fails on his second attempt. Therefore Turbo cannot guarantee to reach the last row in 2 attempts. Next, we exhibit a strategy for n = 3. On the first attempt, Turbo travels along the path (1,1) (2,1) (2, 2) ... (2, 2023). This path meets every cell in the second row, so Turbo will find the monster in row 2 and his attempt will end. If the monster in the second row is not on the edge of the board (that is, it is in cell (2, i) with 2<= i <=2022), then Turbo takes the following two paths in his second and third attempts: (1, i - 1) (2, i -1) (3, i -1) Ñ(3, i) (4, i) …. (2024, i). (1, i -1) (2, i -1) (3, i - 1) (3, i) (4, i) …. (2024, i). The only cells that may contain monsters in either of these paths are (3, i -1) and (3, i -1). At most one of these can contain a monster, so at least one of the two paths will be successful. In conclusion, the final answer is n=3. (FYI, 2022 is the largest value of n) btw, Ñ is an arrow.

megahertz13

29.08.2024 17:40

Scilyse

27.09.2024 08:32

The answer is three (which is not enough in my opinion). To show that Turbo cannot win in two attempts, simply kill Turbo when he moves onto the second row, then kill Turbo again when he moves onto the third row (necessarily in a different column). To show that Turbo can always win in three attempts, first locate the monster in the second row, killing Turbo once in the process. If the monster is not on either of the board's edges, then move to one of the cells diagonally below where the monster is; since both of the aforementioned cells cannot be occupied by monsters, Turbo dies at most once here, and hence he can move to the column below the first monster and proceed to win. [asy][asy] unitsize(0.75cm); int cols = 9; for(int i = 1; i <= cols - 1; ++i) { draw((i, 1) -- (i, cols),grey); } draw((0, 1) -- (0, cols)); draw((cols, 1) -- (cols, cols)); for(int i = 2; i <= cols - 1; ++i) { draw((0, i) -- (cols, i),grey); } draw((0, 1) -- (cols, 1)); draw((0, cols) -- (cols, cols)); filldraw((0,1)--(0,0)--(cols,0)--(cols,1)--cycle,invisible,black); filldraw((0,cols)--(0,cols+1)--(cols,cols+1)--(cols,cols)--cycle,invisible,black); label((3.5, cols-0.5),scale(1.5)*"$\times$",red); label((2.5, cols-1.5),scale(1.5)*"$\times$",red); // filldraw((4,cols-2)--(5,cols-2)--(5,cols-1)--(4,cols-1)--cycle,palegreen,grey); draw((2.5,cols+0.5)--(2.5,cols-1.3),blue+linewidth(1.2),EndArrow(TeXHead)); draw((4.5,cols+0.5)--(4.5,cols-1.5)--(3.5,cols-1.5)--(3.5,0.5),blue+linewidth(1.2),EndArrow(TeXHead)); [/asy][/asy]Otherwise, move Turbo in the following "staircase" (mirrored if the monster is on the other side): [asy][asy] unitsize(0.75cm); int cols = 9; for(int i = 1; i <= cols - 1; ++i) { draw((i, 1) -- (i, cols),grey); } draw((0, 1) -- (0, cols)); draw((cols, 1) -- (cols, cols)); for(int i = 2; i <= cols - 1; ++i) { draw((0, i) -- (cols, i),grey); } draw((0, 1) -- (cols, 1)); draw((0, cols) -- (cols, cols)); filldraw((0,1)--(0,0)--(cols,0)--(cols,1)--cycle,invisible,black); filldraw((0,cols)--(0,cols+1)--(cols,cols+1)--(cols,cols)--cycle,invisible,black); label((0.5,cols-0.5),scale(1.5)*"$\times$",red); draw((1.5,cols+0.5)--(1.5,cols-1.5)--(2.5,cols-1.5)--(2.5,cols-2.5)--(3.5,cols-2.5)--(3.5,cols-3.5)--(4.5,cols-3.5)--(4.5,cols-4.5)--(5.5,cols-4.5)--(5.5,cols-5.5)--(6.5,cols-5.5)--(6.5,cols-6.5)--(7.5,cols-6.5)--(7.5,cols-7.5)--(8.5,cols-7.5)--(8.5,cols-8.5),blue+linewidth(1.2),EndArrow(TeXHead)); [/asy][/asy]If Turbo doesn't hit a monster, then he wins; otherwise, perform one of the following manoeuvres depending on the position of the monster relative to the staircase: [asy][asy] unitsize(0.75cm); int cols = 9; for(int i = 1; i <= cols - 1; ++i) { draw((i, 1) -- (i, cols),grey); } draw((0, 1) -- (0, cols)); draw((cols, 1) -- (cols, cols)); for(int i = 2; i <= cols - 1; ++i) { draw((0, i) -- (cols, i),grey); } draw((0, 1) -- (cols, 1)); draw((0, cols) -- (cols, cols)); filldraw((0,1)--(0,0)--(cols,0)--(cols,1)--cycle,invisible,black); filldraw((0,cols)--(0,cols+1)--(cols,cols+1)--(cols,cols)--cycle,invisible,black); label((0.5,cols-0.5),scale(1.5)*"$\times$",red); label((4.5,cols-4.5),scale(1.5)*"$\times$",red); draw((1.5,cols+0.5)--(1.5,cols-1.5)--(2.5,cols-1.5)--(2.5,cols-2.5)--(3.5,cols-2.5)--(3.5,cols-3.5)--(4.5,cols-3.5)--(4.5,cols-4.3),blue+linewidth(1.2),EndArrow(TeXHead)); draw((3.5,cols-3.5)--(3.5,cols-4.5)--(0.5,cols-4.5)--(0.5,0.5),purple+linewidth(1.2),EndArrow(TeXHead)); for(int i = 1; i <= cols - 1; ++i) { draw((i+cols+0.75, 1) -- (i+cols+0.75, cols),grey); } draw((0+cols+0.75, 1) -- (0+cols+0.75, cols)); draw((cols+cols+0.75, 1) -- (cols+cols+0.75, cols)); for(int i = 2; i <= cols - 1; ++i) { draw((0+cols+0.75, i) -- (cols+cols+0.75, i),grey); } draw((0+cols+0.75, 1) -- (cols+cols+0.75, 1)); draw((0+cols+0.75, cols) -- (cols+cols+0.75, cols)); filldraw((0+cols+0.75,1)--(0+cols+0.75,0)--(cols+cols+0.75,0)--(cols+cols+0.75,1)--cycle,invisible,black); filldraw((0+cols+0.75,cols)--(0+cols+0.75,cols+1)--(cols+cols+0.75,cols+1)--(cols+cols+0.75,cols)--cycle,invisible,black); label((0.5+cols+0.75,cols-0.5),scale(1.5)*"$\times$",red); label((5.5+cols+0.75,cols-4.5),scale(1.5)*"$\times$",red); draw((1.5+cols+0.75,cols+0.5)--(1.5+cols+0.75,cols-1.5)--(2.5+cols+0.75,cols-1.5)--(2.5+cols+0.75,cols-2.5)--(3.5+cols+0.75,cols-2.5)--(3.5+cols+0.75,cols-3.5)--(4.5+cols+0.75,cols-3.5)--(4.5+cols+0.75,cols-4.5)--(5.3+cols+0.75,cols-4.5),blue+linewidth(1.2),EndArrow(TeXHead)); draw((4.5+cols+0.75,cols-4.5)--(3.5+cols+0.75,cols-4.5)--(0.5+cols+0.75,cols-4.5)--(0.5+cols+0.75,0.5),purple+linewidth(1.2),EndArrow(TeXHead)); [/asy][/asy]and Turbo wins, as desired.

Zfn.nom-_nom

14.12.2024 13:36

Imagine using a braindead algorithm: there are $2023$ columns and $2022$ monsters. You can try distinct columns until you find the one without any monsters, which would take $2023$ attempts in the worst case. Now imagine a simple algorithm that uses memory: start at column $1$. If you hit a monster, reroute around it while staying as close as possible. If you encounter another monster while rerouting, restart at that column and reroute around the new monster. Repeat until you bypass the connected blob of monsters. A worst-case monster arrangement for this strategy is a diagonal line stretching from the end of column $1$ to the start of column $2022$, with column $2023$ free. This would also require $2023$ attempts. Can we do better? Yes, and here’s how: The simple algorithm requires $n$ steps to find any possible path through $n$ columns but fails because the first $2022$ attempts are tested on impossible column configurations. Note that every impossible configuration consists of monsters arranged in a diagonal line. To improve, consider the following algorithm: First, check the first and last columns. If neither column is the gap, observe that there cannot be a diagonal line stretching from the monster in column $1$ to the monster in column $2023$. This guarantees a possible path through the $2023$ columns. Next, test the middle column. One or both sides of the split cannot form a solid diagonal line, so at least one half contains a valid path. Repeat this process, testing the middle of the remaining side, until the gap is found. Since the number of columns is $n = 2023$, the number of steps required is approximately: \[ 2 \text{ (initial setup)} + \log_2(n) \text{ (halvings)} + 1 \text{ (final check)}. \]For $n = 2023$, $\log_2(2023) \approx 11$, so the total number of steps is: \[ 2 + 11 + 1 = 14. \] This binary search-like algorithm reduces the number of attempts from $2023$ to $14$, providing a significant improvement. i think i can get down to two . visual solution(https://imgur.com/hIRP6QQ ) for 10*9, generalizable to (2n)*(2n-1).