Featured image of post 拉姆齊理論：混亂之中必有秩序——以雙色圖解證明 6 人的人際關係
數學

拉姆齊理論：混亂之中必有秩序——以雙色圖解證明 6 人的人際關係

只要聚集 6 個人，就必然存在 3 個互相認識的人，或是 3 個互相不認識的人。本文透過雙色圖解證明拉姆齊數 R(3,3)=6，剖析 5 人的反例、完整驗證全部 32768 種著色情形，並延伸探討數列與網路中的實際應用。

1. 6 人齊聚，必定能找到的 3 人小組

假設在一場派對中聚集了 6 個人。其中可能有人是老朋友，也可能有人是初次見面。無論誰與誰互相認識，其人際關係多麼錯綜複雜，都無所謂。即便如此，以下兩種情況也必定至少有一種成立：

  • 任選其中 2 人，彼此都是互相認識的 3 人組。
  • 任選其中 2 人，彼此都是互不相識的 3 人組。

這並不是「通常能找到」，而是無論你如何安排他們之間的關係，都毫無例外、必然存在。此外，「6 人」這個數字是最小的。如果只有 5 個人，完全可以構造出一種人際關係配置，使得上述兩種 3 人小組都不存在。

這個小小的驚奇，就是通往 拉姆齊理論（Ramsey Theory） 的入口。無論多麼複雜地劃分一個龐大的結構，只要整體的規模足夠大，就絕對無法完全避開具備特定規律的小型結構。這正是拉姆齊理論所探討的——「不可避免的規律性」。

然而，這並不意味著混亂之中會隨意浮現出任何你想要的規律。只有當我們明確了以什麼為研究對象、劃分成幾種類別、以及要尋找何種結構時，它才會成為嚴謹的數學命題。現在，就讓我們從紙上畫出 6 個點這個親切直觀的例子開始吧。

2. 將人際關係轉化為紅線與藍線

模型的約定

在本文中，我們將「認識」視為一種對稱關係。也就是說，若 A 認識 B，則 B 也認識 A；且每一對人之間，必然能明確歸類為「互相認識」或「互不相識」的其中一種。

單方面僅知道對方名字的關係，或是無法確定是否認識的模糊關係，均不包含在此模型中。此外，「互不相識」也並不代表「討厭對方」或「處於敵對狀態」。

我們將每個人抽象化為點，並將兩人之間的關係抽象化為線。

圖形要素意義
點（頂點）1 位參與者
紅色實線兩人彼此認識
藍色虛線兩人彼此不認識
由 3 條同色邊組成的三角形我們正在尋找的 3 人小組

由於所有人兩兩之間都連上了一條線，因此這在圖論中被稱為 完全圖（Complete Graph） 。頂點數為 $n$ 的完全圖記作 $K_n$，其邊的數量如下：

$$ \binom{n}{2}=\frac{n(n-1)}{2} $$

如果有 6 個人，邊數就是 15 條。請注意，僅僅「A 認識 B 且 A 認識 C」，並不代表這 3 個人彼此都互相認識，因為 B 與 C 之間也必須是紅線。請務必牢記：條件是三角形的 全部 3 條邊 都必須是同一種顏色。

在下文中，我們將全部為紅色或全部為藍色的三角形稱為 單色三角形（Monochromatic Triangle） 。為了讓不易分辨顏色的讀者也能輕鬆閱讀，圖解中以實線表示紅色，以虛線表示藍色。

3. 證明 6 個人時必然能找到

在本次證明中，我們唯一需要的工具就是 鴿籠原理。我們只需運用一個極其樸素的事實：「將 5 個物體分成 2 類，則至少有一類會分到 3 個或以上」。

步驟 1：只聚焦於其中 1 個人

在 6 個人當中，我們任選 1 人，稱之為 A。從 A 出發，連接到其餘 5 個人共有 5 條線。因為每條線非紅即藍，所以根據鴿籠原理，至少有 3 條線是同一種顏色。

$$ \left\lceil\frac{5}{2}\right\rceil=3 $$

這裡的 $\lceil x\rceil$ 表示大於或等於 $x$ 的最小整數（天花板函數）。也可以換個角度思考：如果紅線和藍線都只有 2 條或更少，總共最多只有 4 條線，根本無法塗滿全部 5 條線。

我們不妨假設至少有 3 條是紅線，並將這些紅線所連向的 3 個人分別稱為 B、C、D。此時，A–B、A–C、A–D 全都是紅線。如果在開頭發現的是至少 3 條藍線，只需將後續討論中的紅色與藍色對調，論證過程完全相同。

步驟 2：觀察 B、C、D 之間的關係

對於 B–C、B–D、C–D 這 3 條線，只存在以下兩種可能：

情況 ①：至少有 1 條是紅線。 例如，若 B–C 是紅線，由於 A–B 與 A–C 也都是紅線，因此 A、B、C 便構成了一個全紅的三角形。此時其餘 2 條線是什麼顏色都完全不影響結果。

情況 ②：1 條紅線也沒有。 這意味著 B–C、B–D、C–D 全都是藍線。如此一來，B、C、D 便構成了一個全藍的三角形。

從 A 出發選取 3 條同色邊，若其連接的 3 人之間有紅線則形成紅色三角形，若無則形成藍色三角形的證明圖解

圖中的灰色邊以及省略未畫出的邊，是證明過程中無需確定顏色的部分。在實際的完全圖中，它們同樣會被塗上紅色或藍色。

至此，我們便證明了無論如何著色，都必然存在單色三角形。我們根本不需要去逐一檢查全部 15 條邊。 僅憑從 1 個人出發的 5 條邊，以及其所連接的 3 個人之間的相互關係，就涵蓋了所有的可能性。 大學教材解說

4. 為什麼 5 個人是不夠的？

「6 個人就足夠」與「6 個人是最小值」，是兩個不同的命題。若要證明 6 是最小值，就必須構造出一個 5 個人時不滿足條件的反例。

我們將 5 個人放置在正五邊形的 5 個頂點上。讓相鄰的人之間——也就是五邊形外圍的 5 條邊——塗成紅色；而內部剩下的 5 條對角線，則全部塗成藍色。

將五邊形外圍塗成紅色、對角線塗成藍色的 5 人反例。兩種顏色中均不存在三角形

若只看紅色邊，它是一個沿著五邊形繞行一圈的環。任選 3 個人，都無法單純依靠紅色邊封閉構成一個三角形。若只看藍色邊，它呈現出星形（五角星），但只要重新調整頂點的走訪順序，它同樣也是一個環繞 5 個頂點一圈的五邊形環。因此，藍色邊中同樣沒有三角形。

請注意，星形內部的線段交點並不是新的頂點。對應於人的只有 A 到 E 這 5 個點。即使線段交叉在視覺上似乎形成了小三角形，但那並不是本問題中所定義的三角形。

由於既能避開全紅的 3 人組，也能避開全藍的 3 人組，因此 5 個人無法保證該結論成立。結合前面「6 個人必定成立」的結論，我們便能確定最小人數就是 6。

5. 這個「最小規模」被稱為拉姆齊數

當我們將完全圖的邊塗上紅色或藍色時，必定會出現紅色 $K_s$ 或藍色 $K_t$ 的最小頂點數，記為 拉姆齊數（Ramsey Number） $R(s,t)$。

所謂紅色的 $K_s$，是指在所選出的 $s$ 個頂點之間，所有的邊都是紅色的；僅僅是透過紅色路徑連通是遠遠不夠的。由於 $K_3$ 就是三角形，因此到目前為止我們得到的結論可以寫成下面這一行：

$$ R(3,3)=6 $$

拉姆齊定理指出：對於任意給定且固定的有限整數 $s,t$，必然存在這樣一個有限的數。然而，「存在這樣一個數」與「能輕易求出其最小值」完全是兩回事。儘管三角形情況的證明十分簡短，但只要稍微擴大尋找單色群體的大小，計算難度就會急劇上升。

對於基本的天花板（上界），存在以下遞迴不等式關係：

$$ R(s,t)\leq R(s-1,t)+R(s,t-1) \qquad(s,t\geq3) $$

設右式為 $N$，我們從 $N$ 個頂點中任選 1 個頂點。若從該頂點以紅線相連的頂點數達到 $R(s-1,t)$ 個以上，則在這些頂點中必然存在紅色的 $K_{s-1}$ 或藍色的 $K_t$。若是前者，只要加上原本選取的頂點，就能構成紅色的 $K_s$；若是後者，則直接達成目標。

如果紅線連接的頂點沒有那麼多，那麼以藍線相連的頂點數就至少會有 $R(s,t-1)$ 個。此時只需將相同的推導反過來應用於藍色即可。這本質上也是「聚焦於 1 個頂點，收集相同顏色鄰居」這一證明思路的推廣。

若從邊界值 $R(2,t)=t$ 與 $R(s,2)=s$ 出發，便能透過此遞迴關係依序建構出有限的上界。然而，由於這是不等式，所得到的數值並不一定是最小值。清楚區分「能夠給出保證的規模」與「真正必需的最小值」，是極為重要的。

6. 「幾乎必然」與「毫無例外必然」截然不同

現在我們來做一個實驗：假設每條邊各自獨立地以 $1/2$ 的機率塗成紅色或藍色。雖然這個機率模型對於純數學證明並非必需，但它能幫助我們觀察結果上的差異。

若頂點保持以 A、B、C……等名稱標記來計數，著色配置的總數如下（即使旋轉或重新標記後形狀相同，只要頂點標記不同，也視為不同的著色）：

$$ 2^{\binom{n}{2}} $$

對於 6 個人而言，共有 $2^{15}=32768$ 種情形。當我們對 3 到 6 人進行全數窮舉檢驗時，結果如下表所示：

人數著色總數無單色三角形的著色數存在單色三角形的比例
3 人8625.00%
4 人641871.88%
5 人10241298.83%
6 人327680100.00%

比較 3 至 6 人時存在單色三角形的比例。5 人時雖達 98.83% 但仍殘存 12 種反例，而在 6 人時則達到 100%

在 5 個人時，隨機著色出現單色三角形的機率約高達 98.83%。若只嘗試幾次，人們很可能會誤以為「5 個人也必然存在」。然而，在全部 1024 種著色中，仍確確實實殘存著 12 種反例。機率極高與完全沒有反例之間，存在著本質上的絕對差距。

此表是建立在每條邊獨立且等機率著色的假設下的比例。我們並非主張現實中的人際關係是彼此獨立、各佔一半機率產生的。相反地，6 人的定理完全不依賴機率，因此無論人際關係多麼極端或偏頗，定理都必然成立。

平均而言，能找到幾個？

任意選定 3 個頂點，其間有 3 條邊，共有 8 種著色方式。其中全紅與全藍這 2 種是單色，因此形成單色三角形的機率為 $1/4$。設單色三角形的個數為 $T$，根據期望值的線性性質：

$$ E[T]=\binom{n}{3}\frac14 $$

在 6 個人時，平均會有 5 個。雖然三角形之間因為共用邊而不一定彼此獨立，但在計算期望值的總和時，並不需要獨立性。

然而，平均值為正，絕不代表在每種著色配置下都必定存在。5 個人時的平均值也是 2.5 個，但卻存在個數為 0 的反例。切勿混淆「平均情況」與「最壞情況」，這也是拉姆齊理論帶給我們的重要思維視角。

7. 用 Python 驗證全部 32,768 種著色情形

以下程式碼僅使用 Python 內建的標準函式庫即可執行。我們將紅色編碼為 0、藍色編碼為 1，並將每條邊的顏色對應到二進位整數的各個位元。程式會選取任意 3 個頂點，並檢查它們之間的 3 條邊是否同色。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from itertools import combinations

def check_all(n):
    edges = list(combinations(range(n), 2))
    edge_index = {edge: i for i, edge in enumerate(edges)}
    triples = [
        [edge_index[e] for e in combinations(vertices, 2)]
        for vertices in combinations(range(n), 3)
    ]
    total = 1 << len(edges)
    without_triangle = 0
    minimum = len(triples)

    for coloring in range(total):
        count = 0
        for i, j, k in triples:
            if ((coloring >> i) & 1) == ((coloring >> j) & 1) == ((coloring >> k) & 1):
                count += 1
        without_triangle += (count == 0)
        minimum = min(minimum, count)

    return total, without_triangle, minimum

for n in range(3, 7):
    total, missing, minimum = check_all(n)
    print(f"{n} 人：共 {total} 種情形，無同色三角形 {missing} 種，最少 {minimum} 個")

1
2
3
4

3 人：共 8 種情形，無同色三角形 6 種，最少 0 個
4 人：共 64 種情形，無同色三角形 18 種，最少 0 個
5 人：共 1024 種情形，無同色三角形 12 種，最少 0 個
6 人：共 32768 種情形，無同色三角形 0 種，最少 2 個

6 個人時「最少 2 個」這項結果，是比最初的證明更進一步的發現。事實上，若將每個頂點所連出的紅線數記為 $r_v$、藍線數記為 $b_v$，則有 $r_v+b_v=5$，且 $r_vb_v\leq6$。

非單色的三角形中，恰好有兩個頂點同時連接了紅線與藍線。因此，若我們統計每個頂點處「1 條紅線與 1 條藍線組成的配對」數量，就會把每個非單色三角形重複計算 2 次。由於 6 個頂點中的全部三角形共有 20 個，因此：

$$ T=\binom63-\frac12\sum_{v=1}^{6}r_vb_v \geq20-\frac12\cdot6\cdot6=2 $$

這在數學上給出了嚴格證明。更進一步地，若將 6 個頂點平分為兩組（每組 3 個），各組內部的邊塗成紅色，而跨組相連的邊全部塗成藍色，則會恰好產生 2 個紅色三角形、0 個藍色三角形。因此，最小值 2 也是完全精確的。

這種全排列窮舉法對於較小的頂點數非常有效，但著色總數是以 $2^{n(n-1)/2}$ 的速度爆發式增長。若增加人數執行相同的程式碼，運算負擔會迅速加劇，因此這裡僅限定驗證 3 到 6 人。圖表與詳細的分佈數據可參閱 重現用腳本 與 計算結果 JSON。

8. 應用 ①：網路中的「全連通」或「全非連通」

現在讓我們把「認識與否」這個生活詞彙，替換為設備之間的「直接連線」。假設有 6 台設備，每對設備之間只有「存在直接連線」或「不存在直接連線」兩種狀態。只要連線是無向的（雙向對稱），我們就可以直接套用相同的定理。

如此一來，在 6 台設備中，必定存在一個 3 台設備兩兩均有直接連線的群組，或者一個 3 台設備兩兩均無直接連線的群組。前者在圖論中稱為 3 個頂點的 團（Clique） ，後者則稱為 3 個頂點的 獨立集（Independent Set） 。請注意，這裡的「不存在直接連線」並不代表無法透過其他設備轉發進行通訊。

這種視角也可以應用於兩兩設定相容／互斥條件的工作排程，或是檢視微型網路的互聯架構設計。例如，即便系統設計者提出「既要避免出現 3 項完全彼此相容的任務，也要避免出現 3 項完全彼此互斥的任務」這樣的要求，我們在實際搜尋之前就能斷定：只要任務總數達到 6 項，這項要求在數學上就是不可能滿足的。

不過，拉姆齊定理並不會替我們預先選擇出現的究竟是哪一種。有時我們渴望找到 3 項相互相容的任務，但實際出現的卻可能是 3 項互相衝突的組合。此外，即便每兩項之間彼此相容，也可能在 3 項同時執行時發生整體資源不足的情況，這類條件需要另外進行驗證。定理所能保證的範疇，始終僅限於我們所賦予的兩兩關係。

9. 應用 ②：從雜亂的數列中找出遞增或遞減子序列

我們將 6 個互不相同的數字按任意順序排列。若位置 $i$ 在位置 $j$ 之前（$i\lt j$），當 $a_i\lt a_j$ 時連紅線，當 $a_i\gt a_j$ 時連藍線。

這同樣是 6 個頂點的完全圖的雙色著色問題。因此，圖中必定存在單色三角形。將這 3 個位置由小到大設為 $i\lt j\lt k$：若是紅色三角形，則滿足：

$$ a_i\lt a_j\lt a_k $$

若是藍色三角形，則滿足：

$$ a_i\gt a_j\gt a_k $$

這意味著： 在保持原始順序的前提下，必然能從中提取出長度為 3 的遞增子序列或長度為 3 的遞減子序列。 這些項在原數列中不需要是相鄰的。像這樣不改變相對順序而從中抽出的序列，在數學上稱為子序列（Subsequence）。

從數列 4、1、5、2、6、3 中，選取原始位置 2、4、6 提取出遞增子序列 1、2、3 的示意圖

在圖中的數列 $4,1,5,2,6,3$ 中，選取第 2、4、6 個位置，即可得到 $1,2,3$。這並非將數值從小到大重新排序，而是在保持其原始出現順序的情況下選取出來的。

這項原理引領出從資料序列中尋找規律性子結構的重要思維。然而，即便挑選出的 3 個資料點呈現遞增趨勢，也絕不能作為整體時間序列具備上升趨勢的證據。因為對於任何排列順序都必然能找到的結構，單憑其存在本身，並不能稱之為特殊現象。

另外值得一提的是，在數列的這個問題中，6 項並非最小值；事實上，只要有 5 個互不相同的項，就足以保證存在長度為 3 的單調遞增或遞減子序列。這是著名的「艾狄胥–塞凱賴什單調子序列定理（Erdős–Szekeres Theorem）」的一個特例。由於從數列構建的著色受到傳遞性等大小關係的約束，因此能獲得比任意雙色著色更強的結果。單調子序列相關講義資料

10. 總結：混亂之中，亦有無法逃避的規律

將 6 個人的人際關係轉化為紅線與藍線，並僅僅聚焦於從 1 個人出發的 5 條邊，我們便嚴格證明了單色三角形的必然存在。而 5 個人的五邊形構造給出了反例，由此確立了拉姆齊數 $R(3,3)=6$。

值得我們深思並銘記的核心觀念有以下三點：

  • 「必然存在」並不等同於在隨機實驗中以極高機率出現。 5 個人時即便機率高達約 98.83%，依然存在反例；而 6 個人時則是毫無例外、一個反例也不剩。
  • 規律的存在，與該規律背後的現實意義是兩回事。 僅僅因為存在單色三角形或遞增子序列，並不能直接決定群體整體的性質或因果關係。
  • 數學保證始終伴隨著明確的對象與前提條件。 關係是否對稱、所有配對能否嚴格分為兩類、我們尋求的究竟是何種子結構，都必須事先予以釐清。

拉姆齊理論的迷人之處，並不在於將複雜的整體化簡為單純的現象。而是揭示了：即便整體結構依然無比複雜混亂，深藏於其中的局部規律也絕不可能被完全抹滅。只要在紙上畫下幾條簡單的線，我們便能親自體會這份深刻的數學之美。

參考資料

本文章中的圖表、全排列窮舉數據表、機率與數量分佈，均由隨附的 Python 腳本生成。

comments powered by Disqus
© 2020 - 2026 kenjinote
使用 Hugo 建立
主題 Stack 由 Jimmy 設計