2023 USAJMO Problems/Problem 3

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

Let's consider what happens when our first domino slides into the empty square:

Page

Toolbox

Search

2023 USAJMO Problems/Problem 3

Problem

Solution