Difference between revisions of "2023 USAJMO Problems/Problem 3"
(→2023 USAJMO Problems/Problem 3) |
(→Solution) |
||
(10 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
Consider an <math>n</math>-by-<math>n</math> board of unit squares for some odd positive integer <math>n</math>. We say that a collection <math>C</math> of identical dominoes is a maximal grid-aligned configuration on the board if <math>C</math> consists of <math>(n^2-1)/2</math> dominoes where each domino covers exactly two neighboring squares and the dominoes don't overlap: <math>C</math> 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 <math>k(C)</math> be the number of distinct maximal grid-aligned configurations obtainable from <math>C</math> by repeatedly sliding dominoes. Find the maximum value of <math>k(C)</math> as a function of <math>n</math>. | Consider an <math>n</math>-by-<math>n</math> board of unit squares for some odd positive integer <math>n</math>. We say that a collection <math>C</math> of identical dominoes is a maximal grid-aligned configuration on the board if <math>C</math> consists of <math>(n^2-1)/2</math> dominoes where each domino covers exactly two neighboring squares and the dominoes don't overlap: <math>C</math> 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 <math>k(C)</math> be the number of distinct maximal grid-aligned configurations obtainable from <math>C</math> by repeatedly sliding dominoes. Find the maximum value of <math>k(C)</math> as a function of <math>n</math>. | ||
+ | |||
+ | ==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 <math>\left(\dfrac{n+1}{2}\right)^2 = \frac{n^2+2n+1}{4}</math>, all of which can be connected by a single path. Let those <math>\frac{n^2+2n+1}{4}</math> belong to a set <math>S</math> of squares. | ||
+ | |||
+ | If the initial uncovered square was not an element of <math>S</math>, then it could either be <math>1</math> or <math>\sqrt{2}</math> away from a square in <math>S</math>. If the initial square was a distance of <math>1</math> from a element of <math>S</math>, then there would be <math>\left(\dfrac{n+1}{2}\right)\left(\dfrac{n-1}{2}\right)</math> 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 <math>\sqrt{2}</math> away from a square in <math>S</math>, then there would be <math>\left(\dfrac{n-1}{2}\right)^2</math> 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 <math>\frac{n^2+2n+1}{4}</math>, thus making a maxmial of <math>k(C)=\boxed{\frac{n^2+2n+1}{4}}</math> achievable configurations from <math>C</math> (<math>C</math>'s uncovered square must belong in <math>S</math>). | ||
+ | |||
+ | ~ sml1809 | ||
+ | |||
+ | ==See Also== | ||
+ | {{USAJMO newbox|year=2023|num-b=2|num-a=4}} | ||
+ | {{MAA Notice}} |
Latest revision as of 00:27, 14 January 2024
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.