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

 

作者,张明智


关注 哆嗒数学网 每天获得更多数学趣文

 

 

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

 

 

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

 

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

 

 

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

 

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

 

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

 

 

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

 

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

):

 

12345678

 

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

 

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

 

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

 

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

 

 

 

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

 

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

 

 

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

 

 

 

关注 哆嗒数学网 每天获得更多数学趣文

 

标签: none

评论已关闭