混沌与秩序出版时间（拉姆齐定理告诉了我们什么）
混沌与秩序出版时间（拉姆齐定理告诉了我们什么）1，2，3，4，5，6，7，8首先看一个代数的例子。我们从 1 依次开始往后写正整数，假设我们有红黑两种颜色的笔，在每个整数写好的整数上涂上红色或者黑色。如果想要一定会出现一个长度是3同色的等差数列，问至少要写到几？答案是 9。显然，这里的临界值是 8。临界状态有很多，我们呈现其中一种，如下（下面的2、4、5、7涂上红色)再换一套语言来理解鸽笼原理。假设有 n 种颜色用来给鸽子上色，如果要保证一定出现“同色”鸽子，问至少需要多少只鸽子？答案还是 n 1。再换一套语言。假设有 A B 两 个集合，其中集合B中有n个元素(即势为n)。现在从集合 A 向集合 B 作映射 f，如果要保证一定会出现 f(a) = f(b)，问集合A的元素个数至少是多少个？答案还是 n 1。从这个角度看，鸽笼原理，以至拉姆齐理论其实是在探讨这样的问题：如何从不确定性中抽取出确定性，或者说如何从混沌（Chaos）中
电影《美丽心灵》中有一段非常浪漫的场景：纳什和艾丽西亚站在喷泉边，仰望星空，艾丽西亚说自己曾数星星数到了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猜想说：至少需要 n-2 个点（任意三点不共线），才能保证最终的构型一定会出现凸 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%。更多细节，欢迎查询生日悖论。
所以如果从概率的角度看鸽笼原理，可以更精细地看到这种不确定性到确定性的转化过程。事实上，概率方法作为组合数学中非常前沿的一类方法，应用非常广泛，包括很多拉姆齐理论的具体结论都可以用概率方法来证明。
来源：哆嗒数学网
编辑：AI
近期热门文章Top10
↓ 点击标题即可查看 ↓
1. 掉入地下一万米
2. 从前有个学生熬夜迟到了，错把困扰数学家的难题当作业做了出来
3. 原子弹制造指南
4. 吸猫一时爽，一直吸猫一直爽
5. 为什么长时间不洗头，洗的时候搓不出很多泡沫？| No.145
6. 一个大活人，还能让尿活活憋死？？？
7. 所以，WiFi 和 4G 到底哪个更耗电？
8. 传纸条被发现，一看竟写着...
9. 铅笔上面那块废柴橡皮为什么容易把纸擦破？
10. 一幅图读懂量子力学（薛定谔的猫）
