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

Revision as of 15:23, 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$ .

Solution

We claim that the maximum possible value for $k(C)$ when $n=i$ is $i$ more than $k(C)$ when $n=i-1$ .

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 $\frac{n-1}{2}$ by $\frac{n-1}{2}$ .

Page

Toolbox

Search

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

Revision as of 15:23, 8 May 2023

Problem

Solution

@@ Line 6: / Line 6: @@
 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>.
-Let's consider what happens when our first domino slides into the empty square:
+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>.