Difference between revisions of "2023 USAMO Problems/Problem 3"
m |
|||
| Line 29: | Line 29: | ||
| − | + | ==See Also== | |
| − | {{MAA Notice | + | {{USAMO newbox|year=2023|num-b=2|num-a=4}} |
| + | {{MAA Notice]] | ||
Latest revision as of 18:18, 6 October 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 the answer is 
.
First, consider a checkerboard tiling of the board with 4 colors: R, G, B, Y. Number each column from 
to from left to right and each row from to from top to bottom. We color a tile R if its row and column are odd, a tile G is its row is even but its column is odd, a tile B if its row and column is even, and a tile Y if its row is odd but its column is even.
Lemma 1: Throughout our moves, the color of the uncolored tile stays an invariant.
Consider that a domino can either only change rows or can only change columns. Therefore, sliding a domino into the hole and creating a new one has two possible colors. Of these, note that the new hole will always trivially be two tiles away from the old hole, meaning that the parity of both the row and column number stays the same. Thus, the lemma holds.
Lemma 2: There are more red tiles than any other color.
Because each color is uniquely defined by the parity of a pair of column and row number, it satisfies to show that given an odd integer , there are more odd positive integers less than or equal to than even ones. Obviously, this is true, and so red will have more tiles than any other color.
Lemma 3: For any starting configuration and any blank tile 
such that the blank tile's color matches the blank tile's color of , there is no more than one unique configuration 
that can be produced from using valid moves.
We will use proof by contradiction. Assume there exists two different . We can get from one of these to another using moves. However, we have to finish off with the same hole as before. Before the last move, the hole must be two tiles away from the starting hole. However, because the domino we used to move into the blank tile's spot is in the way, that hole must be congruent to the hole produced after the first move. We can induct this logic, and because there is a limited amount of tiles with the same color, eventually we will run out of tiles to apply this to. Therefore, having two distinct with the same starting hole is impossible with some .
We will now prove that is the answer. There are 
rows and columns that are odd, and thus there are red tiles. Given lemma 3, this is our upper bound for a maximum. To establish that is indeed possible, we construct such a :
In the first column, leave the first tile up blank. Then, continuously fill in vertically oriented dominos in that column until it reaches the bottom.
In the next 
columns, place 
vertically oriented dominos in a row starting from the top. At the bottom row, starting with the first unfilled tile on the left, place horizontally aligned dominos in a row until you reach the right.
Obviously, the top left tile is red. It suffices to show that any red tile may be uncovered. For the first column, one may slide some dominos on the first column until the desired tile is uncovered. For the bottom row, all the first dominos may be slid up, and then the bottom dominos may be slid to the left until the desired red tile is uncovered. Finally, for the rest of the red tiles, the bottom red tile in the same color may be revealed, and then vertically aligned dominos in the same column may be slid down until the desired tile is revealed. Therefore, this configuration may produce different configurations with moves.
Hence, we have proved that is the maximum, and we are done. 
~SigmaPiE
See Also
| 2023 USAMO (Problems • Resources) | ||
| Preceded by Problem 2 |
Followed by Problem 4 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
{{MAA Notice]]
