 |
榕城老應
好的智力遊戲，挑戰的是智力而不是知識。簡單直觀有確定的答案，但有一定的難度。問題的解決，不僅有征服高峰的快感，還常有開拓眼界的收獲。上一個帖子“稱球問題”就屬於這一類。
我這裏再出一道題。為了讓大家有收獲，先給大家一個思路。
我所學的許多知識中大約最直觀的就是這個“抽屜原理”了。它是組合數學的一個基本原理，最先是由德國數學家狄利克雷明確地提出來的，因此，也稱為狄利克雷原理。
這原理形象的說法是：將10個蘋果放在9個抽屜，至少有一個抽屜會有2個或以上的蘋果。如此等等，總之傻子都能明白的道理。其實我在上麵稱球問題的定理證明中就幾次用到抽屜原理。隻不過人人不打磕的就能通過，所以就不再提了。這抽屜原理，用信息也能給出個解釋，不過組合數學覺得用集合論就能說明白，就不提了。
抽屜原理如果沒有個不尋常的應用，那也沒人會認這個賬，早讓奧卡姆的剃刀給切去了。下麵是題目，給大家一個驗證的機會。
1958年6/7月號的《美國數學月刊》上有這樣一道題目： 證明在任意6人的集會上，有3個人以前彼此都相識，或者有3個人以前彼此不相識，這兩者必居其一。
這道題的數目有限，自然可以用枚舉法證明。但用抽屜原理，幾句話就能說清，你知道該怎麽證明嗎？
別看這道題簡單，六人集會問題是組合數學中著名的拉姆塞定理的一個簡單的特例，它的思路可以得出另一些深入的結論。它們構成了組合數學中的“拉姆塞理論”。
×××××
你想出來怎麽證明了嗎？要是沒有，下麵是證明。
在6人中任選一人（稱為主人），他與其他5人的關係，可以分成兩類：認識的和不認識的。5人分2類，至少有一類是3人以上（抽屜原理）。
假設認識的至少有3人，這3人如果互相全不認識，就滿足問題中後一條件。否則，至少有兩人認識，再加上主人，就有了互相認識的3個人，滿足前一條件。因此，兩條件必居其一。
假設不認識的起碼有3人，將前一假設論中“認識”與“不認識”互換，完全對稱地可以證明了結論。
|
|
|
