经典证明：几个利用概率法进行证明的例子.doc

经典证明：几个利用概率法进行证明的例子概率论并不仅仅是用来算算概率的。有些时候，概率论远比我们想象中的更强大。考虑这样一个问题。考虑集合X上的一个集合族，集合族中的所有集合大小均为d。我们说这个集合族是可以二染色的，如果对X的元素进行适当的红蓝二着色之后，每个集合里面都包含了两种颜色的元素。例如，当d=3时，1,2,3, 1,2,4, 1,3,4, 2,3,5就是可二染色的，把1、2染成红色，把3、4、5染成蓝色，则每个集合里都含有两种颜色。是否存在d=3的不可二染色集族呢？这样的集族当然是存在的，例如取集合1,2,3,4,5的全部C(5,3)个元素个数为3的子集，则无论如何染色，总会有一个集合里面的元素全是一种颜色。上述推理立即告诉我们，对于一个给定的d，一定存在一个集合个数为C(2d-1, d)的不可二染色集族。这个数目还能再少吗？我们想知道，不可二染色集族中的集合个数最少可以少到什么地步。一个极其简单的证明给出了一个下界：集族的大小一定大于2(d-1)。当d=3时，你一辈子也不能构造一个不可二染色集族，里面只含4个集合。为了证明这一点，不妨对X中的所有元素进行随机着色，每个元素取成红色和蓝色的概率均等。那么，一个元素个数为d的集合中，所有元素均为一种颜色的概率就应该是1/2(d-1)。如果集族内的集合个数只有不到2(d-1)个，那么即使“集合中是否只有一种颜色”是互相独立的，这些事件的并（至少有一个集合内只有一种颜色）的概率也不超过2(d-1) * 1/2(d-1) = 1，何况这些事件还不是独立的，因此存在单色集合的概率必然小于1。这个概率值小于1说明什么？这说明，“至少有一个单色集合”并不是必然事件，一定有一种染色方案使得每个元素里都含两种颜色，换句话说该集族可以被二染色。这种证明方法奇就奇在，利用概率论进行推理得到的结果居然是一个确定的结论。Wikipedia上给出了另一个经典的概率法证明，问题仍然与染色有关。或许大家经常听到这样一个结论：六个人在会议上握手，则存在三个两两之间都握过手，或者两两之间都没握手的人。一种更夸张的说法是，假设好友关系是双向的，那么世界上任何六个人之间或者存在三个两两都是好友的人，或者存在三个两两都不是好友的人。用图论的话说，对完全图K_6的边进行红蓝二着色，则图中一定存在一个单色的（所有边都是一种颜色的）同构于K_3的子图。K_6已经是能够满足此要求的最小完全图了，你可以尝试构造一个K_5的边二着色，使得图中不含单色的K_3子图。1930年，Frank P. Ramsey证明了，对于一个给定的r，总存在一个足够大的n，使得K_n的边二着色一定含有单色的K_r子图。这就是著名的Ramsey定理。Ramsey定理给出了n的一个上界，不过n的下界又是多少呢？1947年，Erds的一个经典证明告诉我们，随着r的增加，n至少是指数级的增长。为了证明这一点，我们随机给完全图K_n进行着色，每条边都有1/2的概率取红色，1/2的概率取蓝色。一个K_r子图的所有边都为红色或者都为蓝色，其概率为2(1/2)C(r,2)。那么对于所有C(n,r)个不同的K_r子图，单色子图个数的期望值即为C(n,r) 2(1/2)C(r,2)。想想看，如果上面这个期望值小于1的话说明什么？这表明，不是所有着色方案都含有单色K_r子图，至少存在一种着色方案，它的单色K_r子图个数为0。因此，为了保证所有着色方案中都存在至少一个单色K_r子图，我们必须保证这个期望值大于等于1，也即2 C(n,r) 2C(r,2)。不等式右边是r(r-1)/2个2相乘的结果，不等式左边却还不及nr，满足上述不等式至少得先保证nr 2(r(r-1)/2)，这里n至少得有2(r-1)/2)，这就足以说明n是指数级别增长的了。很多存在性问题的证明方法都不是构造性的，它虽然证明了满足某种性质的数学对象是存在的，但并没有得出构造该数学对象的方法。利用概率进行证明往往都是非构造的，虽然证到了结论，究竟该如何寻找一个不含单色K_r子图的着色方案，这个问题直到今天仍然没有解决。Erds似乎是很喜欢概率法证明，最经典的一些概率证明都来源于Erds。我们再来看一个比较复杂的例子。空间中的n个点确定了3C(n,3)个角。随着n的增加，这些角不可能永远都只有锐角，总会有一个直角或者钝角冒出来。在平面上，只确定锐角的点集最多只能有三个点，摆放四个点将不可避免地产生直角或钝角。在三维空间中，五个点已经是最好的结果了（上图），可以证明六个点里无论如何都含有直角或钝角。Danzer和Grnbaum猜想：在d维空间中只含锐角的最大点集为2d-1。这个猜想始终未被证明。21年后，Paul Erds和Zoltn Fredi推翻了这个猜想。他们用一个非构造性的证明说明，你可以从34维立方体的顶点中选取72个点，使得它们只确定出锐角。事实上，他们利用概率论证明了这样一个非概率性的事实：在d维空间中，存在一个大小为2 (6/9) (2/3)d点集S0,1d，使得该点集所确定的角都是锐角（x是取x的下整的意思）。令m=(6/9) (2/3)d，然后随机选取3m个0/1向量x(1), x(2), ., x(3m) 0,1d显然，这些点所构成的角只可能是锐角或直角。向量x(i), x(j), x(k)确定一个以x(j)为顶点的直角当且仅当x(i)-x(j)与x(k)-x(j)的点积为0，换句话说对所有的坐标维ld都满足要么x(i)和x(j)的第l个坐标相等，要么x(k)和x(j)的第l个坐标相等。不妨把x(i)的第l个坐标记为x(i)l，则上述条件就可以写成x(i)l=x(j)l或x(k)l=x(j)l。我们把满足该条件的三元组(i,j,k)叫做一个“问题组”。注意，我们随机取向量时有可能取到重复的，当发生x(i)=x(j)或者x(k)=x(j)时，对应的角并不存在，但它显然也属于一个问题组。在某一坐标l上，x(j)l既不等于x(i)l也不等于x(k)l只有两种情况，既x(i)l=x(k)l=0且x(j)l=1，以及x(i)l=x(k)l=1且x(j)l=0。这占了所有8种情况的1/4。由于所有向量的所有坐标都是独立选取的，因此三个向量形成问题组的概率就应该是(3/4)d。空间中的n个点确定了3 C(n,3)个角，因此问题组个数的期望值就应该是3 C(3m,3) (3/4)d。既然期望值是这么多，这说明至少存在一种向量的取法，使得问题组的个数最多只有3 C(3m,3) (3/4)d。然而3 C(3m,3) (3/4)d 3 (3m)3 (3/4)d / 6= m3 (81/6)