當大家需要面對一群可能不太熟識的人,會覺得自在嗎?至少伍德不太行。若是演講、講課之類一對多的場合,其實沒什麼問題,但若是聯誼、派對之類散在人群內、需要去認識大家的情形,我就不大擅長了。或許是因為前者是我能控制場面,而後者則充滿不確定性所致。不過伍德倒是挺喜歡在聯誼上看到和自己一樣有些不知所措的人,總有種找到同類的親切感。
今天的伍德說數就來跟大家談一群人中認識及不認識的問題。1930年,英國數學家、哲學家兼經濟學家*1法蘭克‧普朗普頓‧拉姆齊(Frank Plumpton Ramsey)在其文章提出並證明了一個很簡單、卻或許有些讓人驚訝的敘述:「任意六個人中,一定能找出三個人互相認識,或三個人互相不認識。」這裡我們把「A認識B、B不認識A」這種情形歸為互相不認識,因此兩個人要就互相認識、要就互相不認識。
這個敘述被後世稱為拉姆齊定理,並延伸出一連串的研究,在高中數學奧林匹亞中,類似思路的問題也層出不窮。今天我們就來聊聊這個定理怎麼證明──其實出乎意料地容易。
一、拉姆齊定理
為了方便,我們把拉姆齊定理再抄一次在這裡。
「任意六個人中,一定能找出三個人互相認識,或三個人互相不認識。」
最直接的思路當然是把所有情形都列出來,只不過數目有點多。A~F中,每兩個人都要考慮認不認識,AB、AC...、EF共有15個組合,每個組合都有兩種可能,所以最不動腦的解答是把2^15=32768種情形都列出來,然後一一驗證。其實在有電腦的現在倒也不是太難的事情了,不過我們就不走這條路,來看看比較巧妙的作法。
拉姆齊問題和上次的四色定理一樣,都是歸在圖論(Graph Theory)這一分支底下的問題。簡單來說,就是將人事物比擬為點、其間的關係比擬為線,並染上不同的顏色,最後(巧妙地)數數,進而達到目的的數學。在這裡,我們把六個人比擬成不共線的六個點,所謂不共線,其實就是說這些點不在同一條直線上的意思,所以任意三點都能連出一個三角形。大家可以想像同一條直線上的三個點當然只能連出那條直線,而不是三角形。
接著我們把所有點兩兩連線,把互相認識的兩人間的線塗上紅色、互相不認識的兩人間的線塗成藍色*2。整張圖上就會充滿紅色和藍色的線。例如下圖就是個例子。
A~F中,每兩個人認識或不認識都被記錄下來,例如AB間紅色的線就代表他們相互認識。而ABC這個紅色三角形就表示這三個人相互認識;BDE這個藍色三角形就是他們互相不認識,兩個都是拉姆齊定理提到保證會出現的組合(拉姆齊定理只保證至少出現一種情形)。從這種角度出發,拉姆齊定理也能這麼寫:
「任意不共線的六點間,兩兩用紅色或藍色線段相連,最後一定會出現紅色或藍色三角形。」
而因此,拉姆齊定理有時也被稱為拉姆齊雙染色定理(因為他老兄做的事情實在太多了...)。
那麼在我們將問題轉化成連線和染色問題後,就來聊聊拉姆齊定理的證明──別急著走,真說起來其實很短。
Proof:
Step 1:我們先固定住一個人,稱它為A。A和其他人共會連出五條線段,也就是AB、AC、...、AF。這五條線段只有紅色和藍色兩種可能。
Step 2:這裡要注意其中一定有一種顏色有三個(以上)。他們可能是五紅、四紅一藍、三紅二藍、...、五藍,不管怎樣一定有種顏色是三個以上。一種稍微巧妙一點的方法是反證法,如果兩種顏色都湊不到三個,最多就只有兩紅兩藍的Quota,不可能是五條線*3。
Step 3:那麼我們就抓出其中三條紅線(如果是藍線,思路是一樣的),假設那三條分別是AB、AC、AD。結果就會變下面這樣。(AE、AF和其他點間也有連線,不過不重要就不畫了)
Step 4:現在來看看BC、BD和CD,如果它們其中有任何一條是紅線──恭喜,你就找到紅色三角形了。如果它們三條都是藍線呢?恭喜,你找到藍色三角形了。所以不論如何,你都可以找到互相認識的三人(紅色三角形)或是互相不認識的三人(藍色三角形)。
以上,證明結束。
從上面的圖很容易誤會E、F兩個人沒作用,再強調一次,它們的作用是保證AB到AF間可以找出三條紅線(藍線)。
有趣的是,如果只有五個人,倒是能畫出沒有紅色和藍色三角形的情形:
這個魔法陣(X)裡就沒有紅色和藍色三角形(中間小的不算啦欸)。
二、拉姆齊數
拉姆齊問題出乎意料地直接,也啟發了後續的研究。其中一個最直接的推廣是「需要幾個人,才能保證找到x人互相認識或y人互相不認識」。這個人數被稱為拉姆齊數,記做R(x,y)。從上面的討論中,我們知道R(3,3)=6。自然地,R(x,y)=R(y,x)。(紅色藍色互換的概念)
當x、y很小時還能討論,但人一多時的拉姆齊數到目前都還沒定論(只有範圍)。舉例來說,我們只知道R(4,4)=18(18個人裡一定能找出四個人相互認識或四個人相互不認識),但R(5,5)只知道是介在43~48間。另外也有x、y不相等時的研究,像是R(4,5)=25(25個人裡一定能找出四個人相互認識或五個人相互不認識)。或許改天找出新的拉姆齊數,你也能在數學史上留名也不一定。
今天我們畫了一堆魔法陣(X?),聊了圖論裡一支有趣的問題:拉姆齊定理。像這樣的問題其實也是數學,是很正統的純數學。數學不是只有代數、幾何這類看來很「王道」的學科,其實很寬廣,探討的問題也各式各樣。除了以往的專欄,以後要是有機會也想再跟大家聊聊數學這個領域中不同的問題呢。
那麼今天就先跟大家聊到這邊,伍德說數,我們下次見!
*1. 這兼得有點多,更厲害的是每個領域中拉姆齊都有很好的貢獻,不只是沾光而已。
*2. 顏色沒有其他意思,大家塗得開心就好。
*3. 如果你讀過其他數學科普書,沒錯,這就是鴿籠原理(Pigeonhole Principle)的運用──我知道你們要說什麼,對,伍德鴿改天來聊聊鴿籠原理吧。