来自天书的证明(二):简洁,思想的力量

本文遵守首页上的CC版权声明,转载请注明作者与出处,谢谢!

作者:fwjmath

真正巧妙有思想的证明很多都不长,下面就说几个书中的例子。

定理:有n个顶点的没有三角形的图G的边数小于等于 n^2/4,等号当且仅当n是偶数且G是完全二部图K(n/2,n/2)。

这个定理在很多书里边都有讲证明,通常都是将柯西不等式应用到顶点度数上的。现在在这里我们给出一个只需要用均值不等式的证明。

证明:设G(V,E)为符合条件的图,A为G的最大独立集(独立集指的是集合中的顶点两两不邻接),a是G的点独立数(就是A的元素个数)。令 b = n – a。因为G中没有三角形,对于每个顶点 i,与之邻接的顶点构成一个独立集,这样的话我们对于所有顶点 i 有d(i) <= a。令集合B = V A,|B| = b。容易知道任一条G中的边至少有一端顶点在B中(如果有一条边两端顶点都在A中的话这两个顶点就邻接,这违反了独立集的定义)。这样的话我们有以下的不等式:

image

等号成立当且仅当a=b且每个顶点i的度数都为a,也就是说当且仅当n是偶数且G是完全二部图K(n/2,n/2)。证毕。

这个证明显然比用柯西不等式的证法简明而又有思想性。

再来举个例子。

对于任意集合E,如果它的一个子集族F满足对于任意一对元素x和y(都是E的子集),x和y互不包含,则我们把这样的子集族称为Sperner族。

Sperner 定理:对于n元集E上的Sperner族S,我们有:

image

以下证明来自Wiki。

证明(Lubell, D.):令sk为S中k元集的个数,0 ≤ k ≤ n。

由二项式系数的极值在中央的结论,我们有:image 。对k求和,我们有:image

由于S是一个Sperner族,任意一对子集不互相包含。这样的话我们定义以下这样一个游戏:从空集开始,如果当前集合不在S中的话,就在当前集合中任意加上一个E中的元素,继续这个游戏,直到当前集合为E,如果E属于S的话游戏失败,否则游戏成功。如果当前集合在S中的话,游戏失败停止。这样的话,在当前集合为k元集的时候,游戏失败停止的概率恰好是image,而且由于S是Sperner族,所以对于不同的k这个事件是独立的,失败的总概率就是对于前面的式子对k求和。由概率的性质我们可以得到: image 。(这个概率证明是我刚刚想出来的~~~)

这样的话结合两个不等式,我们有:image ,于是image 。证毕。

继续来一个有关子集族的例子。

定理:设集合X元素个数为n。令F是满足以下条件的一个子集族:对于X中任意一对元素x,y,F中存在且仅存在一个子集同时包含这两个元素。设F元素个数为m,则m >= n。

证明(Motzkin 与 Conway):对于X中任意元素x,定义rx为子集族F中包含x的子集的个数。容易知道2 <= rx < m。对于F中的任意子集Ai,如果x不属于Ai的话,因为同时包含x和Ai中的任一元素的子集必须互不相同(否则有一对Ai中的元素同时又在另一个集合出现,与定义矛盾),所以我们有 rx >=|Ai|。如果 m < n 的话,对于x不属于Ai我们有:

image

然后我们有:

image

这显然是荒谬的。故 m>= n,证毕。

最后看一个数论的例子,稍微有些冗长,但是思想还是很不错的。

命题:任意形如 4m+1 的质数均可表为两个完全平方数的和。

证明(Roger Heath-Brown):考虑集合

image

显然这个集合是有限集。

考虑映射image ,显然这个映射是对合的。

再考虑以下两个集合

image

容易验证,f将T映射到ST,将U映射到SU。这样的话由映射f的对合性,我们知道T和U的元素个数正好是S的一半,于是|T|=|U|。

再考虑映射image ,容易验证g的确是一个映射,而且也是对合的。

但g有且仅有一个不动点,那就是 x = (p – 1) / 4, y = z = 1。这个是容易通过解方程组得出的。

这样的话,我们可以知道U的元素个数是奇数,因为如果将U中的元素(x, y, z)与g(x, y, z)配对的话,最后就剩下一个。这样的话T的元素个数也是奇数。

最后考虑映射image ,容易看出这也是一个对合的映射。由于T的元素个数是奇数,所以h必定至少有一个不动点。所以T中存在这样的元素(x’, y’, z’)使得x’=y’。这样的话我们有p = (2x’)² + z’²。这就是p的一个平方和表示。证毕。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s