世界上任意N個人中,一定有4個人互相認識,或者有4個人兩兩互不相識,N至少是幾?
源自一道經典的奧數題:
世界上任何6人中,一定有3人相互認識,或者有3人兩兩互不相識
證明方法是:假定6人中有A,至少與3人相互認識,或者至少與3人互不相識(抽屜原理)。假定A與BCD相互認識,那麼BCD中只要有兩人相互認識,則命題成立;反之BCD兩兩互不相識,命題也成立。
當然還有更笨拙的辦法,例如窮舉,6人中認識或不認識的組合一共有2^C(6,2)=32768種,用計算機遍歷一下就秒出了。
但如果把「相互認識」、「兩兩互不相識」人數改成4人,題目會怎樣呢?我覺得應該分幾步走:
- 給定一個N,使命題不成立,例如3人「相互認識」或「兩兩互不相識」的情況,N=5時就不成立;
- 證明存在這個N,使命題成立;
- 給出N的一個具體的數值,但未必是最小的;
- 給出最小值。
可目前我一點思路都沒有,哪怕是窮舉難度也非常大,組合一共是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不讓男生參加?有什麼好的方案?
※數學思維需要從小抓起嗎?
※為什麼奧數金牌得主不出國深造呢?
※請教一道數學題,涉及到高數知識?
※如何識別一個好的奧數老師?