% © Evan Chen
% Downloaded from https://web.evanchen.cc/
\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\href{http://web.evanchen.cc}{\ttfamily web.evanchen.cc},
updated \today}
\title{IMO 2024 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2024 IMO.
The ideas of the solution are a mix of my own work,
the solutions provided by the competition organizers,
and solutions found by the community.
However, all the writing is maintained by me.
These notes will tend to be a bit more advanced and terse than the ``official''
solutions from the organizers.
In particular, if a theorem or technique is not known to beginners
but is still considered ``standard'', then I often prefer to
use this theory anyways, rather than try to work around or conceal it.
For example, in geometry problems I typically use directed angles
without further comment, rather than awkwardly work around configuration issues.
Similarly, sentences like ``let $\mathbb{R}$ denote the set of real numbers''
are typically omitted entirely.
Corrections and comments are welcome!
\end{abstract}
\tableofcontents
\newpage
\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
Find all real numbers $\alpha$ so that, for every positive integer $n$, the integer
\[ \left\lfloor \alpha \right\rfloor + \left\lfloor 2 \alpha \right\rfloor
+ \left\lfloor 3 \alpha \right\rfloor + \dots + \left\lfloor n \alpha \right\rfloor \]
is divisible by $n$.
\item %% Problem 2
For which pairs of positive integers $(a,b)$ is the sequence
\[ \gcd(a^n+b, b^n+a) \qquad n = 1, 2, \dotsc \]
eventually constant?
\item %% Problem 3
Let $a_1$, $a_2$, $a_3$, \dots\ be an infinite sequence of positive integers,
and let $N$ be a positive integer.
Suppose that, for each $n > N$,
the number $a_n$ is equal to the number of times $a_{n-1}$ appears
in the list $(a_1, a_2, \dots, a_{n-1})$.
Prove that at least one of the sequences $a_1$, $a_3$, $a_5$, \dots\
and $a_2$, $a_4$, $a_6$, \dots\ is eventually periodic.
\item %% Problem 4
Let triangle $ABC$ with incenter $I$ satisfying $AB < AC < BC$.
Let $X$ be a point on line $BC$, different from $C$,
such that the line through $X$ and parallel to $AC$ is tangent to the incircle.
Similarly, let $Y$ be a point on line $BC$, different from $B$,
such that the line through $Y$ and parallel to $AB$ is tangent to the incircle.
Line $AI$ intersects the circumcircle of triangle $ABC$ again at $P$.
Let $K$ and $L$ be the midpoints of $AC$ and $AB$, respectively.
Prove that $\angle KIL + \angle YPX = 180^{\circ}$.
\item %% Problem 5
Turbo the snail is in the top row of a grid with $2024$ rows and $2023$ columns
and wants to get to the bottom row.
However, there are $2022$ hidden monsters, one in every row except the first and last,
with no two monsters in the same column.
Turbo makes a series of attempts to go from the first row to the last row.
On each attempt, he chooses to start on any cell in the first row,
then repeatedly moves to an orthogonal neighbor.
(He is allowed to return to a previously visited cell.)
If Turbo reaches a cell with a monster,
his attempt ends and he is transported back to the first row to start a new attempt.
The monsters do not move between attempts, and Turbo remembers whether or not each cell
he has visited contains a monster.
If he reaches any cell in the last row, his attempt ends and Turbo wins.
Find the smallest integer $n$ such that Turbo has a strategy which guarantees
being able to reach the bottom row in at most $n$ attempts,
regardless of how the monsters are placed.
\item %% Problem 6
A function $f \colon \QQ \to \QQ$ is called \emph{aquaesulian}
if the following property holds: for every $x,y \in \mathbb{Q}$,
\[ f(x+f(y)) = f(x) + y \quad \text{or} \quad f(f(x)+y) = x + f(y). \]
Show that there exists an integer $c$ such that for any aquaesulian function $f$
there are at most $c$ different rational numbers of the
form $f(r) + f(-r)$ for some rational number $r$,
and find the smallest possible value of $c$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{IMO 2024/1, proposed by Santiago Rodriguez (COL)}
\textsl{Available online at \url{https://aops.com/community/p31205921}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all real numbers $\alpha$ so that, for every positive integer $n$, the integer
\[ \left\lfloor \alpha \right\rfloor + \left\lfloor 2 \alpha \right\rfloor
+ \left\lfloor 3 \alpha \right\rfloor + \dots + \left\lfloor n \alpha \right\rfloor \]
is divisible by $n$.
\end{mdframed}
The answer is that $\alpha$ must be an even integer.
Let $S(n, \alpha)$ denote the sum in question.
\paragraph{Analysis for $\alpha$ an integer.}
If $\alpha$ is an integer, then the sum equals
\[ S(n, \alpha) = (1+2+\dots+n) \alpha = \frac{n(n+1)}{2} \cdot \alpha \]
which is obviously a multiple of $n$ if $2 \mid \alpha$;
meanwhile, if $\alpha$ is an odd integer then $n = 2$ gives a counterexample.
\paragraph{Main case.}
Suppose $\alpha$ is not an integer; we show the desired condition can never be true.
Note that replacing $\alpha$ with $\alpha \pm 2$ changes by
\[ S(n \pm 2, \alpha) - S(n, \alpha) = 2(1+2+\dots+n) = n(n+1) \equiv 0 \pmod n \]
for every $n$.
Thus, by shifting appropriately we may assume $-1 < \alpha < 1$ and $\alpha \notin \ZZ$.
\begin{itemize}
\ii If $0 < \alpha < 1$,
then let $m \ge 2$ be the smallest integer such that $m \alpha \ge 1$.
Then
\[ S(m, \alpha) = \underbrace{0 + \dots + 0}_{m-1\text{ terms}} + 1 = 1 \]
is not a multiple of $m$.
\ii If $-1 < \alpha < 0$,
then let $m \ge 2$ be the smallest integer such that $m \alpha \le -1$.
Then
\[ S(m, \alpha) = \underbrace{(-1) + \dots + (-1)}_{m-1\text{ terms}} + 0 = -(m-1) \]
is not a multiple of $m$.
\end{itemize}
\pagebreak
\subsection{IMO 2024/2, proposed by Valentino Iverson (IDN)}
\textsl{Available online at \url{https://aops.com/community/p31205957}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
For which pairs of positive integers $(a,b)$ is the sequence
\[ \gcd(a^n+b, b^n+a) \qquad n = 1, 2, \dotsc \]
eventually constant?
\end{mdframed}
The answer is $(a,b)=(1,1)$ only, which obviously works since the sequence is always $2$.
Conversely, assume the sequence
\[ x_n \coloneqq \gcd(a^n+b, b^n+a) \] is eventually constant.
The main crux of the other direction is to consider
\[ M \coloneqq ab+1. \]
\begin{remark*}
[Motivation]
The reason to consider the number is the same technique used in IMO 2005/4,
namely the idea to consider ``$n = -1$''.
The point is that the two rational numbers
\[ \frac 1a + b = \frac{ab+1}{b}, \qquad \frac 1b + a = \frac{ab+1}{a} \]
have a large common factor: we could write ``$x_{-1} = ab + 1$'', loosely speaking.
Now, the sequence is really only defined for $n \ge 1$,
so one should instead take $n \equiv -1 \pmod{\varphi(M)}$
--- and this is exactly what we do.
\end{remark*}
Obviously $\gcd(a,M) = \gcd(b,M) = 1$.
Let $n$ be a sufficiently large multiple of $\varphi(M)$
so that \[ x_{n-1} = x_n = x_{n+1} = \dotsb. \]
We consider the first three terms;
the first one is the ``key'' one that gets the bulk of the work,
and the rest is bookkeeping and extraction.
\begin{itemize}
\ii Consider $x_{n-1}$.
Note that
\[ a (a^{n-1} + b) = a^n + ab \equiv 1 + (-1) \equiv 0 \pmod M \]
and similarly $b (b^n + a) \equiv 0 \pmod M$.
Hence $M \mid x_{n-1}$.
\ii Consider $x_n$, which is now known to be divisible by $M$. Note that
\begin{align*}
0 &\equiv a^n + b \equiv 1 + b \pmod M \\
0 &\equiv b^n + a \equiv 1 + a \pmod M.
\end{align*}
So $a \equiv b \equiv -1 \pmod M$.
\ii Consider $x_{n+1}$, which is now known to be divisible by $M$. Note that
\[ 0 \equiv a^{n+1} + b \equiv b^{n+1} + a \equiv a + b \pmod M. \]
We knew $a \equiv b \equiv -1 \pmod M$,
hence this means $0 \equiv 2 \pmod M$, so $M = 2$.
\end{itemize}
From $M = 2$ we then conclude $a = b = 1$, as desired.
\begin{remark*}
[No alternate solutions known]
At the time nobody seems to know any solution not depending critically
on $M = ab+1$ (or prime numbers dividing $M$, etc.).
They vary in execution once some term of the form $x_{k\varphi(n)-1}$ is taken,
but avoiding the key idea altogether does not currently seem possible.
A good example to consider for ruling out candidate ideas is $(a,b) = (18,9)$.
\end{remark*}
\pagebreak
\subsection{IMO 2024/3, proposed by William Steinberg (AUS)}
\textsl{Available online at \url{https://aops.com/community/p31206050}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $a_1$, $a_2$, $a_3$, \dots\ be an infinite sequence of positive integers,
and let $N$ be a positive integer.
Suppose that, for each $n > N$,
the number $a_n$ is equal to the number of times $a_{n-1}$ appears
in the list $(a_1, a_2, \dots, a_{n-1})$.
Prove that at least one of the sequences $a_1$, $a_3$, $a_5$, \dots\
and $a_2$, $a_4$, $a_6$, \dots\ is eventually periodic.
\end{mdframed}
We present the solution from ``gigamilkmen'tgeg''
in \url{https://aops.com/community/p31224483},
with some adaptation from the first shortlist official solution as well.
Set $M \coloneqq \max(a_1, \dots, a_N)$.
\paragraph{Setup.}
We will visualize the entire process as follows.
We draw a stack of towers labeled $1$, $2$, \dots, each initially empty.
For $i=1,2,\dots$, we imagine the term $a_i$ as adding a block $B_i$ to tower $a_i$.
Then there are $N$ initial blocks placed, colored \emph{red}.
The rest of the blocks are colored \emph{yellow}:
if the last block $B_i$ was added to a tower that then reaches height $a_{i+1}$,
the next block $B_{i+1}$ is added to tower $a_{i+1}$.
We'll say $B_i$ \emph{contributes} to the tower containing $B_{i+1}$.
In other words, the yellow blocks $B_i$ for $i > N$
are given coordinates $B_i = (a_i, a_{i+1})$ for $i>N$.
Note in particular that in towers $M+1$, $M+2$, \dots, the blocks are all yellow.
\begin{center}
\begin{asy}
unitsize(0.85cm);
int[] a = {1,2,2,2,2,2,3,4,1,2,6,1,3,2,7,1,4,2,8,1,5,1,6,2,9,1,7,2,10};
int N = 8;
filldraw(shift(0,0)*unitsquare, palered, black+1);
filldraw(shift(1,0)*unitsquare, palered, black+1);
filldraw(shift(2,0)*unitsquare, palered, black+1);
filldraw(shift(3,0)*unitsquare, palered, black+1);
filldraw(shift(1,1)*unitsquare, palered, black+1);
filldraw(shift(1,2)*unitsquare, palered, black+1);
filldraw(shift(1,3)*unitsquare, palered, black+1);
filldraw(shift(1,4)*unitsquare, palered, black+1);
for (int i=N; i M$ then $a_{n+1} \le M$.
\end{claim*}
\begin{proof}
Assume for contradiction there's a first moment where $a_n > M$ and $a_{n+1} > M$,
meaning the block $B_n$ was added to an all-yellow tower past $M$
that has height exceeding $M$.
(This is the X'ed out region in the figure above.)
In $B_n$'s tower, every (yellow) block (including $B_n$)
was contributed by a block placed in different towers at height $a_n > M$.
So before $B_n$, there were already $a_{n+1} > M$ towers of height more than $M$.
This contradicts minimality of $n$.
\end{proof}
It follows that the set of indices with $a_n \le M$
has arithmetic density at least half, so certainly
at least some of the numbers must occur infinitely often.
Of the numbers in $\{1,2,\dots,M\}$,
define $L$ such that towers $1$ through $L$ grow unbounded
but towers $L+1$ through $M$ do not.
Then we can pick a larger threshold $N' > N$ such that
\begin{itemize}
\ii Towers $1$ through $L$ have height greater than $(M,N)$;
\ii Towers $L+1$ through $M$ will receive no further blocks;
\ii $a_{N'} \le L$.
\end{itemize}
After this threshold, the following statement is true:
\begin{claim*}
[Alternating small and big]
The terms $a_{N'}$, $a_{N' + 2}$, $a_{N' + 4}$, \dots\ are all at most $L$ while
the terms $a_{N' + 1}$, $a_{N' + 3}$, $a_{N' + 5}$, \dots\ are all greater than $M$.
\end{claim*}
\paragraph{Automaton for $n \equiv N' \pmod 2$.}
From now on we always assume $n > N'$.
When $n \equiv N' \pmod 2$, i.e., when $a_n$ is small, we define the state
\[ S(n) = (h_1, h_2, \dots, h_L; a_n). \]
For example, in the figure below, we illustrate how
\[ S(34) = (9,11;a_{34}=1) \longrightarrow S(36) = (9,12;a_{36}=2) \]
\begin{center}
\begin{asy}
unitsize(0.85cm);
int[] a = {1,2,2,2,2,2,3,4,1,2,6,1,3,2,7,1,4,2,8,1,5,1,6,2,9,1,7,2,10,1,8,2,11,1,9,2,12};
int N = 8;
filldraw(shift(0,0)*unitsquare, palered, black+1);
filldraw(shift(1,0)*unitsquare, palered, black+1);
filldraw(shift(2,0)*unitsquare, palered, black+1);
filldraw(shift(3,0)*unitsquare, palered, black+1);
filldraw(shift(1,1)*unitsquare, palered, black+1);
filldraw(shift(1,2)*unitsquare, palered, black+1);
filldraw(shift(1,3)*unitsquare, palered, black+1);
filldraw(shift(1,4)*unitsquare, palered, black+1);
for (int i=N; i N'$,
we have $h_\ell \le h_{\ell+1} + C \cdot (L-1)$.
\end{claim*}
\begin{proof}
Assume for contradiction that there is some moment $n > N'$ such that
\[ h_\ell > h_{\ell+1} + C \cdot (L-1) \]
and WLOG assume that $h_\ell$ was just updated at the moment $n$.
Together with $h_{k+1} \le h_k + C$ for all $k$ and triangle inequality, we conclude
\[ \min(h_1, \dots, h_\ell) > q \coloneqq \max(h_{\ell+1}, \dots, h_L). \]
We find that the blocks now in fact alternate between being placed
among the first $\ell$ towers and in towers with indices greater than $q$ thereafter.
Hence the heights $h_{\ell+1}$, \dots, $h_L$ never grow after this moment.
This contradicts the definition of $L$.
\end{proof}
\begin{remark*}
In fact, it can be shown that the period is actually exactly $L$,
meaning the periodic part will be exactly a permutation of $(1,2,\dots,L)$.
For any $L$, it turns out there is indeed a permutation achieving that periodic part.
\end{remark*}
\pagebreak
\section{Solutions to Day 2}
\subsection{IMO 2024/4, proposed by Dominik Burek (POL)}
\textsl{Available online at \url{https://aops.com/community/p31218657}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let triangle $ABC$ with incenter $I$ satisfying $AB < AC < BC$.
Let $X$ be a point on line $BC$, different from $C$,
such that the line through $X$ and parallel to $AC$ is tangent to the incircle.
Similarly, let $Y$ be a point on line $BC$, different from $B$,
such that the line through $Y$ and parallel to $AB$ is tangent to the incircle.
Line $AI$ intersects the circumcircle of triangle $ABC$ again at $P$.
Let $K$ and $L$ be the midpoints of $AC$ and $AB$, respectively.
Prove that $\angle KIL + \angle YPX = 180^{\circ}$.
\end{mdframed}
Let $T$ be the reflection of $A$ over $I$, the most important point to add
since it gets rid of $K$ and $L$ as follows.
\begin{claim*}
We have $\angle KIL = \angle BTC$,
and lines $TX$ and $TY$ are tangent to the incircle.
\end{claim*}
\begin{proof}
The first part is true since $\triangle BTC$ is the image of $\triangle KIL$
under a homothety of ratio $2$.
The second part is true because lines $AB$, $AC$, $TX$, $TY$
determine a rhombus with center $I$.
\end{proof}
We thus delete $K$ and $L$ from the picture altogether; they aren't needed anymore.
\begin{center}
\begin{asy}
size(11cm);
pair A = dir(105);
pair B = dir(200);
pair C = dir(340);
pair P = dir(270);
filldraw(unitcircle, opacity(0.1)+lightcyan, blue);
pair I = incenter(A, B, C);
filldraw(incircle(A, B, C), opacity(0.1)+lightcyan, blue);
draw(A--B--C--cycle, blue);
pair E = foot(I, C, A);
pair F = foot(I, A, B);
pair T = 2*I-A;
pair U = 2*I-E;
pair V = 2*I-F;
draw(U--T--V, deepgreen);
draw(B--T--C, red);
pair K = midpoint(A--B);
pair L = midpoint(A--C);
draw(K--I--L, red+dashed);
pair X = extension(U, T, B, C);
pair Y = extension(V, T, B, C);
draw(A--P, grey);
draw(circumcircle(B, X, P), grey+dashed);
draw(circumcircle(C, Y, P), grey+dashed);
dot("$A$", A, dir(A));
dot("$B$", B, dir(160));
dot("$C$", C, dir(20));
dot("$P$", P, dir(45));
dot("$I$", I, dir(250));
dot("$T$", T, dir(225));
dot("$K$", K, dir(K));
dot("$L$", L, dir(L));
dot("$X$", X, dir(X));
dot("$Y$", Y, dir(310));
/* -----------------------------------------------------------------+
| TSQX: by CJ Quines and Evan Chen |
| https://github.com/vEnhance/dotfiles/blob/main/py-scripts/tsqx.py |
+-------------------------------------------------------------------+
!size(11cm);
A = dir 105
B 160 = dir 200
C 20 = dir 340
P 45 = dir 270
unitcircle / 0.1 lightcyan / blue
I 250 = incenter A B C
incircle A B C / 0.1 lightcyan / blue
A--B--C--cycle / blue
E := foot I C A
F := foot I A B
T 225 = 2*I-A
U := 2*I-E
V := 2*I-F
U--T--V / deepgreen
B--T--C / red
K = midpoint A--B
L = midpoint A--C
K--I--L / red dashed
X = extension U T B C
Y 310 = extension V T B C
A--P / grey
circumcircle B X P / grey dashed
circumcircle C Y P / grey dashed
*/
\end{asy}
\end{center}
\begin{claim*}
We have $BXPT$ and $CYPT$ are cyclic.
\end{claim*}
\begin{proof}
$\dang TYC = \dang TYB = \dang ABC = \dang APC = \dang TPC$ and similarly.
(Some people call this Reim's theorem.)
\end{proof}
To finish, observe that
\[ \dang CTB = \dang CTP + \dang PTB = \dang CYP + \dang PXB
= \dang XYP + \dang XYP = \dang XPY \]
as desired.
(The length conditions $AC > AB > BC$ ensure that $B$, $X$, $Y$, $C$ are collinear
in that order, and that $T$ lies on the opposite side of $\ol{BC}$ as $A$.
Hence the directed equality $\dang CTB = \dang XPY$
translates to the undirected $\angle BTC + \angle XPY = 180\dg$.)
\pagebreak
\subsection{IMO 2024/5, proposed by Chu Cheuk Hei (HKG)}
\textsl{Available online at \url{https://aops.com/community/p31218774}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Turbo the snail is in the top row of a grid with $2024$ rows and $2023$ columns
and wants to get to the bottom row.
However, there are $2022$ hidden monsters, one in every row except the first and last,
with no two monsters in the same column.
Turbo makes a series of attempts to go from the first row to the last row.
On each attempt, he chooses to start on any cell in the first row,
then repeatedly moves to an orthogonal neighbor.
(He is allowed to return to a previously visited cell.)
If Turbo reaches a cell with a monster,
his attempt ends and he is transported back to the first row to start a new attempt.
The monsters do not move between attempts, and Turbo remembers whether or not each cell
he has visited contains a monster.
If he reaches any cell in the last row, his attempt ends and Turbo wins.
Find the smallest integer $n$ such that Turbo has a strategy which guarantees
being able to reach the bottom row in at most $n$ attempts,
regardless of how the monsters are placed.
\end{mdframed}
Surprisingly the answer is $n = 3$ for \emph{any} grid size $s \times (s-1)$ when $s \ge 4$.
We prove this in that generality.
\paragraph{Proof that at least three attempts are needed.}
When Turbo first moves into the second row, Turbo could encounter 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.
\paragraph{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.
\subparagraph{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.
\begin{center}
\begin{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));
\end{asy}
\end{center}
\subparagraph{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 left 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 center and right figure
(there are two slightly different cases depending on whether $M_2$
was encountered going east or south).
\begin{center}
\begin{asy}
usepackage("amssymb");
unitsize(0.65cm);
pen gr = grey+linetype("4 2");
int n = 6;
dotfactor *= 2;
picture pic1, pic2, pic3;
picture[] pics = {pic1, pic2, pic3};
for (int j=0; j<3; ++j) {
for (int i=0; i<=n-1; ++i) {
draw(pics[j], (0,i)--(n,i), gr);
}
for (int i=0; i<=n; ++i) {
draw(pics[j], (i,0)--(i,n-1), gr);
}
draw(pics[j], box((0,-1), (n,0)), black);
draw(pics[j], box((0,n-1), (n,n)), black);
draw(pics[j], box((0,-1), (n,n)), black);
label(pics[j], "Starting row", (n/2,n-0.5));
label(pics[j], "Goal row", (n/2,-0.5));
}
label(pic1, "$M_1$", (0.5,4.5), red);
dot(pic1, (1.5,4.5), deepgreen);
draw(pic1, (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));
label(pic2, "$M_1$", (0.5,4.5), red);
label(pic2, "$M_2$", (4.5,2.5), red);
dot(pic2, (1.5,4.5), deepgreen);
draw(pic2, (3.5,2.5)--(4.5,2.5)--(4.5,1.5)--(5.5,1.5)--(5.5,0.2), deepgreen+dashed);
draw(pic2, (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));
label(pic3, "$M_1$", (0.5,4.5), red);
label(pic3, "$M_2$", (4.5,1.5), red);
dot(pic3, (1.5,4.5), deepgreen);
draw(pic3, (3.5,2.5)--(4.5,2.5)--(4.5,1.5)--(5.5,1.5)--(5.5,0.2), deepgreen+dashed);
draw(pic3, (1.5,4.5)--(2.5,4.5)--(2.5,3.5)--(3.5,3.5)--(3.5,1.5)--(0.5,1.5)--(0.5,0.2),
purple+1.5, EndArrow(TeXHead));
add(pic1);
add(shift(7,0)*pic2);
add(shift(14,0)*pic3);
\end{asy}
\end{center}
Thus the problem is solved in three attempts, as promised.
\paragraph{Extended remark: all working strategies look similar to this.}
As far as we know, all working strategies are variations of the above.
In fact, we will try to give a description of the space of possible strategies,
although this needs a bit of notation.
\begin{definition*}
For simplicity, we use $s$ even only in the figures below.
We define the \emph{happy triangle} as the following cells:
\begin{itemize}
\item All $s-1$ cells in the first row (which has no monsters).
\item The center $s-3$ cells in the second row.
\item The center $s-5$ cells in the third row.
\item \dots
\item The center cell in the $\frac s2$\textsuperscript{th} row.
\end{itemize}
\end{definition*}
For $s=12$, the happy triangle is the region shaded in the thick border below.
\begin{center}
\begin{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