只需考虑对称性——EGMO 2022 P5

在刚刚结束的第11届欧洲女子数学奥林匹克竞赛中，第五题是一道组合题。题目是这样的：

对于所有的正整数n和k，设f(n, 2k)是用2 × 1大小的多米诺骨牌完美覆盖一个n × 2k的棋盘所有可能的方法数。例如，f(2, 2) = 2，f(3, 2) = 3。试求出所有的正整数n，使得对于任意正整数k，f(n, 2k) 一定是个奇数。

这是一个棋盘完美覆盖问题，我们第一次讲座的主题就是完美覆盖问题，只不过这道题的目的不在于棋盘是否可以完美覆盖，而是在于求得对于不同尺寸的棋盘，完美覆盖的方法数。

我们从简单的例子入手，寻求规律。

当n = 1时，显然，骨牌只能一个个地横着排下去，只存在1种完美覆盖的方法。所以对于所有的k，f(n, 2k)= 1，n = 1是符合题意的一个解。

当n = 2时，f(2, 2) = 2。如下图，一共有2种完美覆盖方法。

注意到，因为2 × 2的棋盘是一个正方形，所以这两种完美覆盖方法实际上具有旋转对称性，即将左图顺时针旋转90度，即可得到右图。

同时注意到，2 × 1的多米诺骨牌本身不具有旋转对称性，即将一块横着（或者竖着）摆放的多米诺骨牌顺时针旋转90度后，得到的竖着（或者横着）摆放的多米诺骨牌无法和原来的骨牌完全重合。

这意味着，对于f(2, 2)中的任一个完美覆盖方法，都可以通过顺时针旋转90度得到另一个与之不完全相同的完美覆盖方法。因此f(2, 2)一定是一个偶数。

容易知道，这一旋转对称性对于任意正方形的棋盘都是存在的。所以，当n为偶数时，出于上述的旋转对称性，f(n, n)一定是一个偶数。因此，所有偶数n都不是符合题意的解。

当n = 3时，f(3, 2) = 3。如下图，一共有3种完美覆盖方法。

如果要对这3种方法进行分类，我们可以发现，如果在棋盘的竖直方向画出一条中线的话，那么第2种和第3种方法两两关于这条中线镜面对称，而第1种方法自身关于这条中线镜面对称。

换句话说，对于任意奇数n，所有的完美覆盖方法可以分为两类：

1. 自身关于中线镜面对称。中间一块多米诺骨牌必然是横着摆放在中线上，否则无法形成镜面对称。剩下的偶数块骨牌分为对称的上下两部分，因此，这一类的方法与上面（或下面）部分的完美覆盖方法一一对应，即这一类的方法数等于f((n - 1)/2, 2k)。

2. 自身关于中线不对称。对于这一类中的某一个方法，在此类中一定存在另一个方法，它们两两关于中线镜面对称，因此，这一类方法的总数为偶数。

f(n, 2k)等于这两类方法数之和。因此，对于任意奇数n，如果其自身关于中线镜面对称的方法数f((n -1)/2, 2k)是一个奇数，那么其方法的总数也是一个奇数；如果其自身关于中线镜面对称的方法数f((n -1)/2,2k)是一个偶数，那么其方法的总数f(n, 2k)也是一个偶数。即，f(n, 2k)与f((n -1)/2, 2k)同奇偶性。

对于任意奇数n，反复进行(n - 1)/2的操作，直到下一个得数不是整数为止，其结果要么得到一个偶数2m，要么得到1（因为对于其它奇数，这个操作仍然可以继续下去）。

如果得到一个偶数2m，因为f(2m, 2m)一定是一个偶数，所以回溯得出f(n, 2m)一定是个偶数，即n不是符合题意的一个解。

如果得到1，因为f(1, 2k) = 1，所以对于n = 1, 3, 7, 15…，f(n, 2k)都是奇数，这些奇数n都是符合题意的解。

综上，我们得出所求解即形如2^m - 1的奇数。

总结起来，这道组合题并不需要用到很高深的数学知识，解题的关键无非用到了两种对称性：首先通过旋转对称将所有的偶数n排除在外；然后通过镜面对称，找到了对于所有奇数f值同奇偶性的一种递归规律；最终从n = 1开始通过反推，得出所有符合题意的解。