主題

我們認識嗎--簡談拉姆齊(Ramsey)定理

伍德‧瓦懷特 | 2021-09-26 14:47:23 | 巴幣 590 | 人氣 251

  當大家需要面對一群可能不太熟識的人,會覺得自在嗎?至少伍德不太行。若是演講、講課之類一對多的場合,其實沒什麼問題,但若是聯誼、派對之類散在人群內、需要去認識大家的情形,我就不大擅長了。或許是因為前者是我能控制場面,而後者則充滿不確定性所致。不過伍德倒是挺喜歡在聯誼上看到和自己一樣有些不知所措的人,總有種找到同類的親切感。

  今天的伍德說數就來跟大家談一群人中認識及不認識的問題。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)的運用──我知道你們要說什麼,對,伍德鴿改天來聊聊鴿籠原理吧。
送禮物贊助創作者 !
0
留言

創作回應

老周(LeviChou)
大大泥對我是不是有什麼誤會,我真的不熟幾何,說mind-blowing肯定是一種鄉巴佬行為LOL
2021-09-27 09:08:12
伍德‧瓦懷特
沒啦,大家都有各自專長,震驚的點可能不太一樣XD
(順帶一提,數學裡我也相對不擅長幾何,不過圖論是歸在離散數學、組合數學下面,倒不是幾何──當然,也不是說他們就毫無交集。)
其實我真的也認為你上次的做法可行,只是要修一下而已。比第一次看到只知道畫線連老半天、說不出所以然的我還要好一些XD
2021-09-27 09:11:11
熟魚片
簡直是簡單易懂又精闢的驗證過程,我一個字都看不懂
2021-09-27 14:01:39
伍德‧瓦懷特
那就是我得檢討了...
2021-09-27 14:18:59
熟魚片
沒有啦,伍德的圖解很好理解,是我慧根不夠xd
2021-09-27 14:56:27
伍德‧瓦懷特
真的不求大家第一次看就完全理解,我也是看了、跟著想過一遍才懂的
2021-09-27 14:59:56
玹竹以墨
這個證明真的很短,而且很容易懂耶OAO!!!很有趣!!!
2021-09-27 19:15:31
伍德‧瓦懷特
歡迎下次放閃時使用(欸)
要有這樣證明短又不太需要花大篇幅做前置作業的題材實在不容易...Orz
2021-09-27 23:48:44
悠閒紅茶(冷卻中)
為什麼、紅茶率先想到的不是複雜的數學公式,而是金髮廚師憤怒地大吼:生的!
2021-10-15 21:45:38
伍德‧瓦懷特
就像前面的留言一樣,拉姆齊實在給人印象太強了XD 只好再喊一次:
It's maaaaaaaaath!(X)
2021-10-16 05:08:02

相關創作

更多創作