\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{CAMO 2020/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 33}
\maketitle
\section*{Problem}
Let $n$ be a positive integer. Eric and a squid play a turn-based game on an infinite grid of unit squares. Eric's goal is to capture the squid by moving onto the same square as it.
Initially, all the squares are colored white. The squid begins on an arbitrary square in the grid, and Eric chooses a different square to start on. On the squid's turn, it performs the following action exactly $2020$ times: it chooses an adjacent unit square that is white, moves onto it, and sprays the previous unit square either black or gray. Once the squid has performed this action $2020$ times, all squares colored gray are automatically colored white again, and the squid's turn ends. If the squid is ever unable to move, then Eric automatically wins. Moreover, the squid is claustrophobic, so at no point in time is it ever surrounded by a closed loop of black or gray squares. On Eric's turn, he performs the following action at most $n$ times: he chooses an adjacent unit square that is white and moves onto it. Note that the squid can trap Eric in a closed region, so that Eric can never win.
Eric wins if he ever occupies the same square as the squid. Suppose the squid has the first turn, and both Eric and the squid play optimally. Both Eric and the squid always know each other's location and the colors of all the squares. Find all positive integers $n$ such that Eric can win in finitely many moves.
\section*{Video}
\href{https://www.youtube.com/watch?v=KqT4kXRA6nA&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/KqT4kXRA6nA}}
\newpage
\section*{Solution}
The answer is $n \ge 4035$.
First, we prove that the squid wins if $n \le 4034$.
For this part, the squid commits to only using gray squares, no black
squares, unless it surrounds Eric.
\begin{claim*}
The squid wins if Eric ever steps within taxicab distance $2014$
from it.
\end{claim*}
\begin{proof}
The squid can run towards Eric and surround Eric in black cells.
\end{proof}
Hence, when the game starts, we may as well assume the distance is at least $2015$.
Now on each of the squid's turns,
the squid can run straight away,
so that at the start of each squid turn, the taxicab distance is at most $4035$.
On each of Eric's turns,
since he cannot catch the squid in one turn,
Eric must maintain a distance of at least $2015$.
This gives a winning strategy for Eric.
Now we claim that squid loses on one turn for $n \ge 4035$.
If the squid starts at $(0,0)$, we have Eric start at $(1007, -1008)$
(this choice doesn't really matter).
Note that:
\begin{itemize}
\ii The squid cannot surround Eric on the first turn.
\ii After squid moves, we highlight in blue every cell which is adjacent
to some black or grey cell.
\ii There are at most $2018 \cdot 2 + 2020 \cdot 5 = 2020 \cdot 2 + 6$ blue cells
generated this way, and the squid is one on such blue cell;
some of these outer blue cells form a loop.
\ii The rightmost lower blue cell is within $2013$ of Eric.
\ii We hence get a bound of $\half (2020 \cdot 2 + 6) + 2013 = 4036$.
\ii If equality holds, then
\begin{itemize}
\ii All the blue cells are used in the loop.
\ii The rightmost lower blue is the same checkerboard color
as the squid starting cell.
\ii In this case, ``farthest'' point on loop is wrong color.
\end{itemize}
So equality cannot hold, and $4035$ does the job.
\end{itemize}
TODO add diagram
\end{document}