来自不同领域的证明

说到数学证明，不得不谈到数学界的一篇奇文。1987年，斯坦·瓦根（Stan Wagon）在《美国数学月刊》上发表了一篇题目为《一个矩形剖分定理的十四种证法》的论文，论文中提到了这么一个定理：

如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一边为整数长。

换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也一定有至少一条整数长的边。这个命题看似简单，想到证明方法却并不容易。斯坦·瓦根竟然给出了十四种完全不同的证明方法，每一种证明方法都非常巧妙。我选择了其中六个最具代表性的证明，和大家一同分享。

我们所要介绍的第一个证明是我觉得最巧妙的证明方法。证明的关键在于下面这个引理：像国际象棋棋盘一样对整个平面黑白染色，那么与两坐标轴平行放置且至少一边长为偶数个单位的矩形一定覆盖了相同面积的黑色区域和白色区域。原因很简单，如图 1，无妨假设这个矩形的水平方向上的边是偶数个单位长，那么该矩形中的每个横条显然都覆盖了相同面积的黑白两色区域。对于竖直边的边长为偶数的矩形，也是同样的道理。

图1

下面，我们把平面分成大小的正方形，并且像上面那样对其进行黑白二染色，然后像图2那样，将整个大矩形对齐坐标轴放在平面上，左下角和原点重合。这个矩形内的每个小矩形都有至少一条整数边，也即至少有一边的长度是1/2的偶数倍，因此每个小矩形都覆盖了相同面积的黑色区域和白色区域。这样，整个大矩形也就覆盖了相同面积的黑色区域和白色区域。

图2

下面我们将说明，对于一个左下角与原点对齐的矩形，如果右上角的顶点（x，y）的两个坐标值都不是整数，那么这个矩形所覆盖的黑色区域一定大于白色区域。如图3，除去黑白相等的“整”的部分，最后剩下的就是最右上角的那个横纵两个方向均未被填满的1×1正方形有待讨论。

图3

如图4，坐标（x，y）的位置只有A、B、C三种可能。如果坐标（x，y）位于区域A，很容易看出黑色面积比白色面积大；如果坐标（x，y）位于区域 B，也很容易看出黑色面积比白色面积大；如果坐标（x，y）位于区域 C，则矩形没有覆盖到的拐角形区域中白色面积更大，因而矩形内的黑色面积就更大一些。

图4

如果要让整个矩形覆盖相同面积的黑色区域和白色区域，x和y至少有一个是整数才行，而这就是我们所要证明的结论了。

利用数学归纳法，我们可以得到另一个思路完全不同的初等的证明。如图 5，我们首先把每个小矩形都分割成单位宽度的长条。这样的话，大矩形里就只有两种小矩形：宽为1的竖条状矩形（图5中的浅色矩形）和高为1的横条状矩形（图5中的深色矩形）。我们对浅色矩形的个数施加归纳。随便选择一个浅色的矩形（例如图 5（2）中的阴影矩形），增加它的高度，让它“穿过”它头顶上的深色矩形（把它正上方的深色矩形截断），直到这根竖条状矩形的顶端碰到了另一个浅色矩形的底端。把后者作为新的操作对象，继续增加其高度，必要时再次更换操作对象，直到达到整个大矩形的上边界。我们用同样的方法让最初所选的阴影矩形向下“生长”到大矩形的下边界。

图5

注意到在此过程中，浅色矩形始终保持着单位宽度，深色矩形始终保持着单位高度。整个过程结束后，深色矩形的个数变多了，但浅色矩形的个数不变。此时我们得到了一条上下贯穿整个大矩形的浅色矩形链。把它们擦掉，将右半部分左移一个单位，重新拼成一个大矩形。新的大矩形高度不变，宽度减1，因而原来的整数边还是整数，非整数边仍然不是整数。同时，浅色矩形的个数减少了。反复进行这样的操作，总有一个时候大矩形里只剩下深色的矩形（则原大矩形高度显然为整数），或者某次操作后所有矩形都被去掉了（则原大矩形宽度为整数）。

借用这种方法我们还可以得到一个颇有喜剧效果的反证法。假设大矩形的长度和宽度都不是整数，那么每一步操作后，它们仍然是非整数，这表明大矩形里不可能只剩一种颜色的小矩形，于是我们可以无限制地调用上面的操作。最后的结果是：我们得到了一个用整数长或整数宽的小矩形拼成的一个大矩形，而这个大矩形的横边竖边都小于1！这显然是荒谬的。

接下来，我将要给大家介绍第三种证明方法——图论方法。如图6，首先，找出图中所有的“交叉点”（包括整个大矩形的四个顶点），然后按照下面的方式把它们连起来：对于每个小矩形，如果它的两条水平边的长度是整数，就用上下两条线分别连接水平方向上的两对点；如果它的两条竖直边的长度是整数，就用左右两条线分别连接竖直方向上的两对点；如果它的四条边的长度都是整数，只需连接其中一组对边即可。这样的话，每个矩形都会产生两条连线，矩形的四个顶点各被用过一次。于是，我们得到了一个由若干顶点和这些顶点之间的连线构成的图。在这个图中，大矩形的四个顶点的度数为 1；由于其他每个交叉点都同属于两个小矩形或者四个小矩形，因此其余顶点的度数都是2或者4。下面，我们把这个矩形放在平面直角坐标系中，大矩形的左下角对齐原点（0，0）。现在，从原点出发，沿着我们所画的线条行走，并且把沿途走过的线条都擦掉。显然，我们走到的每个点的两个坐标均为整数。

我们是从一个度数为1的顶点出发的，显然不可能再回到出发点了，只能沿着图中的线条漫无目的地游荡。但是，图中的总边数是有限的，总有一个时候我们将会无路可走。注意到，我们绝不可能在度数为2或者4的地方无路可走，因为度数为偶数也就意味着这个顶点“有进必有出”。因此，这趟旅程的终点必然会落在另一个度数为1的点上。这个终点一定是大矩形的另一个角，因而它的两个坐标值均为整数。于是命题得证。

图6

利用类似的思路，安德烈·内普（Andrei Gnepp）曾给出一个更简单的证明：由于每个小矩形都有至少一对整数长的边，因而一个小矩形的四个顶点中，两个坐标值均为整数的顶点只可能有0个、2个或者4个。把它们全部加起来，符合条件的总顶点数S仍然是偶数。但是，这S个顶点中有些点是重复算过的。除了大矩形四个角上的顶点外，其他每个顶点都同属于两个矩形或者四个矩形，如果某个顶点的横纵坐标都是整数，则它将会被重复计算两次或者四次。假如我们有S₁个两坐标均为整数的顶点只被算过一次，有 S₂个这样的点被算过两次，有 S₄个这样的点被加了四次，则有S＝S₁﹢2×S₂﹢4×S₄。我们立即得出，S₁也是偶数。但我们已经有一个只被算过一次的点（即最左下角的点（0，0）），那么S₁至少为 2，即至少还有一个两坐标均为整数并且只被算过一次的点，它即是大矩形的另一个角。

彼得·温克勒（Peter Winkler）也曾给出图论证明法的另一个变形。如图7，还是把整个大矩形放在平面直角坐标系中，左下角和原点重合。现在，对于每个小矩形，如果它的两条水平边的长度是整数，就把这个矩形染成浅色，不过在上下两条边各留下一个很窄很窄的深色横条；如果它的两条竖直边的长度是整数，就把它染成深色，不过左右两条边各留下一个很窄很窄的浅色竖条；如果它的四条边的长度都是整数，就随便采用一种染色方案。那么，整个大矩形中要么存在一条从左边界到右边界的浅色路径，要么浅色区域没能连通左右边界，从而整个图中存在一条从下边界到上边界的深色路径。在前一种情况中，容易看出，这条路径穿过的所有竖直线段的x坐标都是整数，这就表明整个大矩形的宽度是整数；类似地，后一种情况也就表明，整个大矩形的高度是整数。

图7

接下来是第四种证明方法，这种证明方法可就有些另类了。同样将矩形放置在平面直角坐标系中，左下角对齐原点（0，0）。选取一个充分小的变量t。对于每个小矩形，把所有x坐标不是整数的竖直边都向右平移t，把所有y坐标不是整数的水平边都向上平移t。如果一个小矩形的竖直边的长度是整数，那么它的两条水平边要么都被平移了t，要么都没有被平移；如果一个小矩形的水平边的长度是整数，那么它的两条竖直边要么都被平移了t，要么都没有被平移。总之，一个宽和高分别为w、h的小矩形，变化之后的新的面积只可能是w×（h±t）、（w±t）×h、w×h中的一种，它一定是一个关于t的一次函数（包括常函数的情况）。因此，整个大矩形的新面积也是一个关于t的一次函数。然而，如果大矩形的两条边的长度a、b都不是整数，大矩形的面积将会变为（a﹢t）（b﹢t），这是一个关于t的二次函数。因此，大矩形至少会有一条整数长的边。

下面轮到真正怪异的证明方法登场了。借助看上去与这个问题毫不相干的微积分知识，我们能够迅速证明这一结论。还是把矩形放在平面直角坐标系中，左下角对齐原点（0，0）。考虑函数e^{2πi（x﹢y）}在每个小矩形上的积分：

显然，这个式子等于0当且仅当x₁-x₀和y₁-y₀中至少一个是整数，也即该小矩形至少有一边的长度是整数。考虑函数在整个大矩形上的积分，它可以拆成各个小矩形上的积分的和，因此结果仍然是0。这说明，大矩形中也有至少一条整数长的边。

令人更加难以置信的是，这个结论竟然还有一种数论证法。证明的关键就在于，质数有无穷多个。给定一个满足要求的大矩形，如果你宣称它的四条边的长度都不是整数，它们都多出了大小至少为ε的“零头”。那么，我总能找出一个足够大的质数p，使得。然后我们将说明，大矩形其中有一条边的长度除去整数部分后的“零头”不会超过1/p，由此产生矛盾。这样的话，至少有一边恰好是整数长才行。

仍然是把大矩形放在平面直角坐标系中，左下角对齐原点（0，0）。考虑所有形如的点所形成的点阵（其中i、j均为整数）。我们需要把整个点阵平移到一个合适的位置，使得点阵中没有点恰好落在小矩形的边界上。这总是可以办到的，例如，我们算出每个小矩形的每条横边到点阵中离它最近的点的距离，取所有这些最近距离中最小的非0的值，然后在竖直方向上将点阵移动一个比这还小的距离；另一个方向亦是如此。

假如数轴上分布着间隔为1/p的点，容易看出，任取一个长度为整数的区间，只要这些点不与区间的端点重合，那么区间内所含点数一定是p的倍数。注意到每个小矩形内部所含的点数都是两个数的乘积，由于其中至少有一个数恰好是p的倍数，因此每个小矩形内都有p的倍数个点。那么，整个大矩形所含的点的个数（即所有小矩形所含点数之和）也是p的倍数。大矩形内的所有点的个数也是两个数的乘积，然而p是质数，因此两个数中至少一个含有因数p。那么，对应的那条边也包含了p的倍数个点。这说明，这条边应该是整数长，最多有1/p的误差。