朋友問題 (4 人互相認識/不認識)

引理 1 :
世界上任意 9 人當中必有 4 人互相認識或有 3 人互不相識。
引理 1 證明 :
我們總可以於 9人當中選出某君 A ,令到其餘 8人當中不認識 A的總人數不等於 3。
不然的話 ,對每人而言都恰好存在3個人不認識他/她 ,那麼互不相識的2人
共有 3 x 9 / 2 對(非整數) ,矛盾! 故可分以下 2種情況討論 :
Case 1 :
其餘 8 人當中不認識 A 的總人數至多 2 人 :
則認識 A 的總人數至少 6人 ,在題主的〈朋友問題(6人)〉裡已證明他們中必有 3人互相認識或互不相識 :
當有 3人互相認識時 ,加上 A 就有 4人互相認識 ,引理 1 成立。
當有 3人互不相識時 ,引理 1 亦成立。
Case 2 :
其餘 8 人當中不認識 A 的總人數至少 4 人 :
如果不認識 A 的所有人互相認識 ,則引理 1 成立。
不然 ,至少有 2人互不相識 ,加上 A 就有 3人互不相識 ,引理 1 亦成立。綜上 ,引理 1 得證。
同理可證引理 2 :
世界上任意 9 人當中必有 3 人互相認識或有 4 人互不相識。
現在證明世界上任何 18 人當中肯定有 4 人是互相認識或互不相識。
在 18 人中選出某君 A ,並將其餘 17 人依照其認識 A 與否分成 2 類 ,則其中一類至少有 9 人(鴿籠原理)。
Case 1 :
若至少 9 人認識 A ,由引理 2 知至少有 3 人互相認識或 4 人互不相識 :
當有 3 個人互相認識時 ,連同 A 便有 4 人互相認識 ,命題成立。
當有 4 個人互不相識時 ,命題亦成立。
Case 2 :
若至少 9 人不認識A ,由引理 1 知至少有 4 人互相認識或 3 人互不相識 :
當有 4 個人互相認識時 ,命題成立。
當有 3 個人互不相識時 ,連同 A 便有 4 人互不相識 ,命題亦成立。綜上 ,世界上任何 18 人當中肯定有 4 人是互相認識或互不相識。
最後 ,下圖表明當 n = 17 時 ,並不保證當中肯定有 4 人是互相認識或互不相識 :


圖片參考：http://imgcld.yimg.com/8/n/HA04628698/o/20121120141528.jpg
以正 17 邊形的 17 個點代表 17 個人 , 2 點相連代表該 2 人相識 , 沒有連線的 2 點代表該 2 人互不相識。
每個點分別與其左右相隔 1 , 2 , 4 , 8 個位置的 8 個點相連。
可驗證圖中找不到任何 4 個點是互相連線或互不相連的。
故 n 最少值為 18。

Ramsey theory 拉姆齊定理指出R(4,4) 18，則n 的最少值為18。