数学竞赛中的俄罗斯方块——一道USAMO组合题的解答

解答 先考虑𝑛=3时的情形，进行如下操作：

1. 进行两次操作（1），此时木板上只剩下左上、右上、右下三个空格；
2. 移除第二行的三块石头；
3. 在左边两列的空格处放置三块石头；
4. 依次移除第一列和第二列的石头．

当𝑛>3，且3|𝑛时，将𝑛×𝑛的木板分成若干个3×3的小区域，类似进行如上操作即可．

接下来考虑3不整除𝑛时的情形．

将每个单元格进行赋值．设从下到上第𝑎行，从左到右第𝑏列的单元格坐标为(𝑎,𝑏)．若单元格(𝑎,𝑏)中有石头，则将其赋值为𝑥^(𝑎−1)𝑦^(𝑏−1)，否则将其赋值为0．考虑三种操作会带来的结果：

1. 在以(𝑎,𝑏)为拐角的“𝐿”形区域中放置三块石头后，所有方格赋值之和增加

公式：\begin{align*} &x^{a-1}y^{b-1}+x^{a}y^{b-1}+x^{a-1}y{b}\\ =&(1+x+y)x^{a-1}y^{b-1} \end{align*}

2. 移除第𝑎行的所有石头后，所有方格赋值之和减少

公式：\begin{align*} &x^{a-1}(1+y+y^2+\cdots+y^{n-1})\\ =&x^{a-1}\cdot\dfrac{y^{n}-1}{y-1} \end{align*}

3. 移除第𝑏列的所有石头后，所有方格赋值之和减少

公式：\begin{align*} &y^{b-1}(1+x+x^2+\cdots+x^{n-1})\\ =&y^{b-1}\cdot\dfrac{x^{n}-1}{x-1} \end{align*}

由于最终木板上没有任何石头，故存在非负整系数多项式𝑓(𝑥,𝑦)，𝑔(𝑥)，ℎ(𝑦)，满足：

公式：\begin{align*} &(1+x+y)f(x,y)\\ =&\dfrac{y^n-1}{y-1}g(x)+\dfrac{x^n-1}{x-1}h(y) \end{align*}

设𝜔≠1为一个𝑛次单位根，则对于任意的1≤𝑎,𝑏≤𝑛−1，

于是

公式：\begin{align*} &(1+\omega^a+\omega^b)f(\omega^a,\omega^b)\\ =&\dfrac{(\omega^b)^n-1}{\omega^b-1}g(\omega^a)+\dfrac{(\omega^a)^n-1}{\omega^a-1}h(\omega^b)\\ =&0 \end{align*}

又3不整除𝑛时，1+𝜔^(𝑎)+𝜔^(𝑏)≠0，故

固定𝑏，关于𝑥的方程，𝑓(𝑥,𝜔^(𝑏))=0有

这𝑛−1个不同的根．注意到，第𝑛行的方格中一定无法被放满石头，要使得最后木板为空，则不能在第𝑛行的任何方格中放置石头．于是𝑓(𝑥,𝑦)中𝑥的最高次数不超过𝑛−2，矛盾！

综上，满足题意的𝑛为所有3的倍数．