世界上任意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.


R(4,4)等於18


關鍵詞:Ramsey數 完全圖


Ramsey數:

r(4,4)=18


推薦閱讀:

為什麼女子奧賽CGMO不讓男生參加?有什麼好的方案?
數學思維需要從小抓起嗎?
為什麼奧數金牌得主不出國深造呢?
請教一道數學題,涉及到高數知識?
如何識別一個好的奧數老師?

TAG:數學 | 圖論 | 奧林匹克數學 | 組合數學 |