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

概率论并不仅仅是用来算算概率的。有些时候，概率论远比我们想象中的更强大。

考虑这样一个问题。考虑集合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(http://en.wikipedia.org/wiki/Probabilistic_combinatorics)上给出了另一个经典的概率法证明，问题仍然与染色有关。

或许大家经常听到这样一个结论：六个人在会议上握手，则存在三个两两之间都握过手，或者两两之间都没握手的人。一种更夸张的说法是，假设好友关系是双向的，那么世界上任何六个人之间或者存在三个两两都是好友的人，或者存在三个两两都不是好友的人。用图论的话说，对完全图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年，Erdős的一个经典证明告诉我们，随着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) ≥ 2^C(r,2)。不等式右边是r(r-1)/2个2相乘的结果，不等式左边却还不及n^r，满足上述不等式至少得先保证n^r > 2^(r(r-1)/2)，这里n至少得有2^((r-1)/2)，这就足以说明n是指数级别增长的了。

很多存在性问题的证明方法都不是构造性的，它虽然证明了满足某种性质的数学对象是存在的，但并没有得出构造该数学对象的方法。利用概率进行证明往往都是非构造的，虽然证到了结论，究竟该如何寻找一个不含单色K_r子图的着色方案，这个问题直到今天仍然没有解决。

Erdős似乎是很喜欢概率法证明，最经典的一些概率证明都来源于Erdős。我们再来看一个比较复杂的例子。

空间中的n个点确定了3·C(n,3)个角。随着n的增加，这些角不可能永远都只有锐角，总会有一个直角或者钝角冒出来。在平面上，只确定锐角的点集最多只能有三个点，摆放四个点将不可避免地产生直角或钝角。在三维空间中，五个点已经是最好的结果了（上图），可以证明六个点里无论如何都含有直角或钝角。Danzer和Grünbaum猜想：在d维空间中只含锐角的最大点集为2d-1。这个猜想始终未被证明。21年后，Paul Erdős和Zoltán Füredi推翻了这个猜想。他们用一个非构造性的证明说明，你可以从34维立方体的顶点中选取72个点，使得它们只确定出锐角。事实上，他们利用概率论证明了这样一个非概率性的事实：在d维空间中，存在一个大小为2 · [(√6/9) · (2/√3)^d]点集S⊆{0,1}^d，使得该点集所确定的角都是锐角（[x]是取x的下整的意思）。

令m=[(√6/9) · (2/√3)^d]，然后随机选取3m个0/1向量

x(1), x(2), …, x(3m) ∈ {0,1}^d

显然，这些点所构成的角只可能是锐角或直角。向量x(i), x(j), x(k)确定一个以x(j)为顶点的直角当且仅当x(i)-x(j)与x(k)-x(j)的点积为0，换句话说对所有的坐标维l≤d都满足要么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 = m^3 · (81/6) · (3/4)^d = m^3 · (9/√6)^2 · (√3/2)^(2d) ≤ m

也就是说，问题组的数目不超过m个。既然这样，我们就可以去掉每个三元组中的其中一个向量（一共去掉了m个向量），破坏掉仅有的问题组，使得剩下的2m个向量中不含任一问题组。这就是一个大小为2 · [(√6/9) · (2/√3)^d]的只确定了锐角的点集。