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

Difference between revisions of "2023 USAJMO Problems/Problem 3"

(→‎Solution)
(→‎Solution)
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==
 
−
 
−
We claim that the maximum possible value for <math>k(C)</math> when <math>n=i</math> is <math>i</math> more than <math>k(C)</math> when <math>n=i-1</math>.
 
−
 
−
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 2 squares above the original one. However, there is 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 original shaded square. The new uncovered square, as a result, would be either two squares to the left, or to the right of the original 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>
 
−
 
−
Now, notice that the only squares that cound be uncovered are those that have of a spaced out <math>\frac{n-1}{2}</math> by <math>\frac{n-1}{2}</math>.
 

Revision as of 16:36, 8 May 2023

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$.

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