\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/PhNIee2CzdY}}

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

\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, \dots, -3\ell, -2\ell, -\ell, 0, 1, 2, \dots, \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$, \dots, $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}
