2023 USAJMO Problems/Problem 3
Problem
Consider an -by- board of unit squares for some odd positive integer . We say that a collection of identical dominoes is a maximal grid-aligned configuration on the board if consists of dominoes where each domino covers exactly two neighboring squares and the dominoes don't overlap: 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 be the number of distinct maximal grid-aligned configurations obtainable from by repeatedly sliding dominoes. Find the maximum value of as a function of .
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":
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:
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:
We put the original shaded square was in the corner, so, the possible number of squares that cound be uncovered is , all of which can be connected by a single path. Let those belong to a set of squares.
If the initial uncovered square was not an element of , then it could either be or away from a square in . If the initial square was a distance of from a element of , then there would be possible uncovered squares:
If the initial square was a distance of away from a square in , then there would be possible squares that could be uncovered:
So, that means the maximal number of squares that can be uncovered is , thus making a maxmial of achievable configurations from ('s uncovered square must belong in ).
~ sml1809
See Also
2023 USAJMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.