2023 Putnam B1

Consider an $m$-by-$n$ grid of unit squares, indexed by $(i,j)$ with $1 \leq i \leq m$ and $1 \leq j \leq n$. There are $(m-1)(n-1)$ coins, which are initially placed in the squares $(i,j)$ with $1 \leq i \leq m-1$ and $1 \leq j \leq n-1$. If a coin occupies the square $(i,j)$ with $i \leq m-1$ and $j \leq n-1$ and the squares $(i+1,j), (i,j+1)$, and $(i+1,j+1)$ are unoccupied, then a legal move is to slide the coin from $(i,j)$ to $(i+1,j+1)$. How many distinct configurations of coins can be reached starting from the initial configuration by a (possibly empty) sequence of legal moves?

考虑一个 $m$×$n$ 单位正方形网格，由 $(i,j)$ 索引，其中 $1 \leq i \leq m$ 和 $1 \leq j \leq n$。有 $(m-1)(n-1)$ 个硬币，最初放置在 $1 \leq i \leq m-1$ 和 $1 \leq j \leq n-1$ 的方格 $(i,j)$ 中。如果一枚硬币以 $i \leq m-1$ 和 $j \leq n-1$ 占据方格 $(i,j)$，并且方格 $(i+1,j)、(i,j+1)$ 和 $(i+1,j+1)$ 未被占据，则合法的移动是将硬币从 $(i,j)$ 滑动到 $(i+1,j+1)$。从初始配置开始，通过合法移动序列(可能是空的)可以达到多少种不同的硬币配置？