\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USAMO 2021/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 65}
\maketitle

\section*{Problem}
Let $n \ge 2$ be an integer.
An $n \times n$ board is initially empty.
Each minute, you may perform one of three moves:
\begin{itemize}
\item If there is an L-shaped tromino region
  of three cells without stones on the board
  (see figure; rotations not allowed),
  you may place a stone in each of those cells.
\begin{center}
\begin{asy}
  size(1.5cm);
  filldraw( (0.1,0.1)--(1.9,0.1)--(1.9,0.9)
    --(0.9,0.9)--(0.9,1.9)--(0.1,1.9)--cycle, rgb(0.7,0.7,0.7), black+2);
  draw( scale(2)*unitsquare, black );
  draw( (1,0)--(1,2), black );
  draw( (0,1)--(2,1), black );
\end{asy}
\end{center}
\item If all cells in a column have a stone, you may remove all stones from that column.
\item If all cells in a row have a stone, you may remove all stones from that row.
\end{itemize}
For which $n$ is it possible that, after some non-zero number of
moves, the board has no stones?

\section*{Video}
\href{https://www.youtube.com/watch?v=9WNgDETHOlI&t=2325}{\texttt{https://youtu.be/9WNgDETHOlI}}

\section*{External Link}
\url{https://aops.com/community/p21498538}

\newpage

\section*{Solution}
The answer is $3 \mid n$.

\medskip

\textbf{Construction}:
For $n=3$, the construction is fairly straightforward,
shown below.
\begin{center}
\begin{asy}
  size(10cm);
  picture g;
  for (int i=0; i<=3; ++i) {
  draw(g, (i-0.5,-0.5)--(i-0.5,2.5), grey);
  draw(g, (-0.5,i-0.5)--(2.5,i-0.5), grey);
  }
  add(g);
  add(shift(4,0)*g);
  add(shift(8,0)*g);
  add(shift(12,0)*g);

  real r = 0.35;
  fill(circle( (0,0), r ), red);
  fill(circle( (1,0), r ), red);
  fill(circle( (0,1), r ), red);
  fill(circle( (1,1), r ), blue);
  fill(circle( (2,1), r ), blue);
  fill(circle( (1,2), r ), blue);

  fill(circle( (4,0), r ), red);
  fill(circle( (4,1), r ), red);
  fill(circle( (6,1), r ), blue);

  fill(circle( (8,0), r ), red);
  fill(circle( (8,1), r ), red);
  fill(circle( (10,1), r ), blue);
  fill(circle( (9,0), r ), deepgreen);
  fill(circle( (9,1), r ), deepgreen);
  fill(circle( (10,0), r ), deepgreen);
\end{asy}
\end{center}
This can be extended to any $3 \mid n$.

\medskip

\textbf{Polynomial-based proof of converse}:
Assume for contradiction $3 \nmid n$.
We will show the task is impossible
even if we allow stones to have real weights in our process.
A valid elimination corresponds to a polynomial $P \in \RR[x,y]$
such that
\begin{align*}
  \deg_x P &\le n-2 \\
  \deg_y P &\le n-2 \\
  (1+x+y) P(x,y)
  &\in \left< 1+x+\dots+x^{n-1}, \; 1+y+\dots+y^{n-1}\right>.
\end{align*}
(Here $\left< \dots\right>$ is an ideal of $\RR[x,y]$.)
In particular, if $S$ is the set of $n$th roots of unity other than $1$,
we should have
\[ (1+z_1+z_2) P\left( z_1, z_2 \right) = 0 \]
for any $z_1 , z_2 \in S$.
Since $3 \nmid n$, it follows that $1+z_1+z_2 \neq 0$ always.

So $P$ vanishes on $S \times S$,
a contradiction to the bounds on $\deg P$
(by, say, combinatorial nullstellensatz on any nonzero term).

\textbf{Linear algebraic proof of converse}
(due to \href{https://aops.com/community/p21499813}{William Wang}):
Suppose there is a valid sequence of moves.
Call $r_j$ the number of operations clearing row $j$,
indexing from bottom-to-top.
The idea behind the solution is that we are going to
calculate, for each cell, the number of times it is operated
on entirely as a function of $r_j$.
For example, a hypothetical illustration with $n=6$ is partially drawn below,
with the number in each cell denoting how many times it was the corner of an $L$.
\[
  \begin{bmatrix}
    0 & 0 & 0 & 0 & 0 & 0 \\
    c_1 & c_2 & {\color{blue}c_3}=r_3 & {\color{blue}c_4}=r_5-r_4 & {\color{blue}c_5}={\color{red}r_5} & 0 \\
    \vdots & \vdots & r_2+r_3-r_5  & r_5-r_3 & {\color{red}r_4} & 0  \\
    \vdots & \vdots & r_1+r_2+r_3-r_4-r_5 & r_5-r_2  & {\color{red}r_3} & 0  \\
    \vdots & \vdots & r_1+r_2+r_4-r_5  & r_5-r_1  & {\color{red}r_2} & 0  \\
    \vdots & \vdots & r_1+r_4-r_5  & r_5  & {\color{red}r_1} & 0  \\
  \end{bmatrix}
\]
Let $a_{i,j}$ be the expression in $(i,j)$.
It will also be helpful to define $c_i$ in the obvious way as well.

\begin{claim*}
  We have $c_n = r_n = 0$, $a_{n-1,j} = r_j$ and $a_{i,n-1} = c_i$.
\end{claim*}
\begin{proof}
  The first statement follows since $(n,n)$ may never obtain a stone.
  The equation $a_{n-1,j} = r_j$ follows as both equal the number of times
  that cell $(n,j)$ obtains a stone.
  The final equation is similar.
\end{proof}

\begin{claim*}
  For $1 \le i,j \le n-1$, the following recursion holds:
  \[ a_{i,j} + a_{i+1,j} + a_{i+1,j-1} = r_j + c_{i+1}. \]
\end{claim*}
\begin{proof}
  Focus on cell $(i+1,j)$.
  The left-hand side counts the number of times that gains a stone
  while the right-hand side counts the number of times it loses a stone;
  they must be equal.
\end{proof}
We can coerce the table above into matrix form now as follows.
Define
\[
  K = \begin{bmatrix}
    -1 & -1 & 0 & 0 & \dots & 0 & 0 & 0 \\
    0 & -1 & -1 & 0 & \dots & 0 & 0 & 0 \\
    0 & 0 & -1 & -1 & \dots & 0 & 0 & 0 \\
    \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
    0 & 0 & 0 & 0 & \dots & -1 & -1 & 0 \\
    0 & 0 & 0 & 0 & \dots & 0 & -1 & -1 \\
    1 & 1 & 1 & 1 & \dots & 1 & 1 & 0 \\
  \end{bmatrix}.
\]
Then define a sequence of matrices $M_i$ recursively by $M_{n-1} = \id$,
and \[ M_i = \id + K M_{i+1} = \id + K + \dots  + K^{n-1-i}. \]
The matrices are chosen so that, by construction,
\[ \left< r_1, \dots, r_{n-1} \right> M_i = \left< a_{i,1}, \dots, a_{i,n-1} \right> \]
for $i=1,2,\dots,n-1$.
On the other hand, we can extend the recursion one level deeper and obtain
\[ \left< r_1, \dots, r_{n-1} \right> M_0 = \left< 0, \dots, 0 \right>. \]
However, the crux of the solution is the following.
\begin{claim*}
  The eigenvalues of $K$ are exactly $-(1+e^{\frac{2\pi i k}{n}})$
  for $k=1,2,\dots,n-1$.
\end{claim*}
\begin{proof}
  The matrix $-(K+\id)$ is fairly known to have roots of unity
  as the coefficients.
\end{proof}
However, we are told that apparently
\[ 0 = \det M_0 = \det\left( \id + K + K^2 + \dots + K^{n-1} \right) \]
which means $\det(K^n - \id) = 0$.
This can only happen if $K^n$ has eigenvalue $1$, meaning that
\[ \left[ -(1+\omega) \right]^n = 1 \]
for $\omega$ some $n$\ts{th} root of unity, not necessarily primitive.
This can only happen if $\left\lvert 1+\omega \right\rvert = 1$, ergo $3 \mid n$.

\end{document}
