\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USEMO 2019/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 10}
\maketitle
\section*{Problem}
Consider an infinite grid $\mathcal G$ of unit square cells.
A \emph{chessboard polygon} is a simple polygon
(i.e.\ not self-intersecting)
whose sides lie along the gridlines of $\mathcal G$.
Nikolai chooses a chessboard polygon $F$
and challenges you to paint some cells of $\mathcal G$ green,
such that any chessboard polygon congruent to $F$
has at least $1$ green cell but at most $2020$ green cells.
Can Nikolai choose $F$ to make your job impossible?
\section*{Video}
\href{https://www.youtube.com/watch?v=V2TNgUwbs6A&list=PLi6h8GM1FA6yfhMMNqJi1mht4KmZnXpj6}{\texttt{https://youtu.be/V2TNgUwbs6A}}
\newpage
\section*{Solution}
The answer is YES, the task can be made impossible.
The solution is split into three parts.
First, we describe a ``polygon with holes'' $F$.
In the second part we prove that this $F$ works.
Finally, we show how to take care of the holes to obtain a true polygon.
\textbf{Part 1. Construction.}
Choose large integers $m \ge 5$, $n \ge 1$ with $m$ odd.
We will let \[ s = m^n \] throughout the solution.
Let $F_0$ be a square of side length $s$.
Starting from $F_0$,
iterate the following procedure.
Divide $F_i$ into squares of side $s / m^{i}$
and poke a square hole of side $3s / m^{i+1}$
(a \emph{phase-$i$} hole)
in the center of each such square to obtain $F_{i + 1}$.
Finally, let $F = F_n$.
The output is shown below for $m = 11$ and $n = 3$.
The claim is that for a suitable choice of $(m,n)$
this will serve as the desired example.
\begin{center}
\begin{asy}
size(11cm);
int m = 11;
int s =3;
int k = (m-s)#2;
filldraw(scale(m^3)*unitsquare, palecyan, blue+1.2);
for (int i=0; i 2020$.
\bigskip
\textbf{Part 3. Handling the holes.}
We are left to show how to repair the
above construction so that $F$ becomes a true polygon.
Let $D$ be any sufficiently large positive integer.
Consider a homothetic copy $F_D$ of $F$ scaled by a factor of $D$.
Cut several canals of unit width into $F_D$ so that $F_D$ continues
to be connected and every hole in $F_D$ is
joined by a canal to the boundary of $F_D$.
(Canals do not need to be straight; they may go around holes.)
When $F_D$ is repaired in this way,
it becomes a true polygon $F'_D$.
Since the total area of all canals is proportional to $D$
and the total area of $F_D$ is proportional to $D^2$,
when $D$ becomes arbitrarily large the ratio of the area of $F'_D$
to the area of $F_D$ becomes arbitrarily close to one.
Therefore, for all sufficiently large $D$ our proof
that $F$ is in fact a counterexample goes through for $F'_D$ as well,
with straightforward adjustments.
The solution is complete.
\begin{remark*}
[Author comments]
Some time after I came up with
this problem, Ilya Bogdanov pointed out to me that it is similar to
problem 3.6 in Ilya Bogdanov and Grigory Chelnokov, Pokritiya
Kletchatimi Figurkami, Summer Conference of the Tournament of Towns,
2007, \url{https://www.turgor.ru/lktg/2007/3/index.php}.
The USEMO directors agreed that the two problems are different enough
that mine was suitable for the contest.
\end{remark*}
\end{document}