A bagel is a loop of $2 a+2 b+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 \geq 8$, a 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 \geq 8$, we have
$$
\frac{1}{100}<\frac{f(n)}{n^{\alpha}}<100 .
$$
The answer is $\alpha=3 / 2$.
In what follows, " $Y$ is about $X$ " means that $Y=[1+o(1)] X$. Equivalently, $\lim _{n \rightarrow \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.

ๆा 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 horizontal or vertical depending on the orientation of its pair of longer sides. (A square bagel is both.) For each $a<b$ with $2 a+2 b+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.

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=\lceil\sqrt{n / 2}\rceil \quad \text { and } \quad D=\left\{-\ell^{2},-(\ell-1) \ell, \ldots,-3 \ell,-2 \ell,-\ell, 0,1,2, \ldots, \ell\right\} .
$$

Then $|D|$ is about $\sqrt{2 n}$.
We refer to the set $D$ as a ruler in the sense that for any $1 \leq 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 \leq 0$ is a multiple of $\ell$.
Now, if we let $T=\left\{-\ell^{2},-\ell^{2}+1, \ldots, \ell\right\}$ then we may define
$$
S=(D \times T) \cup(T \times D) .
$$

An illustration below is given for $\ell=5$.
Note that $|S|$ is at most about $n|D|$, that is, at most about $\sqrt{2} \cdot n^{3 / 2}$.
Claim - The set $S$ is a bakery of order $n$.

Proof. Let $a$ and $b$ be any positive integers with $2 a+2 b+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 $\left(x_{1}, y_{1}\right)$ and $\left(x_{2}, y_{2}\right)$ has a hole with side lengths $a$ and $b$ and all of its cells are in $S$, as needed.
Remark. Let us call a ruler 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, Ed Pegg Jr, Hitting All The Marks.