您当前的位置:首页 > 学习 > 阅览室

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

时间:12-06来源:作者:点击数:

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

考虑这样一个问题。考虑集合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年,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]的只确定了锐角的点集。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门