MathDB

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

.
Proposed by Holden Mui

Problem Statement