来自天书的证明(三):利用概率证明存在性

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

作者:fwjmath

利用概率解题,即使在奥赛中也少有。但这不表明概率就不能解题。大家应该很熟悉以下的问题:

在一个2×2的表格中染n种颜色,要求有公共边的格不能染同一种颜色,求染色方案数。

这个题目很容易,答案就是 C(n, 4) + C(n, 3) + C(n, 2)。但是这个题目也可以用概率解决。首先,第一格有n种选择,然后与之相邻的两格都有 n – 1 种选择。这两格颜色相同的概率是 1 / (n – 1),于是最后一格能取的颜色的期望值就是 ((n – 3)(n – 2) / (n – 1) + 1)。这样的话染色方案数就是 n * (n – 1) * (n – 1) * ((n – 3)(n – 2) / (n – 1) + 1) = C(n, 4) + C(n, 3) + C(n, 2)。我们用概率方法也得出了同样的答案。

又比如说这个问题:1xn的表格染k种颜色,要求有公共边的格不能染同一种颜色,求染色方案数。

答案显然是k*(k-1)^(n-1)。用概率的方法也很好算。任意染色,任意相邻两格不同色的概率是(1 – 1 / n),这样的话因为有(n – 1)个相邻的位置,所以总数是(k ^ n) * (1 – 1 / n) ^ (n – 1) = k*(k-1)^(n-1)。

也许你会说这只不过是一般的计算方法的变形而已,但是在某些存在性问题当中,概率方法是很有效的。Erdos就以将概率方法应用到各种各样的地方而著称。事实上,概率方法也许就是他最先引入并且广泛使用的。这种方法的原则很简单:

如果给定一个集合,里边不存在符合某种条件的对象的概率小于1,那么里边一定存在一个对象符合这个条件。

这是显然的。但正是因为有了这个思想,我们才得以证明一些有趣的结论。

定理:对于集合X的子集族F,如果F中的子集都是d元集而且|F| < 2 ^ d的话,则必存在对X中元素的一个二染色,使对于F中的任意X的子集中均包含两种颜色的元素。

证明:随机对X中元素等可能二染色。对于F中的一个子集A,令EA为“A中元素染同色”这个事件。由于A是d元集,而染色又是等可能的,所以我们有:P(EA) = (1 / 2) ^ (d – 1)。又因为m = |F| <= 2 ^ (d – 1),于是我们有:

image

所以必定存在一个符合要求的二染色。证毕。

这个证明还是很简洁的。

下面我们再来看一个关于组合数学的一个重要问题——Ramsey数——的定理。首先我们来简单解释一下Ramsey数。如果对一个完全图Kn的边任意染红色和蓝色,必定存在一个边全是红色的a阶完全图或者是一个边全是蓝色的b阶完全图的话,我们将n的最小值记作R(a, b)。这就是Ramsey数的定义。

定理(Erdos):对于任意 k >= 2,我们有R(k, k) >= 2 ^ (k / 2)。

这个下界看似简单而宽泛,但到目前为止仍然没有人推进它。

证明:对于k=2, 3,容易验证下界成立。

假设 k >= 4。设 N < 2 ^ (k / 2)。我们对完全图KN进行边的随机等可能红蓝染色。这样的话每种染色方案的出现概率都是image 。令A是一个由k个顶点组成的集合。定义事件AR为“联结A中顶点的边都被染红色”。容易知道image 。这样的话,令pR为存在边全被染成红色的k阶完全图的概率,我们有:

image

由于N < 2 ^ (k / 2),k >= 4,我们有以下的不等式:

image

这样的话我们有pR < 1 / 2,对称地,存在边全被染成蓝色的k阶完全图的概率pB也有pB < 1 / 2。这样的话,pR + pB < 1,也就是说必存在一个染色,使KN中既没有全红的k阶完全子图也没有全蓝的k阶完全子图。换言之,R(k, k) > N。由于N < 2 ^ (k / 2),我们有R(k, k) >= 2 ^ (k / 2)。证毕。

这是Erdos的得意之作之一。

后记:终于写完这个系列了~~~花了一天的时间把书中的证明抄上来了~~~真累~~~途中还补了次证明~~~

Advertisements

4 thoughts on “来自天书的证明(三):利用概率证明存在性

  1. 这个数学公式难看了一点如果你懂latex的话,这个可能能让你写得轻松点:http://zhiqiang.org/bbs/topic/1。就是输入latex表达式,系统会帮你转换成图片,你可以在这边直接用。

  2. 用的是公式编辑器~~~的确不怎么样~~~而且截图有些麻烦~~~现学现用LaTeX也不是说不行~~~但是我想找个小软件~~~能生成公式就可以了~~~

发表评论

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