當大家需要面對一群可能不太熟識的人，會覺得自在嗎？至少伍德不太行。若是演講、講課之類一對多的場合，其實沒什麼問題，但若是聯誼、派對之類散在人群內、需要去認識大家的情形，我就不大擅長了。或許是因為前者是我能控制場面，而後者則充滿不確定性所致。不過伍德倒是挺喜歡在聯誼上看到和自己一樣有些不知所措的人，總有種找到同類的親切感。
今天的伍德說數就來跟大家談一群人中認識及不認識的問題。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)的運用──我知道你們要說什麼，對，伍德鴿改天來聊聊鴿籠原理吧。
達人
