世界上任意N個人中，一定有4個人互相認識，或者有4個人兩兩互不相識，N至少是幾？

源自一道經典的奧數題：

世界上任何6人中，一定有3人相互認識，或者有3人兩兩互不相識

證明方法是：假定6人中有A，至少與3人相互認識，或者至少與3人互不相識（抽屜原理）。假定A與BCD相互認識，那麼BCD中只要有兩人相互認識，則命題成立；反之BCD兩兩互不相識，命題也成立。

當然還有更笨拙的辦法，例如窮舉，6人中認識或不認識的組合一共有2^C(6,2)=32768種，用計算機遍歷一下就秒出了。

但如果把「相互認識」、「兩兩互不相識」人數改成4人，題目會怎樣呢？我覺得應該分幾步走：

1. 給定一個N，使命題不成立，例如3人「相互認識」或「兩兩互不相識」的情況，N=5時就不成立；
2. 證明存在這個N，使命題成立；
3. 給出N的一個具體的數值，但未必是最小的；
4. 給出最小值。

可目前我一點思路都沒有，哪怕是窮舉難度也非常大，組合一共是2^C(N,2)種，如果N=10的話，2^45就是天文數字了。

Ramsey"s theorem

Using induction inequalities, it can be concluded that R(4, 3) ≤ R(4, 2) + R(3, 3) ? 1 = 9, and therefore R(4, 4) ≤ R(4, 3) + R(3, 4) ≤ 18. There are only two (4, 4, 16) graphs (that is, 2-colourings of a complete graph on 16 nodes without 4-node red or blue complete subgraphs) among 6.4 × 10^22 different 2-colourings of 16-node graphs, and only one (4, 4, 17) graph (the Paley graph of order 17) among 2.46 × 10^26 colourings.[3] (This was proven by Evans, Pulham and Sheehan in 1979.) It follows that R(4, 4) = 18.

關鍵詞：Ramsey數 完全圖