你见过哪些堪称绝妙的数学证明？ 第1页

2020/7/6更新 添加一个新的证明

Euler Partition Theorem

把一个正整数 不计顺序地分成若干个正整数的和，这样的操作我们记作 的一个划分。这些正整数叫做 的一个part， 的所有划分的数目我们记作 。例如对于正整数4，我们有4=4=3+1=2+2=2+1+1=1+1+1+1一共5种划分（所谓的不计顺序是指4=3+1与4=1+3是同一种划分）

证明：对于任意一个正整数 ，把 的所有part均不相同的划分数目记作 ，把 的所有part均为奇数的划分数目记作 ，有 .

为了证明这个问题，我们先介绍一些定义和引理：

定义：对于一个序列 ，我们定义其生成函数为

生成函数有一个很强大的性质，即他和序列是唯一对应的。因此我们可以把原始问题转化为：求证 和 的生成函数相等。

一个很显然的结论是： 的生成函数 为

引理：我们记 为正整数 的划分数目，满足其中 的的所有parts都属于集合 。那么 的生成函数为

该引理证明如下：

我们不妨设 ，则

该展开式中的每一项均为 的形式，其幂次恰好为集合 中元素可能的线性组合，因此这里面的每一项刚好对应所有parts属于集合 的划分数目。每一项 前面的系数恰好为 。证毕。

到目前为止，我们的原始问题转化为了如下：

证明：

证毕。

在交代清楚背景的情况下，该问题的核心证明只需要一行。^[1]

以下为原答案

来说一个经典问题，这是1988年IMO的第六题。

对于正整数 满足

求证 是完全平方数。

这题题干看似简单，但是确实IMO历史上一道经典的难题。该题在赛前被主试委员会和一些数学家拿来挑战，均无功而返。当年全部参赛选手中一共只有11名选手拿到满分，著名数学家陶哲轩也参加了当届IMO，很遗憾的是Tao在这道题上只拿了1分。这道题最绝妙的解法源于保加利亚选手 Emanouil Atanassov他也因此获得了Special Award^[2]。下面展示解法：

假设 不是完全平方数，则有 (否则可以取 ，此时 为完全平方数)。我们假设 ，我们假设存在一组解 使得 最小。我们注意到原表达式可以转写为

接下来我们考虑方程

很显然这个方程有一个根是 。通过Vieta定理我们不难给出第二个根为

通过上式我们能够看出 是一个整数，因为 都是整数，且 ，否则 为完全平方数与假设矛盾。除此之外 应该为非负数，否则

矛盾。所以而是满足原方程的一组解且 。又注意到

故

与原假设 最小矛盾。故可知 为完全平方数。

该题用到的方法被叫做Vieta root jumping^[3]，也被叫做root flipping，自1988年的该题知名后被广泛用于数学竞赛中。

参考

1. ^ https://sites.math.rutgers.edu/~sahi/Courses/ramanujan.pdf
2. ^IMO results http://imo-official.org/year_individual_r.aspx?year=1988&column=total&order=desc
3. ^Yimin Ge, The method of Vieta jumping http://blogs.sch.gr/sotskot/files/2011/01/Vieta_Jumping.pdf

用直观的物理图像方法，证明 (0,1) 区间上的实数，和整个实数域 中的实数一样多（等势）

所谓等势，就是两个集合之间 一 一 对 应^[1]

你可能会想， 包含 啊，怎么可能一样多呢。但是由于这两个都是无穷多个，而且都是不可数无穷大，所以是可以构筑出来一一对应的关系的。

对应整个数轴

对应数轴上从0到1的线段

将 取出来放在数轴上方

将 弯成一个半圆。这样数轴上的每一个数字，与该半圆圆心的连线，都对应 上的一个数字；同理， 上任何一个数字与圆心的连线延长线，也对应数轴上的一个数字。可证明是一一对应。

比如我可以提供一种函数对应关系。假设 上的数字是x，数轴上的是y

将长度为1的线段弯成半圆后，半径为 。所以有

，其中

假设圆心到数轴的距离为2 （实际上你可以取任何不为0的数值），那么就有

也就是

所以，我们就用这种直观的图像方法证明了 区间上的实数，和 中的实数一样多（等势）

可能有人会好奇，是不是只要有两个无穷多的集合，它们就应该是等势的。答案是：不是的。无限集合分为可数集合和不可数集合，其中不可数的要比可数的拥有更多的元素。自然数集合是可数无穷大，实数是不可数无穷大。论证实数是不可数无穷大的方法叫做对角论证法^[2]。

参考

1. ^ https://zh.wikipedia.org/wiki/%E7%AD%89%E5%8A%BF
2. ^ https://zh.wikipedia.org/wiki/%E5%B0%8D%E8%A7%92%E8%AB%96%E8%AD%89%E6%B3%95

1987年AMM有一篇文章叫《一个矩形划分定理的十四种证明》。这个定理是N. G. de Bruijn在1969年发现的：

定理A：如果一个矩形可以划分为有限个 至少有一条边长是整数 的小矩形，那么这个大矩形至少有一条边长是整数。

我建议读者先自己想一想这定理怎么证明。

下面所有证明及习题中，我们把大矩形左下角放在坐标系(0, 0)。

de Bruijn在1969年的原版证明利用了二重积分在划分上可以相加的性质。在任何矩形 上，积分 等于0当且仅当矩形至少有一条边长是整数。所以在每个小矩形上积分等于0，因此在大矩形上积分也等于0，所以大矩形至少有一条边长是整数。

上面这个积分也可以换成别的函数，比如三角函数，或者 等。还可以换成 ，从这个函数的图像可得出另一个证明：以国际象棋棋盘的方式把整个平面染色，其中每个格子边长1/2， 染黑。只要一个矩形 有一边长是整数，那么矩形里的黑色和白色部分面积相等，所以大矩形也是这样。如果它的两边长都不是整数，那么把边长分为整数部分和小数部分，大矩形就被分为4个部分，其中三个部分黑白面积相等，而剩下的一部分的左下角在棋盘交叉点上，两边长度都小于1，因此黑白面积不等，矛盾。

UC Berkeley的Raphael Robinson发现了一个数论证明。令p为素数，把整个图形放大p倍（也就是长度1变成长度p）。下面把每个交叉点 换成其整数部分 ，我们就得到了一个新的大矩形，它被划分为很多两边长均为整数的小矩形，而且每个小矩形有一边长能被p整除。这样这个新的大矩形的面积也能被p整除，所以它的有一边长能被p整除。这条边只是被换成了它长度的整数部分，所以变化不超过1，所以在放大之前这条边的长度和某个整数相差不超过1/p。因为素数有无穷多个，所以原来的大矩形某一条边长度与某个整数相差无限小，证毕。

下面是英国Warwick大学的Michael S. Paterson发现的图论证明。令所有的交叉点为顶点。每个小矩形都有一边长为整数，我们把这两条平行边在图上标出（允许两顶点之间的重复边），另外两条边不连。这样除了大矩形的四个角以外每个顶点有2条边或者4条边，而大矩形四个角每个角只连了一条边。所以从大矩形一角开始的最长的欧拉路径一定在另一个角结束。因为图上连边的边长都是整数，把这个欧拉路径投影到大矩形的长宽，我们就得到了大矩形至少有一边长为整数。

伊利诺伊大学的Gennady Bachman和贝尔实验室的Mihalis Yannakakis发现了以下扫描线证明：设大矩形为 ，并假设 不是整数。把所有小矩形的下边界去掉，然后对 令 为所有 上边界y坐标不是整数，并且与直线 相交 的小矩形的x方向边长之和。那么 ，而且当 变化的时候，由条件，它一定会变成另一个整数。所以 是整数。而因为 不是整数， 就是最靠上的所有小矩形的宽之和，等于 ，所以 是整数。

用组合中的Sperner引理可得到一个简单证明。假设结论不成立。把每个小矩形画上对角线，然后把所有交叉点 染色：如果 是整数，染X；如果 不是整数但 是整数，染Y；如果都不是整数，染Z。由Sperner引理，三顶点被染不同颜色的三角形有奇数个，但由题目条件这种三角形不存在，矛盾。

还有几种比较长的证明，这里就不讲了，感兴趣可以看原论文。

习题

1. 证明：定理A在如下的弱化条件下也成立：如果小矩形有一个顶点是整点，那么这个小矩形至少有一边长为整数。
2. 证明：如果一个n维长方体（ ）被划分为有限个 有至少k条边是整数 的小n维长方体，那么 中至少有k个是整数。
3. 证明：如果把定理A中的“整数”一词换成“实代数数”（整系数多项式的实根），定理也成立。
4. (Golomb & Robinson) 构造一个定理A在圆环面（ ）上的反例。

原论文：Am. Math. Mon. Vol. 94 No. 7 pp. 601–617。

IMO2011P2 大风车问题

这个看似简单的方法，得分率却如此之低，可见其绝妙之处。

很多选手都会从凸包的角度去考虑，比如去除n个点的凸包（或多次去除）以后在剩下的点中找一点试图证明此点可行，但这就是另外一个较复杂的思路了，可能也是大部分人拿不到此题满分的原因。

现在我比较好奇一个问题：当Δ≥2时，这样的直线是否一定是“不合适的选择”？

用欧拉公式证明高中的排列组合题（大炮打蚊子警告）

在代数拓扑中，对于一个 维复形 ，我们可以定义 为复形 的欧拉示性数。其中 为 中 维单形的数量。

记复形 的 维同调群为 ，我们可以得到著名的欧拉公式（又称欧拉-庞加莱公式）：

在三维情况下，它退化为初中数学中多面体的欧拉公式，即

欧拉公式与欧拉示性数是代数拓扑中一个比较重要的概念。然而有趣的是，这一几何概念可以和排列组合联系起来！

我们可以用欧拉公式证明：

这是一道相当经典的高中排列组合题，当然有初等的证法。事实上我们还可以用代数拓扑的方法证明它。考虑 维单形 ,定义它的闭包复形 。那么 是一个单纯锥，因此 ，而对任意正整数 ，有 。于是根据欧拉公式，复形 的欧拉示性数 。

然后，注意到复形 中 维单形的个数是 （因为相当于 个点中任选 个点），因此其欧拉示性数为 。于是联立上一段的结果，我们得到：

，

即：

，

移项就可以得到我们最终的结果：

这个证明第一次看到的时候感觉还是很神奇的，两个表面上没啥联系的领域居然可以如此结合起来。当然，杀鸡用牛刀，大炮打蚊子也具有别样的快乐（逃

手边恰好有一个非常贴切的例子，是一道IMO的名题：

现有一有限实数列，任意连续7项之和为负，任意连续11项之和为正。问这序列最多可含有多少项。

我强烈推荐在看解答之前，自己思考下；否则，你将错过很多乐趣。

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

现给出如下断言：

这个实数列的长度小于17。

Proof：

假设这个实数列长度 ，则我们可以构造上述矩阵。然而，如果我们依行求和，则 ，因为任意连续7项之和为负；如果我们依列求和，则 ，因为任意连续11项之和为正。显然，矛盾。于是实数列长度 。Q.E.D.

可构造出一个长度为16且符合上述要求的序列： 。

洞察力是多么的重要，省去了多少无用功，直接给出了数列长度的上界。

————————————————————————————————

我原来觉得这个关于上界的证明很妙，但是评论里@寨森Lambda-CDM的解法更加惊为天人。

考虑一个集合, 将其中元素的个数称为集合的基数. 显然, 两个集合基数相等当且仅当其间存在一个双射(一一对应). 定义一个集合的全体子集的集合为该集合的幂集. 以下命题表明, 一个集合与其幂集间不可能存在双射. 注意到集合是其幂集的子集, 于是该命题表明任何集合的基数严格小于其幂集的基数.

(以上证明来自Shen老师的Notes.)

以上证明的核心是一个巧妙的构造, 而稍有常识的人就会发现这和罗素悖论密切相关.