【轉貼】認識不認識? 這是個問題!

[wdshieh 10]

原本貼在推理解謎討論版

有人建議貼到數學版來，就從善如流了

相關討論請看http://www.student.tw/db/showthread.php?t=147950

=================================================

這一題是書上看來的

定義一:

我們先把任意兩個人之間彼此認識的情形，定義為只有「認識」和「不認識」兩種情形。其中

「認識」: 甲認識乙，乙也認識甲

「不認識」: 甲乙彼此不認識，或單方認識另一方的情形，我們都算做「不認識」

上文中沒有加引號的認識不認識，就如同我們日常生活中的用法，你認識某個人的話，表示你知道他的姓名、長相等等

所以根據以上的定義

我「認識」我的高中同班同學阿牛

我「不認識」冰島目前的總統

我「不認識」林志玲，因為我只單方面地認識林志玲，林志玲不認識我，所以我們算「不認識」

定義二:

任意三個人中，如果甲「認識」乙、乙「認識」丙、丙也「認識」甲，則我們稱甲乙丙三人為「兩兩認識」

若甲「不認識」乙、乙「不認識」丙、丙也「不認識」甲，則我們稱甲乙丙三人為「兩兩不認識」

定律:

從地球上的數十億人中任取六個人，則這六個人中

1)某三個人「兩兩認識」

2)某三個人「兩兩不認識」

以上1)或2)的情形至少有一成立

證明看看吧

[rm2slg 10]

這就是有名的Ramsey函數求(3,3)的值

即R(3,3)=6

圖論的做法：

把六個人視為點

每兩個人中間連上一條線

以線的顏色代表認識的情形

如果認識，假設塗紅色

不認識塗藍色

考慮任意一個點

與之相連有五條邊

根據鴿籠原理

必有三邊同色

考慮與這三邊所連的點

如果這三點之間的關係與原本不同色

則有三個人的認識不認識情形相同

如果有一個與原本同色

則一樣形成有三個人認識與不認識情形相同

故必有三人同時認識或同時不認識