% © 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 2021 Solution Notes}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2021 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
Let $n \ge 100$ be an integer.
Ivan writes the numbers $n, n+1, \dots, 2n$ each on different cards.
He then shuffles these $n+1$ cards, and divides them into two piles.
Prove that at least one of the piles contains two cards such that
the sum of their numbers is a perfect square.

\item %% Problem 2
Show that the inequality
\[\sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|}
  \le \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j|} \]
holds for all real numbers $x_1$, $x_2$, \dots, $x_n$.

\item %% Problem 3
Let $D$ be an interior point of the acute triangle $ABC$
with $AB > AC$ so that $\angle DAB = \angle CAD$.
The point $E$ on the segment $AC$ satisfies $\angle ADE =\angle BCD$,
the point $F$ on the segment $AB$ satisfies $\angle FDA =\angle DBC$,
and the point $X$ on the line $AC$ satisfies $CX = BX$.
Let $O_1$ and $O_2$ be the circumcenters of the triangles
$ADC$ and $EXD$, respectively.
Prove that the lines $BC$, $EF$, and $O_1O_2$ are concurrent.

\item %% Problem 4
Let $\Gamma$ be a circle with center $I$, and $ABCD$ a convex quadrilateral
such that each of the segments $AB$, $BC$, $CD$ and $DA$ is tangent to $\Gamma$.
Let $\Omega$ be the circumcircle of the triangle $AIC$.
The extension of $BA$ beyond $A$ meets $\Omega$ at $X$,
and the extension of $BC$ beyond $C$ meets $\Omega$ at $Z$.
The extensions of $AD$ and $CD$ beyond $D$ meet $\Omega$ at $Y$ and $T$, respectively.
Prove that
\[ AD + DT + TX + XA = CD + DY + YZ + ZC. \]

\item %% Problem 5
Two squirrels, Bushy and Jumpy, have collected $2021$ walnuts for the winter.
Jumpy numbers the walnuts from $1$ through $2021$, and digs $2021$ little holes
in a circular pattern in the ground around their favourite tree.
The next morning Jumpy notices that Bushy had placed one walnut into each hole,
but had paid no attention to the numbering.
Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of 2021 moves.
In the $k$th move, Jumpy swaps the positions of the two walnuts adjacent to walnut $k$.

Prove that there exists a value of $k$ such that, on the $k$th move,
Jumpy swaps some walnuts $a$ and $b$ such that $a<k<b$.

\item %% Problem 6
Let $m \ge 2$ be an integer,
$A$ a finite set of integers (not necessarily positive)
and $B_1$, $B_2$, \dots, $B_m$ subsets of $A$.
Suppose that, for every $k=1,2,\dots,m$,
the sum of the elements of $B_k$ is $m^k$.
Prove that $A$ contains at least $\frac{m}{2}$ elements.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{IMO 2021/1, proposed by Australia}
\textsl{Available online at \url{https://aops.com/community/p22698392}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 100$ be an integer.
Ivan writes the numbers $n, n+1, \dots, 2n$ each on different cards.
He then shuffles these $n+1$ cards, and divides them into two piles.
Prove that at least one of the piles contains two cards such that
the sum of their numbers is a perfect square.
\end{mdframed}
We will find three cards $a < b < c$ such that
\begin{align*}
  b+c &= (2k+1)^2 \\
  c+a &= (2k)^2 \\
  a+b &= (2k-1)^2
\end{align*}
for some integer $k$.
Solving for $a$, $b$, $c$ gives
\begin{align*}
  a &= \frac{(2k)^2+(2k-1)^2-(2k+1)^2}{2} = 2k^2 - 4k \\
  b &= \frac{(2k+1)^2+(2k-1)^2-(2k)^2}{2} = 2k^2 + 1 \\
  c &= \frac{(2k+1)^2+(2k)^2-(2k-1)^2}{2} = 2k^2 + 4k
\end{align*}
We need to show that when $n \ge 100$, one can find a suitable $k$.

Let
\begin{align*}
  I_k &\coloneqq \left\{ n \in \ZZ \mid n \le a < b < c \le 2n \right\} \\
  &= \{ n \in \ZZ \mid k^2+2k \le n \le  2k^2-4k \}
\end{align*}
be the interval such that when $n \in I_k$,
the problem dies for that choice of $k$.
It would be sufficient to show these intervals $I_k$
cover all the integers $\ge 100$.
Starting from $I_9 = \left\{ 99 \le n \le 126 \right\}$,
we have
\[ k \ge 9 \implies 2k^2 - 4k \ge (k+1)^2 + 2(k+1) \]
which means the right endpoint of $I_k$
exceeds the left endpoint of $I_{k+1}$.
Hence for $n \ge 99$ in fact the problem is true.

\begin{remark*}
  The problem turns out to be false for $n = 98$, surprisingly.
  The counterexample is for one pile to be
  \[ \{98,100,102,\dots,126\}
    \cup \{129,131,135,\dots,161 \}
    \cup \{162, 164, \dots, 196\}. \]
\end{remark*}
\pagebreak

\subsection{IMO 2021/2, proposed by Calvin Deng}
\textsl{Available online at \url{https://aops.com/community/p22697952}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Show that the inequality
\[\sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|}
  \le \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j|} \]
holds for all real numbers $x_1$, $x_2$, \dots, $x_n$.
\end{mdframed}
The proof is by induction on $n \ge 1$ with the base cases $n=1$ and
$n=2$ being easy to verify by hand.

In the general situation, consider replacing the tuple $(x_i)_i$
with $(x_i+t)_i$ for some parameter $t \in \RR$.
The inequality becomes
\[\sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|}
  \le \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j+2t|}. \]
The left-hand side is independent of $t$.
\begin{claim*}
  The right-hand side, viewed as a function $F(t)$ of $t$,
  is minimized when $2t = -(x_i + x_j)$ for some $i$ and $j$.
\end{claim*}
\begin{proof}
  Since $F(t)$ is the sum of piecewise concave functions,
  it is hence itself piecewise concave.
  Moreover $F$ increases without bound if $|t| \to \infty$.

  On each of the finitely many intervals on which $F(t)$ is
  concave, the function is minimized at its endpoints.
  Hence the minimum value must occur at one of the endpoints.
\end{proof}

If $t = -x_i$ for some $i$, this is the same as shifting all the
variables so that $x_i = 0$.
In that case, we may apply induction on $n-1$ variables,
deleting the variable $x_i$.

If $t = -\frac{x_i+x_j}{2}$, then notice
\[ x_i + t = -(x_j + t) \]
so it's the same as shifting all the variables such that $x_i = -x_j$.
In that case, we may apply induction on $n-2$ variables,
after deleting $x_i$ and $x_j$.
\pagebreak

\subsection{IMO 2021/3, proposed by Mykhalio Shtandenko (UKR)}
\textsl{Available online at \url{https://aops.com/community/p22698068}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $D$ be an interior point of the acute triangle $ABC$
with $AB > AC$ so that $\angle DAB = \angle CAD$.
The point $E$ on the segment $AC$ satisfies $\angle ADE =\angle BCD$,
the point $F$ on the segment $AB$ satisfies $\angle FDA =\angle DBC$,
and the point $X$ on the line $AC$ satisfies $CX = BX$.
Let $O_1$ and $O_2$ be the circumcenters of the triangles
$ADC$ and $EXD$, respectively.
Prove that the lines $BC$, $EF$, and $O_1O_2$ are concurrent.
\end{mdframed}
\emph{This solution was contributed by Abdullahil Kafi}.


\begin{claim*}
    Quadrilateral $BCEF$ is cyclic.
\end{claim*}

\begin{proof}
    Let $D'$ be the isogonal conjugate of the point $D$. The
    angle condition implies quadrilateral $CEDD'$ and $BFDD'$
    are cyclic. By power of point we have \[ AE\cdot AC=AD\cdot AD'=AF\cdot AB \]
    So $BCEF$ is cyclic.
\end{proof}

\begin{claim*}
    Line $ZD$ is tangent to the circles $(BCD)$ and $(DEF)$
    where $Z=EF\cap BC$.
\end{claim*}

\begin{proof}
    Let $\angle CAD=\angle BAD=\alpha$, $\angle BCD=\beta$,
    $\angle DBC=\gamma$, $\angle ACD=\phi$,
    $\angle ABD=\epsilon$.
    From $\triangle ABC$ we have
    $2\alpha+\beta+\gamma+\phi+\epsilon=180^\circ$.
    Let $\ell$ be a line tangent to $(BCD)$ and $K$ be a
    point on it in the same side of $AD$ as $C$ and
    $L=AD\cap BC$. From our labeling we have,
    \begin{align*}
	    \angle AFE &= \beta + \phi \qquad \angle BFD =
	    \alpha + \gamma \qquad \angle DFE = \alpha + \phi
	    \qquad \angle CDL = \alpha + \phi
    \end{align*}
    Now $\angle CDJ = 180^\circ - \gamma - \beta - (\alpha + \phi) = \alpha + \epsilon$.
    So $\angle DFE = \angle EDK = \alpha + \epsilon$, which
    means $\ell$ is also tangent to $(DEF)$. Now by the
    radical center theorem we have $\ell$ passes through
    $Z$.
\end{proof}

Let $M$ be the Miquel point of the cyclic quadrilateral
$BCEF$. From the Miquel configuration we have $A$, $M$, $Z$
are collinear and $(AFEM)$, $(ZCEM)$ are cyclic.

\begin{claim*}
    Points $B$, $X$, $M$, $E$ are cyclic.
\end{claim*}

\begin{proof}
    Notice that $\angle EMB = 180^\circ - \angle AMB -\angle EMZ$
    $=$ $180^\circ - 2\angle ACB = \angle EXB$.
\end{proof}

Let $N$ be the other intersection of circles $(ACD)$ and
$(DEX)$ and let $R$ be the intersection of $AC$ and $BM$.

\begin{center}
\begin{asy}
/*
    Converted from GeoGebra by User:Azjps using Evan's magic cleaner
    https://github.com/vEnhance/dotfiles/blob/main/py-scripts/export-ggb-clean-asy.py
*/
import graph;
size(14cm);
pen ffxfqq = rgb(1.,0.49803,0.);
pen qqwuqq = rgb(0.,0.39215,0.);
pen ffdxqq = rgb(1.,0.84313,0.);
pen qqffff = rgb(0.,1.,1.);
draw((12.,-7.5)--(3.88816,0.36923), linewidth(0.4) + red);
draw((3.88816,0.36923)--(0.5,-7.5), linewidth(0.4) + red);
draw((2.73129,-2.31767)--(4.74594,-3.92841), linewidth(0.4));
draw((4.74594,-3.92841)--(5.47993,-1.17493), linewidth(0.4));
draw(circle((6.25,-6.90419), 5.78078), linewidth(0.4) + red);
draw((6.25,5.85474)--(12.,-7.5), linewidth(0.4));
draw((-9.73375,-7.5)--(5.47993,-1.17493), linewidth(0.4) + red);
draw((-9.73375,-7.5)--(12.,-7.5), linewidth(0.4) + red);
draw((-9.73375,-7.5)--(4.74594,-3.92841), linewidth(0.4));
draw(circle((0.03259,-2.63473), 4.88766), linewidth(0.4) + ffxfqq);
draw(circle((6.84056,0.75675), 5.13208), linewidth(0.4) + qqwuqq);
draw(circle((13.09242,3.87122), 11.42357), linewidth(0.4) + ffxfqq);
draw(circle((6.25,-5.31169), 6.15233), linewidth(0.4) + red);
draw(circle((3.88816,-1.22327), 1.59250), linewidth(0.4) + red);
draw((3.88816,0.36923)--(-9.73375,-7.5), linewidth(0.4));
draw(circle((9.81689,-0.52472), 7.30892), linewidth(0.4) + ffdxqq);
draw((2.50861,-0.42772)--(12.,-7.5), linewidth(0.4));
draw((1.83901,1.90685)--(4.74594,-3.92841), linewidth(0.4));
draw((6.25,5.85474)--(3.88816,0.36923), linewidth(0.4));
draw((0.5,-7.5)--(4.74594,-3.92841), linewidth(0.4));
draw((4.74594,-3.92841)--(12.,-7.5), linewidth(0.4));
draw(shift((-9.73375,-7.5))*xscale(14.91368)*yscale(14.91368)*arc((0,0),1,3.18577,50.41705), linewidth(0.4) + dotted + qqffff);

dot((12.,-7.5),linewidth(3.pt));
label("$B$", (12.47142,-8.47771), NE);
dot((0.5,-7.5),linewidth(3.pt));
label("$C$", (-0.29392,-8.47771), NE);
dot((3.88816,0.36923),linewidth(3.pt));
label("$A$", (3.42645,1.11336), NE);
dot((6.25,5.85474),linewidth(3.pt));
label("$X$", (5.78156,6.47208), NE);
dot((4.74594,-3.92841),linewidth(3.pt));
label("$D$", (4.65520,-5.03038), NE);
dot((5.47993,-1.17493),linewidth(3.pt));
label("$F$", (5.64503,-0.86628), NE);
dot((2.73129,-2.31767),linewidth(3.pt));
label("$E$", (1.58333,-2.43635), NE);
dot((-9.73375,-7.5),linewidth(3.pt));
label("$Z$", (-10.77243,-8.20465), NE);
dot((2.50861,-0.42772),linewidth(3.pt));
label("$M$", (1.20788,-0.21777), NE);
dot((1.83901,1.90685),linewidth(3.pt));
label("$N$", (0.79829,2.47864), NE);
dot((3.29328,-1.01240),linewidth(3.pt));
label("$R$", (3.63125,-1.10520), NE);
\end{asy}
\end{center}

\begin{claim*}
    Points $B$, $D$, $M$, $N$ are cyclic.
\end{claim*}

\begin{proof}
  By power of point we have
  \[
    \opname{Pow}(R, (ACD)) = RC \cdot RA = RM \cdot RB
    = RE \cdot RX = \opname{Pow}(R, (DEX)).
  \]
  Hence $R$ lies on the radical axis of $(ACD)$ and
  $(DEX)$, so $N$, $R$, $D$ are collinear. Also
  \[ RN \cdot RD = RA \cdot RC = RM \cdot RB \] So $BDMN$
  is cyclic.
\end{proof}

Notice that $(ACD)$, $(BDMN)$, $(DEX)$ are coaxial so their
centers are collinear. Now we just need to prove the
centers of $(ACD)$, $(BDMN)$ and $Z$ are collinear. To
prove this, take a circle $\omega$ with radius $ZD$
centered at $Z$. Notice that by power of point
\[ ZC \cdot ZB = ZD^2 = ZE \cdot ZF = ZM \cdot ZA \]
which means inversion circle $\omega$ swaps $(ACD)$ and $(BDMN)$.
So the centers of $(ACD)$ and $(BDMN)$ must
have to be collinear with the center of inversion circle, as desired.
\pagebreak

\section{Solutions to Day 2}
\subsection{IMO 2021/4, proposed by Dominik Burek (POL) and Tomasz Ciesla (POL)}
\textsl{Available online at \url{https://aops.com/community/p22698001}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\Gamma$ be a circle with center $I$, and $ABCD$ a convex quadrilateral
such that each of the segments $AB$, $BC$, $CD$ and $DA$ is tangent to $\Gamma$.
Let $\Omega$ be the circumcircle of the triangle $AIC$.
The extension of $BA$ beyond $A$ meets $\Omega$ at $X$,
and the extension of $BC$ beyond $C$ meets $\Omega$ at $Z$.
The extensions of $AD$ and $CD$ beyond $D$ meet $\Omega$ at $Y$ and $T$, respectively.
Prove that
\[ AD + DT + TX + XA = CD + DY + YZ + ZC. \]
\end{mdframed}
Let $PQRS$ be the contact points of $\Gamma$ an $\ol{AB}$, $\ol{BC}$,
$\ol{CD}$, $\ol{DA}$.

\begin{center}
\begin{asy}
  /*
    Converted from GeoGebra by User:Azjps using Evan's magic cleaner
    https://github.com/vEnhance/dotfiles/blob/main/py-scripts/export-ggb-clean-asy.py
*/
pair I = (0.,0.);
pair P = (-0.40442,0.91457);
pair Q = (-0.35670,-0.93421);
pair R = (0.99998,0.00468);
pair S = (0.70710,0.70710);
pair A = (0.22244,1.19177);
pair B = (-2.62593,-0.06777);
pair C = (1.00681,-1.45484);
pair D = (0.99806,0.41615);
pair X = (2.38106,2.14630);
pair Z = (1.47042,-1.63185);
pair Y = (2.86072,-1.44650);
pair T = (0.99083,1.96044);
pair E = (0.99283,1.53243);
pair F = (4.01929,-2.60507);

size(12.41979cm);
pen qqwuqq = rgb(0.,0.39215,0.);
pen fuqqzz = rgb(0.95686,0.,0.6);
pen zzttqq = rgb(0.6,0.2,0.);
pen cqcqcq = rgb(0.75294,0.75294,0.75294);
draw(P--Q--R--S--cycle, linewidth(0.6) + zzttqq);

draw(circle(I, 1.), linewidth(0.6) + qqwuqq);
draw(circle((1.92609,0.25714), 1.94318), linewidth(0.6) + fuqqzz);
draw(P--Q, linewidth(0.6) + zzttqq);
draw(Q--R, linewidth(0.6) + zzttqq);
draw(R--S, linewidth(0.6) + zzttqq);
draw(S--P, linewidth(0.6) + zzttqq);
draw(circle((0.50340,-0.72742), 0.88462), linewidth(0.6) + fuqqzz);
draw(circumcircle(I,P,S), dotted + fuqqzz);
draw(A--F, linewidth(0.6) + qqwuqq);
draw(B--X, linewidth(0.6) + qqwuqq);
draw(B--F, linewidth(0.6) + qqwuqq);
draw(C--T, linewidth(0.6) + qqwuqq);

dot("$I$", I, dir(160));
dot("$P$", P, dir((-17.392, 6.881)));
dot("$Q$", Q, dir((-17.176, -15.513)));
dot("$R$", R, dir((2.333, 5.318)));
dot("$S$", S, dir((2.248, 5.460)));
dot("$A$", A, dir((-11.357, 7.426)));
dot("$B$", B, dir((-5.839, 9.792)));
dot("$C$", C, dir((2.205, -22.196)));
dot("$D$", D, dir(45));
dot("$X$", X, dir(80));
dot("$Z$", Z, dir((-3.145, -21.676)));
dot("$Y$", Y, dir(90));
dot("$T$", T, dir((-10.053, 11.473)));
dot("$E$", E, dir((10.253, -19.990)));
dot("$F$", F, dir((2.446, 4.708)));
\end{asy}
\end{center}

\begin{claim*}
  We have $\triangle IQZ \cong \triangle IRT$.
  Similarly, $\triangle IPX \cong \triangle ISY$.
\end{claim*}
\begin{proof}
  By considering $(CQIR)$ and $(CITZ)$,
  there is a spiral similarity similarity
  mapping $\triangle IQZ$ to $\triangle IRT$.
  Since $IQ = IR$, it is in fact a congruence.
\end{proof}

This congruence essentially solves the problem.
First, it implies:
\begin{claim*}
  $TX = YZ$.
\end{claim*}
\begin{proof}
  Because we saw $IX = IY$ and $IT = IZ$.
\end{proof}
Then, we can compute
\begin{align*}
  AD + DT + XA
  &= AD + (RT - RD) + (XP-AP) \\
  &= (AD-RD-AP) + RT + XP = RT + XP
\end{align*}
and
\begin{align*}
  CD + DY + ZC &= CD + (SY-SD) + (ZQ-QC) \\
  &= (CD-SD-QC) + SY + ZQ = SY + ZQ
\end{align*}
but $ZQ = RT$ and $XP = SY$, as needed.
\pagebreak

\subsection{IMO 2021/5, proposed by Spain}
\textsl{Available online at \url{https://aops.com/community/p22697921}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Two squirrels, Bushy and Jumpy, have collected $2021$ walnuts for the winter.
Jumpy numbers the walnuts from $1$ through $2021$, and digs $2021$ little holes
in a circular pattern in the ground around their favourite tree.
The next morning Jumpy notices that Bushy had placed one walnut into each hole,
but had paid no attention to the numbering.
Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of 2021 moves.
In the $k$th move, Jumpy swaps the positions of the two walnuts adjacent to walnut $k$.

Prove that there exists a value of $k$ such that, on the $k$th move,
Jumpy swaps some walnuts $a$ and $b$ such that $a<k<b$.
\end{mdframed}
Assume for contradiction no such $k$ exists.
We will use a so-called ``threshold trick''.

This process takes exactly $2021$ steps.
Right after the $k$th move, we consider a situation where
we color walnut $k$ red as well, so at the $k$th step there are $k$ ones.
For brevity, a non-red walnut is called black.
An example is illustrated below with $2021$ replaced by $6$.
\begin{center}
\begin{asy}
  size(14cm);
  dotfactor *= 1.5;
  picture base;
  picture pA, pB, pC, pD, pE, pF, pG;
  pen old = black;
  pen used = mediumred;
  pen active = red;

  draw(pA, unitcircle);
  label(pA, "Initial", origin);
  dot(pA, "$1$", dir(  0), dir(  0), old);
  dot(pA, "$4$", dir( 60), dir( 60), old);
  dot(pA, "$2$", dir(120), dir(120), old);
  dot(pA, "$5$", dir(180), dir(180), old);
  dot(pA, "$3$", dir(240), dir(240), old);
  dot(pA, "$6$", dir(300), dir(300), old);

  draw(pB, unitcircle);
  dot(pB, "$\boxed{1}$", dir(  0), dir(  0), active);
  dot(pB, "$6$", dir( 60), dir( 60), old);
  dot(pB, "$2$", dir(120), dir(120), old);
  dot(pB, "$5$", dir(180), dir(180), old);
  dot(pB, "$3$", dir(240), dir(240), old);
  dot(pB, "$4$", dir(300), dir(300), old);
  draw(pB, dir(60)--dir(300), blue+dotted, Arrows(TeXHead), Margins);

  draw(pC, unitcircle);
  dot(pC, "$1$", dir(  0), dir(  0), used);
  dot(pC, "$5$", dir( 60), dir( 60), old);
  dot(pC, "$\boxed{2}$", dir(120), dir(120), active);
  dot(pC, "$6$", dir(180), dir(180), old);
  dot(pC, "$3$", dir(240), dir(240), old);
  dot(pC, "$4$", dir(300), dir(300), old);
  draw(pC, dir(60)--dir(180), blue+dotted, Arrows(TeXHead), Margins);

  draw(pD, unitcircle);
  dot(pD, "$1$", dir(  0), dir(  0), used);
  dot(pD, "$5$", dir( 60), dir( 60), old);
  dot(pD, "$2$", dir(120), dir(120), used);
  dot(pD, "$4$", dir(180), dir(180), old);
  dot(pD, "$\boxed{3}$", dir(240), dir(240), active);
  dot(pD, "$6$", dir(300), dir(300), old);
  draw(pD, dir(180)--dir(300), blue+dotted, Arrows(TeXHead), Margins);

  draw(pE, unitcircle);
  dot(pE, "$1$", dir(  0), dir(  0), used);
  dot(pE, "$5$", dir( 60), dir( 60), old);
  dot(pE, "$3$", dir(120), dir(120), used);
  dot(pE, "$\boxed{4}$", dir(180), dir(180), active);
  dot(pE, "$2$", dir(240), dir(240), used);
  dot(pE, "$6$", dir(300), dir(300), old);
  draw(pE, dir(120)--dir(240), blue+dotted, Arrows(TeXHead), Margins);

  draw(pF, unitcircle);
  dot(pF, "$1$", dir(  0), dir(  0), used);
  dot(pF, "$\boxed{5}$", dir( 60), dir( 60), active);
  dot(pF, "$3$", dir(120), dir(120), used);
  dot(pF, "$4$", dir(180), dir(180), used);
  dot(pF, "$2$", dir(240), dir(240), used);
  dot(pF, "$6$", dir(300), dir(300), old);
  draw(pF, dir(120)--dir(0), blue+dotted, Arrows(TeXHead), Margins);

  draw(pG, unitcircle);
  dot(pG, "$1$", dir(  0), dir(  0), used);
  dot(pG, "$5$", dir( 60), dir( 60), used);
  dot(pG, "$3$", dir(120), dir(120), used);
  dot(pG, "$4$", dir(180), dir(180), used);
  dot(pG, "$2$", dir(240), dir(240), used);
  dot(pG, "$\boxed{6}$", dir(300), dir(300), active);
  draw(pG, dir(60)--dir(240), blue+dotted, Arrows(TeXHead), Margins);

  add(shift(-3,3)*pA);
  add(shift(0,3)*pB);
  add(shift(3,3)*pC);
  add(shift(6,3)*pD);
  add(shift(0,0)*pE);
  add(shift(3,0)*pF);
  add(shift(6,0)*pG);
\end{asy}
\end{center}

\begin{claim*}
  At each step, the walnut that becomes red is between two non-red or two red walnuts.
\end{claim*}
\begin{proof}
  By definition.
\end{proof}

On the other hand, if there are $2021$ walnuts,
one obtains a parity obstruction to this simplified process:
\begin{claim*}
  After the first step, there is always a consecutive block of black walnuts positive even length.
\end{claim*}
\begin{proof}
  After the first step, there is a block of $2020$ black walnuts.

  Thereafter, note that a length $2$ block of black walnuts can never be changed.
  Meanwhile for even lengths at least $4$, if one places a red walnut inside it,
  the even length block splits into an odd length block and an even length block.
\end{proof}

\begin{remark*}
  The statement is true with $2021$ replaced by any odd number, and false for any even number.

  The motivation comes from the following rephrasing of the problem:
  \begin{quote}
    Start with all $0$'s and at each step change a $0$ between
    two matching numbers from a $0$ to a $1$.
  \end{quote}
  Although the coloring (or $0$/$1$) argument may appear to lose information
  at first, I think it should be \emph{equivalent} to the original process;
  the ``extra'' information comes down to the choice of
  which walnut to color red at each step.
\end{remark*}
\pagebreak

\subsection{IMO 2021/6, proposed by Austria}
\textsl{Available online at \url{https://aops.com/community/p22698082}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $m \ge 2$ be an integer,
$A$ a finite set of integers (not necessarily positive)
and $B_1$, $B_2$, \dots, $B_m$ subsets of $A$.
Suppose that, for every $k=1,2,\dots,m$,
the sum of the elements of $B_k$ is $m^k$.
Prove that $A$ contains at least $\frac{m}{2}$ elements.
\end{mdframed}
If $0 \le X < m^{m+1}$ is a multiple of $m$, then write it in base $m$ as
\[ X = \sum_{i=1}^m c_i m^i \qquad c_i \in \{0,1,2,\dots,m-1\} \]
Then swapping the summation to over $A$ through the $B_i$'s gives
\[ X = \sum_{i = 1}^n \left( \sum_{b \in B_i} b \right) c_i
  = \sum_{a \in A}  f_a(X) a
  \quad\text{where}\quad
  f_a(X) \coloneqq \sum_{i : a \in B_i} c_i.
\]

Evidently, $0 \le f_a(X) \le n(m-1)$ for any $a$ and $X$.
So, setting $|A| = n$, the right-hand side of the display takes on at most
$\left( n(m-1) + 1 \right)^n$ distinct values.
This means
\[ m^m \le \left( n(m-1) \right)^n \]
which implies $n \ge m/2$.

\begin{remark*}
  [Motivation comments from USJL]
  In linear algebra terms,
  we have some $n$-dimensional 0/1 vectors $\vec{v_1}$, \dots, $\vec{v_m}$
  and an $n$-dimensional vector $\vec a$
  such that $\vec{v_i} \cdot \vec a = m^i$ for $i=1, \dots, m$.
  The intuition is that if $n$ is too small,
  then there should be lots of linear dependences between $\vec{v_i}$.

  In fact, \emph{Siegel's lemma} is a result that says,
  if there are many more vectors than the dimension of the ambient space,
  there exist linear dependences whose coefficients are not-too-big integers.
  On the other hand, any linear dependence between $m$, $m^2$, \dots, $m^m$
  is going to have coefficients that are pretty big;
  at least one of them needs to exceed $m$.

  Applying Siegel's lemma turns out to solve the problem
  (and is roughly equivalent to the solution above).
\end{remark*}

\begin{remark*}
  In \url{https://aops.com/community/p23185192},
  \texttt{dgrozev} shows the stronger bound
  $n \ge \left(\frac{2}{3}+\frac{c}{\log m} \right)m$ elements,
  for some absolute constant $c > 0$.
\end{remark*}
\pagebreak


\end{document}
