Difference between revisions of "2023 USAJMO Problems/Problem 3"
(→Problem) |
(→Solution) |
||
| Line 5: | Line 5: | ||
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>. | 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: | ||
Revision as of 16:03, 8 May 2023
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
We claim that the maximum possible value for when 
is 
more than when 
.
Let's consider what happens when our first domino slides into the empty square:
