\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USEMO 2021/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 90}
\maketitle
\section*{Problem}
A \emph{bagel} is a loop of $2a + 2b + 4$ unit squares which can be
obtained by cutting a concentric $a \times b$ hole
out of an $(a + 2) \times (b + 2)$ rectangle,
for some positive integers $a$ and $b$.
(The side of length $a$ of the hole is parallel to the side of length
$a + 2$ of the rectangle.)
Consider an infinite grid of unit square cells.
For each even integer $n \ge 8$,
a \emph{bakery of order $n$} is a finite set of cells $S$ such that,
for every $n$-cell bagel $B$ in the grid,
there exists a congruent copy of $B$ all of whose cells are in $S$.
(The copy can be translated and rotated.)
We denote by $f(n)$ the smallest possible number of cells
in a bakery of order $n$.
Find a real number $\alpha$ such that,
for all sufficiently large even integers $n \ge 8$, we have
\[ \frac{1}{100} < \frac{f(n)}{n^\alpha} < 100. \]
\section*{Video}
\href{https://youtu.be/PhNIee2CzdY}{\texttt{https://youtu.be/V-9UBJr7aDI}}
\newpage
\section*{Solution}
The answer is $\alpha = 3/2$.
In what follows, ``$Y$ is about $X$'' means that $Y = [1+o(1)]X$.
Equivalently, $\lim_{n \to \infty} Y/X = 1$. Intuitively, both of
these say that $X$ and $Y$ become closer and closer together as $n$
grows. This is fine for the problem since only sufficiently large $n$
are involved.
\paragraph{Bound}
First we prove that every bakery $S$ of order $n$
contains at least about $n^{3/2}/8$ cells.
We say that a bagel is \emph{horizontal} or \emph{vertical}
depending on the orientation of its pair of longer sides. (A square bagel is both.)
For each $a < b$ with $2a + 2b + 4 = n$,
take one bagel in $S$ whose hole is of size either $a \times b$ or $b \times a$.
Without loss of generality, at least about $n/8$ of our bagels are horizontal.
Say that there are a total of $k$ rows which contain a longer side
of at least one of our horizontal bagels.
Note that the shorter side length of a horizontal bagel depends only on
the distance between the rows of its longer sides.
Since the shorter side lengths of all of our bagels are pairwise distinct,
we obtain that $\binom{k}{2}$ is at least about $n/8$.
Consequently, $k$ is at least about $\sqrt{n}/2$.
On the other hand, each such row contains at least about $n/4$ cells in $S$.
Therefore, $|S|$ is at least about $n^{3/2}/8$, as needed.
\paragraph{Construction}
To complete the solution,
we construct a bakery $S$ of order $n$
with at most about $\sqrt{2} \cdot n^{3/2}$ cells.
Define
\[ \ell = \left\lceil \sqrt{n/2} \right\rceil
\qquad\text{and}\qquad
D = \{-\ell^2, -(\ell - 1)\ell, \ldots, -3\ell, -2\ell, -\ell, 0, 1, 2, \ldots, \ell\}. \]
Then $|D|$ is about $\sqrt{2n}$.
We refer to the set $D$ as a \emph{ruler} in the sense
that for any $1 \le m < n/2$,
there are $x_1$ and $x_2$ in $D$ with $x_2 - x_1 = m$.
Indeed, one lets $x_2$ be the remainder when $m$ is divided by $\ell$,
so that $x_1 = x_2 - m \le 0$ is a multiple of $\ell$.
Now, if we let $T = \{-\ell^2, -\ell^2+1, \dots, \ell\}$ then
we may define
\[ S = (D \times T) \cup (T \times D). \]
An illustration below is given for $\ell = 5$.
\begin{center}
\begin{asy}
size(13cm);
void mark(int i) {
for (int j=-25; j<=5; ++j) {
filldraw(shift(i,j)*unitsquare, palecyan, black);
filldraw(shift(j,i)*unitsquare, palecyan, black);
}
}
mark(-25);
mark(-20);
mark(-15);
mark(-10);
mark(-5);
mark(0);
mark(1);
mark(2);
mark(3);
mark(4);
mark(5);
\end{asy}
\end{center}
Note that $|S|$ is at most about $n|D|$,
that is, at most about $\sqrt{2} \cdot n^{3/2}$.
\begin{claim*}
The set $S$ is a bakery of order $n$.
\end{claim*}
\begin{proof}
Let $a$ and $b$ be any positive integers with $2a + 2b + 4 = n$.
By the choice of $D$, there are $x_1$ and $x_2$ in $D$ such that $x_2 - x_1 = a + 1$,
as well as $y_1$ and $y_2$ in $D$ such that $y_2 - y_1 = b + 1$.
Then the bagel with opposite corner cells $(x_1, y_1)$ and $(x_2, y_2)$
has a hole with side lengths $a$ and $b$ and all of its cells are in $S$, as needed.
\end{proof}
\begin{remark*}
Let us call a ruler \emph{sparse} when a lot of its marks are missing
but we can still measure out each one of the distances $1$, $2$, \ldots, $N$.
Then for the set $D$ in the solution essentially we need a sparse ruler
with about $c\sqrt{N}$ marks, for some reasonably small positive real constant $c$.
The construction above is simple but also far from optimal.
Other constructions are known which are more complicated but yield smaller values of $c$.
See, for example, \href{https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/}{Ed Pegg Jr, Hitting All The Marks}.
\end{remark*}
\end{document}