2023 USAMO 第 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 all possible values of $k(C)$ as a function of $n$.

考虑一个 $n$×$n$ 单位方块板，其中包含一些奇数正整数 $n$。如果 $C$ 由 $(n^2-1)/2$ 多米诺骨牌组成，其中每个多米诺骨牌正好覆盖两个相邻的方格，并且多米诺骨牌不重叠，那么我们说，相同多米诺骨牌的集合 $C$ 是棋盘上的最大网格对齐配置：然后 $C$ 覆盖棋盘上除一个方格之外的所有方格。我们可以在棋盘上滑动(但不能旋转)多米诺骨牌来覆盖未覆盖的正方形，从而形成一个新的最大网格对齐配置，同时另一个未覆盖的正方形。令 $k(C)$ 为通过重复滑动多米诺骨牌从 $C$ 获得的不同最大网格对齐配置的数量。找出 $k(C)$ 作为 $n$ 函数的所有可能值。