趣题：免分割线的多米诺骨牌覆盖方案

问题：能否用多米诺骨牌既无重复又无遗漏地覆盖一个 6 × 6 的棋盘，使得棋盘上的每一条水平线和每一条竖直线都会穿过至少一个多米诺骨牌？举个例子，下图所示的棋盘覆盖方案就是不满足要求的，因为棋盘的第二条水平线不会切断任何一个多米诺骨牌。



满足要求的棋盘覆盖是不存在的。我们有一个非常漂亮的证明。注意到，任意一条水平线都会把整个棋盘分成上下两部分，这两部分所包含的小正方形的个数都是偶数。那些完全在这条线上面的多米诺骨牌会占据其中偶数个格子，那些完全在这条线下面的多米诺骨牌也会占据其中偶数个格子，因而棋盘的上下两部分各剩下了偶数个格子，这些格子就留给了那些穿过了这条水平线的多米诺骨牌来占据。每一个穿过了这条线的多米诺骨牌都会在上下两部分棋盘各占据一个格子，因此为了完全覆盖棋盘，这样的多米诺骨牌必须得有偶数个才行。结论就是：在一个满足要求的棋盘覆盖方案中，每条水平线都会穿过至少两个多米诺骨牌。同理，每条竖直线也都会穿过至少两个多米诺骨牌。然而，在 6 × 6 的棋盘中，水平线和竖直线一共有 10 条，每条线上都有两个多米诺骨牌，这显然是不现实的，因为整个棋盘里一共也只能放下 18 个多米诺骨牌。

有趣的是，棋盘再稍微大一些，这种推理就失效了。在一个 8 × 8 的棋盘中，水平线和竖直线一共有 14 条，它们对应于 28 个多米诺骨牌，这却并不会导致矛盾，因为棋盘里一共能放下 32 个多米诺骨牌。那么， 8 × 8 的棋盘是否存在满足要求的覆盖方案呢？更一般地，对于哪些正整数 M 和 N ，在一个 M × N 的棋盘里存在满足要求的覆盖方案呢？注意， M 和 N 这两个数当中至少得有一个数是偶数，否则整个棋盘将会有奇数个小方格，这根本不可能被多米诺骨牌既无重复又无遗漏地覆盖住。

不妨假设 M ≤ N 。 M = 1 和 M = 2 的情况基本上可以直接被排除了（不过，这里面有一个特例，即 (M, N) = (1, 2) 可以算作是一个平凡解）。 M = 3 的情况基本上也可以直接被排除，但这可能不大容易看出来。假如一个棋盘只有 3 行，最左边那一列肯定不能全用横向的多米诺骨牌覆盖，否则将会立即产生一条通畅的竖直线，如左图所示。那么，最左边那一列肯定有一个纵向的多米诺骨牌，比如右图中的 1 号多米诺骨牌。于是，覆盖方案会被迫地向右图所示的方向发展，最终会不可避免地出现一条通畅的水平线。

M = 4 的情况也能被排除。最左边的那一列不能全被横着的多米诺骨牌占据，也不能全被竖直的多米诺骨牌占据，剩下的本质不同的可能性就只有下面两种了，这最终都会被迫失败。

接下来该研究的就是 M = 5 的情况。由于 M 、 N 都等于 5 的情况已经被我们排除了（ M 、 N 不能都是奇数），因此我们应该开始考虑 M = 5 并且 N = 6 的情况。这是第一次出现有解的情况：在 5 × 6 的棋盘上，满足要求的覆盖方案是存在的！下图就是其中一种方案，你可以考虑先自己想一会儿再查看答案：

令人意想不到的是，对于其他所有的情况，满足要求的覆盖方案都是存在的！也就是说，如果我们能用多米诺骨牌既无重复又无遗漏地覆盖 M × N 的棋盘，使得棋盘中的每一条水平线和竖直线都会穿过至少一个多米诺骨牌，则 M 和 N 必须而且只须同时满足下面这些条件：

(1) M 和 N 至少有一个是偶数；

(2) M 和 N 都大于 4 ；

(3) M 和 N 不同时等于 6 。

刚才，我们已经给出了 M 、 N 分别等于 5 和 6 时的方案。我们便能很快得出，只要 M 、 N 这两个数一个是奇数一个是偶数，满足要求的覆盖方案都是存在的。这是因为，对于任意一个合法的覆盖方案，我们都能按照下面的模式，把它扩展成一个新棋盘下的覆盖方案，使得棋盘的其中一条边的长度不变，另一条边的长度比原来增加 2 个单位。

我们详细解说一下这种扩展模式吧。首先注意到，原覆盖方案的最后一列不可能都是用横向的多米诺骨牌覆盖的，也不可能都是用纵向的多米诺骨牌覆盖的（否则会立即产生一条通畅的竖直线）。因此，最后一列的多米诺骨牌一定是有横有竖的。把这些多米诺骨牌向右移动两个单位，然后用横向的多米诺骨牌填充由此所得的空白，就得到了一个新的方案。新方案的每条线为什么都穿过了至少一个多米诺骨牌呢？为了说明这一点，我们只需要考察新的棋盘中最后那几条竖直线即可。这很容易看出来——刚才的那个“有横有竖”的结论可以保证这些竖直线都不会是畅通的。

现在，估计大家已经看出来了，为了填上之前埋下的所有坑，我们只差最后一环了：在一个 6 × 8 的棋盘上设计一种满足要求的覆盖方案。这样一来，我们便能从 5 × 6 和 6 × 8 这两个基础布局出发，不断套用刚才的扩展模式，从而为所有应该有解的棋盘提供一个满足要求的解。给出一个 6 × 8 的布局并不容易，但也不算太难，你也可以考虑先想一想，再查看下图所示的答案：

原问题是一道非常经典的问题了，经典的组合数学教材《Introductory Combinatorics》开篇就提过这个例子。后面的探讨则出自 Solomon Wolf Golomb 的《Polyominoes》一书。