好幾個月沒有寫談天說數專欄了,離上一篇都間隔九個月。一方面是要找些盡量不牽涉太複雜式子或觀念的的題材不是那麼容易,另一方面大家也很熱愛伍德的提問箱,總讓伍德有料能大家聊,當然最大原因還是懶。但話說回來,要是伍德都不發文,原本就已經很稀薄的存在感大概會更加縹緲吧。
開場白說得有些太長了,來聊聊今天的問題吧!今天的問題不需要複雜的方程式,也還算跟大家的生活相關──大家還記得上次看地圖是什麼時候嗎?這裡伍德說的不是Google街景地圖或有畫出山脈、氣候那類精細的圖,而是像是地理課本每章一開始,只用各種顏色分隔不同國家的圖。大家有數過除了用來表示海洋、湖泊水域的藍色之外,總共用了多少顏色嗎?
而這就是今天的問題:「隨便給定一張地圖,最多需要幾種顏色就能將其上色完成?」
當然,這裡的「上色」要求相鄰的不同國家(像是美國和加拿大)需要上不同的顏色(像是田的左上和右下角,只有一個點碰到沒關係)。而地圖可以長得奇形怪狀,不必然是地理課本的世界地圖割一塊下來。
這個問題在眾多數學問題裡,用白話敘述起來很簡單,但證明卻意外困難。最後的答案需要的顏色不多,也被冠上「X色定理」的名字(X是答案),許多數學科普書也會提及,或許你也聽過。這裡伍德先把答案遮起來,是希望藉機談談切入問題的思路。而這類談論圖、事物關聯的數學問題一般歸在「圖論」(Graph Theory)下,是離散數學的分支。不只數學系,在寫程式規劃演算法時,圖論也有不少應用。
一、夾出答案
一般看到這類問題,首要任務不是證明,而是先猜出答案。直覺好的天才或許可以馬上猜到,但我們普通人還是得慢慢來,先猜個範圍。要多少顏色就保證夠呢?或許可以從生活經驗下手,常看見的地圖再多彩,似乎六七種就很多了(不含標示地形等特殊要求),保守一點猜,搞不好八種?至少先猜出個上界,在這裡我們指的是八種一定夠。
另一個方向是去猜幾種顏色一定不夠。將一個圓形切成三等分的扇形,一定要三種顏色才夠,所以至少知道兩種不夠。事實上下面的圖形一定需要四種顏色(大家可以自己試試看三種夠不夠)。所以至少需要四種。
從上面的討論,我們猜答案是至少四種到八種之間。而這時數學家們才會再繼續往下細想,一步一步把答案逼出來。那麼再往下的證明伍德在科普專欄就不深究,直接捏他(?)大家最後結果:只要四種顏色就能保證上色完所有地圖。這個定理也因此被後世稱為「四色定理」。
二、四色定理
四色定理的起源是1852年由南非數學家法蘭西斯‧古德里(Francis Guthrie)所提出,當時他看了許多地圖,發現四種顏色似乎就夠了。在和家人的書信往返後,這個問題輾轉傳到當時的數學圈,其中奧古斯塔斯‧德摩根(Augustus De Morgan)*1對這問題很有興趣,也把它推廣給其他數學家研究。
時間來到1879年,律師兼數學家阿爾弗雷德‧肯普(Alfred Kempe)提出了四色定理的證明──但是是錯的。這個錯誤在1890年,由另一位數學家彭西‧西伍德(Percy Heawood)指出,但西伍德除了證明肯普是錯的之外,也只能證明「五個顏色一定夠」的「五色定理」,離四色定理還是差了臨門一腳。有趣的是,當時的數學學界也認為這臨門一腳大概不難,自己不解決也總會有好事者解決*2,而讓研究在歐洲停滯。相關研究由美國承繼,但一時也沒有重大發展。
於是又過了一個世紀,四色定理終於在1976年,由凱尼斯‧阿佩爾(Kenneth Appel)和沃夫岡‧哈肯(Wolfgang Haken)兩位數學家完成證明,但這證明偏偏不是人人買單。怎麼回事呢?原來兩人的證明到了最後一步,將所有圖都只需要四色,簡化到檢驗1936種圖(之後的證明版本簡化到633種)能被四色上完就夠了,而這最後一步──使用了電腦。
在2021年的現在看來,使用電腦根本不是什麼大不了的事情。但在約半個世紀前,「沒有用手算」的證明在某些數學家看來可是離經叛道。事實上,直到今日也仍有數學家在尋找不需要電腦,比較簡潔的證明。雖說伍德不算數學家,但真要我說,只要電腦的演算法能正確達成要求,在證明過程中使用電腦又有何不可呢?雖然可能是個比較暴力直接而不巧妙的證明,但至少是把問題解決了。當然,審查時的重點就得放在演算法是否正確了。
時至今日,大部分人都承認使用電腦的證明,即便仍有人繼續研究,也只是為了找出更精簡、不須電腦的證明,而沒有對其正確性再有質疑。四色定理大概是第一個透過電腦證明的知名定理,爾後在圖論、甚至更多領域中也有不少透過電腦輔助證明的定理,甚至今日的研究可說已經離不開電腦了。當代一個有趣的問題是能不能讓人工智慧思考定理證明,甚至自己發現有趣的定理──會是個好科幻題材,不過伍德不是專家,也說不準,就留給大家自行想像吧!
下一次有機會的話我們來聊聊圖論裡另一個也很有趣的問題:「拉姆齊(Ramsey)問題」。它最初的敘述很簡單、也很白話,但似乎挺令人意外:「任意六個人裡面,一定抓得出相互認識的三人,或相互不認識的三人」。到底怎麼回事,我們下期分曉。
那麼這次就先跟大家聊到這裡,伍德說數,我們下次見!
*1. 這位就是各位高中或大學邏輯課裡學到「德摩根定律」的那位德摩根(狄摩根)。
*2. 甚至當時不少教授把四色定理的證明出成回家作業──沒錯,別以為大學教授都知道回家作業的解答...(但大多數還是知道的。)