Math Gold Medalist

Lor

2023 USAMO

Problem 3

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

Small Example

Considering Range

Coloring

Extremal Combinatorics

Directed Graph

Consider Small Examples

n=1 ->  k(C)=1

n=3 ->  k(C)=1,4

n=5 ->  k(C)=1,2,3,4,9

n=2m+1 -> k(C)=1,2,3,…,k^2,(k+1)^2

If the hole is determined then the table is determined.

k(C) <= (k+1)^2

2020 IMO Problem 4

2016 IMO Problem 2

   Solution