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

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

电影《美丽心灵》中有一段非常浪漫的场景：纳什和艾丽西亚站在喷泉边，仰望星空， 艾丽西亚说自己曾数星星数到了 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%。更多细节，欢迎查询生日悖论。

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