Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2023 USAJMO Problems/Problem 3

Revision as of 14:41, 18 July 2023 by Hungrycalculator (talk | contribs) (→‎Solution)

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_USAJMO_Problems/Problem_3&oldid=195873"