Problem: Consider an $n$-by-$n$ board of unit squares for some odd positive integer $n$.
We say that a collection $C$ of identical dominoes is a
maximal grid-aligned configuration on the board if $C$ consists of $(n^2-1)/2$
dominoes where each domino covers exactly two neighboring squares
and the dominoes don't overlap: $C$ then covers all but one square on the board.
We are allowed to slide (but not rotate) a domino on the board to
cover the uncovered square, resulting in a new maximal grid-aligned configuration
with another square uncovered. Let $k(C)$ be the number of distinct maximal
grid-aligned configurations obtainable from $C$ by repeatedly sliding dominoes.

Find the maximum possible value of $k(C)$ as a function of $n$.

Solution: The answer is that
\[ k(C) \le \left( \frac{n+1}{2} \right)^2. \]
\begin{remark*}
  [Comparison with USAMO version]
  In the USAMO version of the problem,
  students instead are asked to find all possible values of $k(C)$.
  The answer is
  $k(C) \in \left\{ 1, 2, \dots, \left( \frac{n-1}{2} \right)^2 \right\}
  \cup \left\{ \left( \frac{n+1}{2} \right)^2 \right\}$.
\end{remark*}

Index the squares by coordinates $(x,y) \in \{1,2,\dots,n\}^2$.
We say a square is \emph{special} if it is empty or
it has the same parity in both coordinates as the empty square.

Construct a directed graph $G = G(C)$ whose vertices are special squares as follows:
for each domino on a special square $s$, we draw a directed edge
from $s$ to the special square that domino points to, if any.
(If the special square has both odd coordinates,
all special squares have an outgoing edge except the empty cell.
In the even-even case, some arrows may point ``off the board''
and not be drawn.)

\begin{center}
\begin{asy}
size(6cm);

pen border = gray+1.5;

filldraw(box((0, 1), (1, 3)), lightgreen, border);
filldraw(box((0, 3), (2, 4)), lightcyan, border);
filldraw(box((0, 4), (2, 5)), lightgreen, border);
filldraw(box((1, 0), (2, 3)), lightred, border);
filldraw(box((1, 2), (3, 3)), lightblue, border);
filldraw(box((2, 3), (3, 5)), palered, border);
filldraw(box((2, 0), (4, 1)), lightcyan, border);
filldraw(box((2, 1), (4, 2)), lightgreen, border);
filldraw(box((4, 0), (5, 2)), lightred, border);
filldraw(box((3, 3), (5, 4)), lightblue, border);
filldraw(box((3, 2), (5, 3)), palered, border);
filldraw(box((3, 4), (5, 5)), lightcyan, border);
filldraw(box((0, 0), (1, 1)), gray, border);

pair A = (0.5, 4.5);
pair B = (2.5, 4.5);
pair C = (4.5, 4.5);
pair D = (0.5, 2.5);
pair E = (2.5, 2.5);
pair F = (4.5, 2.5);
pair X = (0.5, 0.5);
pair Y = (2.5, 0.5);
pair Z = (4.5, 0.5);

dotfactor *= 2;
dot(A); dot(B); dot(C);
dot(D); dot(E); dot(F);
dot(X); dot(Y); dot(Z);

draw(A--B, EndArrow, Margin(3,3));
draw(C--B, EndArrow, Margin(3,3));
draw(B--E, EndArrow, Margin(3,3));
draw(E--D, EndArrow, Margin(3,3));
draw(F--E, EndArrow, Margin(3,3));
draw(Z--F, EndArrow, Margin(3,3));
draw(Y--Z, EndArrow, Margin(3,3));
draw(D--X, EndArrow, Margin(3,3));
\end{asy}
\end{center}

Now focus specifically on the weakly connected component $T$ of $G$
(i.e.\ the connected component of the undirected version of $G$)
containing the empty square.
\begin{claim*}
  The graph $T$ has no cycles, even undirected.
  Hence, the undirected version of $T$ is tree.
\end{claim*}
\begin{proof}
  Assume for contradiction $T$ had an undirected cycle.
  Then if we look at the direction of arrows along the cycle,
  because every vertex of $T$ had outdegree at most $1$,
  the arrows must all point in the same direction
  (i.e.\ we actually have a directed cycle).
  But then $T$ must consist solely of this cycle.
  Yet the empty square has outdegree $0$, contradiction.
\end{proof}

Notice that all the arrows along $T$ point towards the empty cell,
and moving a domino corresponds to flipping an arrow.
Therefore:
\begin{claim*}
  $k(C)$ is exactly the number of vertices of $T$.
\end{claim*}
\begin{proof}
  Starting with the underlying tree,
  the set of possible graphs is described by picking one vertex to be the sink
  (the empty cell) and then directing all arrows towards it.
\end{proof}

This implies that $k(C) \le \left( \frac{n+1}{2} \right)^2$,
the total number of vertices of $G$
(this could only occur if the special squares are odd-odd, not even-even).
Equality is achieved as long as $T$ is a spanning tree;
one example of a way to achieve this is using the snake configuration below.

\begin{center}
\begin{asy}
unitsize(0.9cm);
dotfactor *= 2;
pen border = gray+1.5;
pair A = (0.5, 4.5);
pair B = (2.5, 4.5);
pair C = (4.5, 4.5);
pair D = (0.5, 2.5);
pair E = (2.5, 2.5);
pair F = (4.5, 2.5);
pair X = (0.5, 0.5);
pair Y = (2.5, 0.5);
pair Z = (4.5, 0.5);

filldraw(box((3, 4), (5, 5)), palecyan, border);
filldraw(box((1, 4), (3, 5)), palecyan, border);
filldraw(box((0, 3), (1, 5)), palecyan, border);
filldraw(box((0, 2), (2, 3)), palecyan, border);
filldraw(box((2, 2), (4, 3)), palecyan, border);
filldraw(box((4, 1), (5, 3)), palecyan, border);
filldraw(box((3, 0), (5, 1)), palecyan, border);
filldraw(box((1, 0), (3, 1)), palecyan, border);
fill(unitsquare, mediumgray);
filldraw(box((3, 3), (5, 4)), lightred, border);
filldraw(box((1, 3), (3, 4)), lightred, border);
filldraw(box((0, 1), (2, 2)), lightred, border);
filldraw(box((2, 1), (4, 2)), lightred, border);
dot(A); dot(B); dot(C);
dot(D); dot(E); dot(F);
dot(X); dot(Y); dot(Z);

draw(C--B, EndArrow, Margin(3,3));
draw(B--A, EndArrow, Margin(3,3));
draw(A--D, EndArrow, Margin(3,3));
draw(D--E, EndArrow, Margin(3,3));
draw(E--F, EndArrow, Margin(3,3));
draw(F--Z, EndArrow, Margin(3,3));
draw(Z--Y, EndArrow, Margin(3,3));
draw(Y--X, EndArrow, Margin(3,3));
\end{asy}
\end{center}