and has written down in a line,and in increasing order,all his positive divisors 
(where 
and 
)
numbers (the greatest common divisors) is equal to 
.
.
of positive integers such that 
.
be a sequence of positive integers and let 
be the sequence of real numbers given by
Show that, if there exists at least one term among every million consecutive terms of the sequence 
such that 
.
Y by KevinYang2.71, MatejV127, hauy1, L567, GeoKing, AlexCenteno2007, centslordm, trk08, ehuseyinyigit, Gato_combinatorio, eduD_looC, Therealway, JuanOrtiz, axolotlx7, Rounak_iitr, OronSH, mathleticguyyy, ItsBesi, QueenArwen, Yrock, ohiorizzler1434, Scilyse, vinyx, Kingsbane2139, cubres, cursed_tangent1434
Turbo the snail plays a game on a board with 
rows and 
columns. There are hidden monsters in 
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
for which Turbo has a strategy that guarantees reaching the last row on the -th attempt or earlier, regardless of the locations of the monsters.
Proposed by Cheuk Hei Chu, Hong Kong
rows and 
columns. There are hidden monsters in 
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
for which Turbo has a strategy that guarantees reaching the last row on the -th attempt or earlier, regardless of the locations of the monsters.Proposed by Cheuk Hei Chu, Hong Kong
This post has been edited 2 times. Last edited by LLL2019, Jul 17, 2024, 10:40 PM
for any grid size 
when 
.
right away. Then on the next attempt, Turbo must enter the third row in different column as 
right after doing so. This means no strategy can guarantee fewer than three attempts.
![[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]](http://latex.artofproblemsolving.com/9/7/8/97848ad4de848a2abd96a634637821e4e7cb6da2.png)
![[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]](http://latex.artofproblemsolving.com/8/1/9/8193c5f6f49114ba25024eae049a6f694c1a7fb5.png)
![[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]](http://latex.artofproblemsolving.com/d/e/6/de68b1a46cb9e6b4d23d8a96f9e7ac9e67af1a5b.png)
even only in the figures below. We define the happy triangle as the following cells:
cells in the second row.
cells in the third row.
t
,![[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]](http://latex.artofproblemsolving.com/f/0/5/f05d55416a197eba1a37e91c59a7e1e24042b6ff.png)
in the figure), then one can finish in two more moves by considering the two paths from ![[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]](http://latex.artofproblemsolving.com/e/1/d/e1d88fc0189daa5e4405d51b3ebd6ff7878adb7b.png)
![[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]](http://latex.artofproblemsolving.com/c/9/6/c965f51f974deeff9a4ecf910592fe47c545765a.png)
\qquad ![[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]](http://latex.artofproblemsolving.com/0/a/d/0addcd87dc99e4ad5a4424d3ad00bac198f577af.png)
![[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]](http://latex.artofproblemsolving.com/0/8/e/08e9f47d7dd8128a0819ffccd9d9883a8fc8291f.png)
in the figure below in order from top to bottom, until it encounters a second Monster ![[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]](http://latex.artofproblemsolving.com/b/8/8/b883d874477e5875e6421ebf805b7b1d1c3e6d96.png)
,
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 
moves (or even 
.
grid with one monster in every other row.
,
.
in the obvious way.
.
then his next attempt must remain within either row 
and then moves right until 
.
and 
,
and then 
if possible; one of these must have a monster on it; WLOG 
:
,
.
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 
.
.
,
We just ignored the rest of the lesson and and played around with the game - I eventually found the right tweaks to make it a presentable problem (it was still on a 6x6 chessboard at the time) and I thought it was a decent problem but not sophisticated enough for anything like the IMO..
)
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!)
.
(Turbo starts in row 0) and the columns 
.
.
and moves right, scanning the whole first row until he finds the monster. Let the monster be in cell 
.
,
and forward. The only way this could fail is if there is a monster in 
;
so Turbo goes from 
and forward to win on attempt 3.
.
by symmetry. Turbo can now win by attempting the silly zigzag path 
and forward to win. If Turbo encounters a monster while going from 
to 
,
to 
,
,
and forward to win on attempt 3.
.
t
.
because the monster on 
.
with 
is impossible.
,
and win on the next attempt, or learn that row 
through 
to sneak under row 
![[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]](http://latex.artofproblemsolving.com/5/d/8/5d82fcf78fdf13072d0fbb6136e890cbb74c6885.png)
Otherwise, move Turbo in the following "staircase" (mirrored if the monster is on the other side):![[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]](http://latex.artofproblemsolving.com/1/7/8/178efbb12b368805d441706443187da289836ad6.png)
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]
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]](http://latex.artofproblemsolving.com/b/f/8/bf8d0b435a60a2be49a0b7000b37922825d9cd0e.png)
and Turbo wins, as desired.
,![\[
2 \text{ (initial setup)} + \log_2(n) \text{ (halvings)} + 1 \text{ (final check)}.
\]](http://latex.artofproblemsolving.com/c/1/7/c1714da40cab6d4a2201c3f62be3f2cd4eb96a03.png)
For 
,![\[
2 + 11 + 1 = 14.
\]](http://latex.artofproblemsolving.com/8/d/8/8d88c590745deee1d9299f12f5ec4c408ed31bd2.png)
,
grid.
grid.
First of all, it is easy to see that 
WLOG, assume that the monster on the second row is at 
Then Turbo checks the following squares of the 
Suppose that the first monster Turbo encounters through this algorithm is on row 
Then Turbo can determine the locations of the monsters in all previous rows, for each 
with 
the monster on row 
Meanwhile, it is known that the monster on row 
not at column 
Hence, Turbo can simply go to 
and then go straight up, as the monster in column 
is known to be at 
.
