电影《美丽心灵》中有一段非常浪漫的场景:纳什和艾丽西亚站在喷泉边,仰望星空,艾丽西亚说自己曾数星星数到了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(限制条件的线性函数),这也是为什么看起来鸽笼原理好像是带余除法的应用。