2023 USAJMO Problems/Problem 3

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 value of $k(C)$ as a function of $n$ .

Solution

To start off, we put the initial non-covered square in a corner (marked by the shaded square). Let's consider what happens when our first domino slides over the empty square. We will call such a move where we slide a domino over the uncovered square a "step":

$[asy] size(5cm); draw((0,0)--(0,3.2)); draw((1,0)--(1,3.2)); draw((0,0)--(1.2,0)); draw((0,1)--(1.2,1)); draw((0,2)--(1.2,2)); draw((0,3)--(1.2,3)); fill(origin--(1,0)--(1,1)--(0,1)--cycle, grey); draw((0.1,1.1)--(0.1,2.9)--(0.9,2.9)--(0.9,1.1)--cycle,dashed); draw((0.1,0.1)--(0.1,1.9)--(0.9,1.9)--(0.9,0.1)--cycle); [/asy]$

When the vertically-oriented domino above the shaded square moved down to cover the shaded square, it had uncovered a new square two squares above the original one. Next, we consider the second another direction the uncovered square can move to:

$[asy] size(5cm); draw((0,0)--(0,3.2)); draw((1,0)--(1,3.2)); draw((0,0)--(1.2,0)); draw((0,1)--(1.2,1)); draw((0,2)--(1.2,2)); draw((0,3)--(1.2,3)); fill((0,2)--(1,2)--(1,3)--(0,3)--cycle, grey); draw((0.1,2.9)--(0.1,2.1)--(1.9,2.1)--(1.9,2.9)--cycle); draw((1.1,2.9)--(1.1,2.1)--(2.9,2.1)--(2.9,2.9)--cycle,dashed); draw((0.1,0.1)--(0.1,1.9)--(0.9,1.9)--(0.9,0.1)--cycle); [/asy]$

In this case, the horizontally-oriented domino besides the shaded square moved to cover the previous shaded square. The new uncovered square, as a result, would be either two squares to the left, or to the right of the previous shaded square.

So, to summarize, during each "move", the uncovered square can move either two steps up, down, left, or right. We can make a path for which the shaded square takes:

$[asy] size(5cm); draw((0,0)--(0,5)); draw((1,0)--(1,5)); draw((2,0)--(2,5)); draw((3,0)--(3,5)); draw((4,0)--(4,5)); draw((5,0)--(5,5)); draw((0,0)--(5,0)); draw((0,1)--(5,1)); draw((0,2)--(5,2)); draw((0,3)--(5,3)); draw((0,4)--(5,4)); draw((0,5)--(5,5)); draw((0.5,0.5)--(0.5,2.5)--(2.5,2.5)--(2.5,0.5)--(4.5,0.5)--(4.5,2.5)--(4.5,4.5)--(2.5,4.5)--(0.5,4.5)); dot((0.5,0.5)); dot((0.5,2.5)); dot((2.5,2.5)); dot((2.5,0.5)); dot((4.5,0.5)); dot((4.5,2.5)); dot((4.5,4.5)); dot((2.5,4.5)); dot((0.5,4.5)); [/asy]$

We put the original shaded square was in the corner, so, the possible number of squares that cound be uncovered is $\left(\dfrac{n+1}{2}\right)^2 = \frac{n^2+2n+1}{4}$ , all of which can be connected by a single path. Let those $\frac{n^2+2n+1}{4}$ belong to a set $S$ of squares.

If the initial uncovered square was not an element of $S$ , then it could either be $1$ or $\sqrt{2}$ away from a square in $S$ . If the initial square was a distance of $1$ from a element of $S$ , then there would be $\left(\dfrac{n+1}{2}\right)\left(\dfrac{n-1}{2}\right)$ possible uncovered squares:

$[asy] draw((0,0)--(0,5)); draw((1,0)--(1,5)); draw((2,0)--(2,5)); draw((3,0)--(3,5)); draw((4,0)--(4,5)); draw((5,0)--(5,5)); draw((0,0)--(5,0)); draw((0,1)--(5,1)); draw((0,2)--(5,2)); draw((0,3)--(5,3)); draw((0,4)--(5,4)); draw((0,5)--(5,5)); dot((0.5,1.5)); dot((0.5,3.5)); dot((2.5,1.5)); dot((2.5,3.5)); dot((4.5,1.5)); dot((4.5,3.5)); [/asy]$

If the initial square was a distance of $\sqrt{2}$ away from a square in $S$ , then there would be $\left(\dfrac{n-1}{2}\right)^2$ possible squares that could be uncovered:

$[asy] draw((0,0)--(0,5)); draw((1,0)--(1,5)); draw((2,0)--(2,5)); draw((3,0)--(3,5)); draw((4,0)--(4,5)); draw((5,0)--(5,5)); draw((0,0)--(5,0)); draw((0,1)--(5,1)); draw((0,2)--(5,2)); draw((0,3)--(5,3)); draw((0,4)--(5,4)); draw((0,5)--(5,5)); dot((1.5,1.5)); dot((1.5,3.5)); dot((3.5,1.5)); dot((3.5,3.5)); [/asy]$

So, that means the maximal number of squares that can be uncovered is $\frac{n^2+2n+1}{4}$ , thus making a maxmial of $k(C)=\boxed{\frac{n^2+2n+1}{4}}$ achievable configurations from $C$ ( $C$ 's uncovered square must belong in $S$ ).

~ sml1809

2023 USAJMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2023 USAJMO Problems/Problem 3

Problem

Solution

See Also