「鸽笼临界值」拉姆齐法则详解(拉姆齐定理告诉了我们什么)

互联网 2022-03-22 17:26:37

今天,神州网给大家普及下关于「鸽笼临界值」拉姆齐法则详解(拉姆齐定理告诉了我们什么)的知识。

电影《美丽心灵》中有一段非常浪漫的场景:纳什和艾丽西亚站在喷泉边,仰望星空, 艾丽西亚说自己曾数星星数到了 4348 颗,纳什笑着回复,咱俩真是一对怪胎。接着,纳什 让艾丽西亚选一个形状,动物随便什么都可以。艾丽西亚想了想说,雨伞。纳什走到艾丽 西亚背后,拿起她的手,在星空中用星星连出一个雨伞的形状。艾丽西亚芳心瞬间被俘获, 于是央求:再来一次,再来一次嘛!来画个章鱼!

混沌与秩序:拉姆齐定理告诉了我们什么?

姑且不论纳什是否做过这么浪漫的事,也不论纳什是否有这样的本领;假如是真的, 我们想问的是,纳什为什么自信可以用星星连出任意的形状呢?答案或许藏在一个数学理论中,这就是组合数学中的拉姆齐理论(Ramsey Theory)。

拉姆齐理论的核心可以概括成:完全的无序是不可能的。更具体的,Ramsey 理论中 典型的问题是:为了保证在某个集合(或系统)中有某种性质(或结构)一定出现,这个 集合的元素个数应该达到多少?从最初的拉姆齐定理到后来发展出的众多拉姆齐型定理都表明:一个集合只要元素数量达到某个临界值后,一定会出现我们预先定义好的某种 性质或结构。纳什之所以自信可以画出任意的形状,是因为星星的数量非常巨大,因此可以保证一定会出现想要的形状。除此之外,我们熟悉的鸽笼原理也是拉姆齐理论的一个例子。

鸽笼原理传统的理解是,n + 1 只鸽子飞进 n 个鸽笼,一定会有一个鸽笼里面至少有两只鸽子。如果遵循 Ramsey 理论的思想,我们可以把鸽笼原理换一种方式理解:给定 n 个鸽笼,如果想要鸽子“同笼”一定发生,那我们至少需要多少只鸽子?答案是 n + 1。

再换一套语言来理解鸽笼原理。假设有 n 种颜色用来给鸽子上色,如果要保证一定出现“同色”鸽子,问至少需要多少只鸽子?答案还是 n+1。

再换一套语言。假设有 A,B 两 个集合,其中集合B中有n个元素(即势为n)。现在从集合 A 向集合 B 作映射 f,如果要保证一定会出现 f(a) = f(b),问集合A的元素个数至少是多少个?答案还是 n + 1。

从这个角度看,鸽笼原理,以至拉姆齐理论其实是在探讨这样的问题:如何从不确定性中抽取出确定性,或者说如何从混沌(Chaos)中找到秩序(Order)。不确定性是说鸽子飞进鸽笼鸽子的染色方案看成映射,因为不同的映射构成一个随机事件的空间,有些随机事件满足我们想要的性质,有些则不能;另一方面,如果我们扩张这个空间,则想要的确定性就一定会出现。这个转变一定会有一个临界状态和临界值,就像水结冰对应的临界状态是冰水混合,对应的临界值是 0°C 一样。在鸽笼原理中,因为我们想要的性质比较简单,这个临界状态正好是鸽子占满鸽笼且均匀分布在鸽笼中,因此对应的临界值是 n(限制条件的线性函数),这也是为什么看起来鸽笼原理好像是带余除法的应用。

首先看一个代数的例子。我们从 1 依次开始往后写正整数,假设我们有红黑两种颜色的笔,在每个整数写好的整数上涂上红色或者黑色。如果想要一定会出现一个长度是3同色的等差数列,问至少要写到几?答案是 9。显然,这里的临 界值是 8。临界状态有很多,我们呈现其中一种,如下(下面的2、4、5、7涂上红色,部分平台不显示颜色,请自行脑补)

):

1,2,3,4,5,6,7,8

对于这个临界状态,如果再添加一个 9,我们来看一下是否一定会出现长度为3的同色等差数列。

首先假如 9 是用红笔写的,那么在1,2,3,4,5,6,7,8,9中,5,7,9 构成了一个长度为3的的等差数列,从而满足要求;如果 9 是用黑笔写的,那么数列就变成了 1,2,3,4,5,6,7,8,9其中3,6,9 构成一个长度为3的的等差数列,也满足要求。

这个结论是 Van der Waerden 定理的一个特例,这里我们只是用一种临界状态说明了 下结论,定理完整的证明远为复杂。不过从这个例子可以看出,我们依旧想从巨大的混沌中找到秩序,而且我们是一定能找到的,只要这个系统足够大。

再看一个几何的例子。假设欧式空间的平面上散布着一些点,满足任何三个点都不共线。在任意两点之间连线段,如果想要最终的图形一定会包含一个凸n边形,至少需要多少个点?我们不妨从最简单的情形开始考虑。n = 3 时,显然只要 3 个点就一定会出现三 角形;n = 4 时,相应的临界值是4,也就是说至少需要5个点才能保证一定会出现凸4边形;n = 5 时,相应的临界值是 8。下面两个图分别是 n = 4 和 n = 5 的临界状态:

混沌与秩序:拉姆齐定理告诉了我们什么?

混沌与秩序:拉姆齐定理告诉了我们什么?

对于一般的 n,Erdos−Szekeres猜想说:至少需要 2^(n−1) + 1 个点(任意三点不共线),才能保证最终的构型一定会出现凸 n 边形(x^y表示x的y次方)。这个猜想至今未解决,最新的进展是 Andrew Suk 于2016 年发在《美国数学会杂志》的文章,他证明了至少需要 2^(n+o(n)) 个点。

最后再回到鸽笼原理。根据鸽笼原理我们知道,367 个人里面一定会有两个人生日是同一天,所以“同日生”这种秩序/确定性所对应的临界值是 366。所谓确定性就是说这个事件的发生概率是 1,如果我们把这种确定性的要求稍微降低下,改成“同日生”的概率 是 99.9%,也就是说只要有两个人他们同日生的概率达到 99.9% 就可以,那这个时候对应的临界值是多少呢?答案非常出乎意料,不是 365,364,……,而是69,也就是说 70 个人 里面有两个人同日生的概率是 99.9%。更多细节,欢迎查询生日悖论。

所以如果从概率的角度看鸽笼原理,可以更精细地看到这种不确定性到确定性的转化过程。事实上,概率方法作为组合数学中非常前沿的一类方法,应用非常广泛,包括很多拉姆齐理论的具体结论都可以用概率方法来证明。