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

题目 为整数．有一块的木板，初始是空的．在每一分钟，可以完成下列三个操作之一：

1. 如果木板上有个单元格组成的形区域（如下图，不允许旋转），且其中都没有石头，则可以在这个单元格中各放置一块石头；
2. 如果某一行的每一个单元格中均有石头，则可以将这一行的所有石头移除；
3. 如果某一列的每一个单元格中均有石头，则可以将这一列的所有石头移除。

对于满足怎样条件的，可以经过若干次（非零）操作后，使得木板上没有任何石头？

（2021年USAMO第1天第3题）

分析 看完题目立马想到了俄罗斯方块，以及一些消除类的小游戏．构造出可以消除完所有石头的操作并不难，可以尝试的情形，发现只有在的方格中可以完成，由此推出时均满足题意．证明其它情形不满足题意是这题的难点，关键是对每个单元格进行赋值，并构造出一个合适的生成函数．此外，在证明答案只能是某个数的倍数时，常用单位根进行分析．

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

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

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

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

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

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

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

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

由于最终木板上没有任何石头，故存在非负整系数多项式，，，满足：

设为一个次单位根，则对于任意的，

于是

又不整除时，，故

固定，关于的方程，有

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

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