摘要：答案非常出乎意料，不是 365，364，。納什之所以自信可以畫出任意的形狀，是因爲星星的數量非常巨大，因此可以保證一定會出現想要的形狀。

作者，張明智。

關注 哆嗒數學網 每天獲得更多數學趣文

電影《美麗心靈》中有一段非常浪漫的場景：納什和艾麗西亞站在噴泉邊，仰望星空， 艾麗西亞說自己曾數星星數到了 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%。更多細節，歡迎查詢生日悖論。

所以如果從概率的角度看鴿籠原理，可以更精細地看到這種不確定性到確定性的轉化過程。事實上，概率方法作爲組合數學中非常前沿的一類方法，應用非常廣泛，包括很多拉姆齊理論的具體結論都可以用概率方法來證明。

關注 哆嗒數學網 每天獲得更多數學趣文