畫樹畫出一個大數–TREE(3)漫談

大家好，上期我們講了一個大數，叫葛立恆數。今天我們再接再厲，再講一個超大數，叫TREE(3)。這裡TREE就是英文裡樹木的那個單詞TREE。TREE(3)其實就是一個函數，函數名稱叫TREE，而函數自變量取值是3。

上期講過，TREE(3)跟葛立恆數比的話，葛立恆數是屬於忽略不計的。更為神奇的是，TREE(3)的定義比葛立恆數更簡單，簡單來說，它就是一個畫「樹」的遊戲，樹林的樹。這裡，這個「樹」的概念，對計算機專業的聽眾來說再熟悉不過了，什麼二叉樹，查找樹等等。如果你不是計算機專業的，也不要緊。你應該也看到過公司的組織架構圖，或是某個人的家譜等等，也是用類似一棵樹的結構展示的，這就是我們今天要談的樹的概念。我在節目介紹裡也放了一個樹的簡單示意圖。

然後TREE(3)這個數，就可以用一種畫樹的遊戲來導出，畫的時候，我們會給每個節點，俗稱葉子的東西，畫上某種顏色。而對線段，俗稱樹枝，我們不關心它的顏色。而TREE(3)，意思就是用三種顏色來畫這顆樹。

我們還有一些畫樹的規則。這個畫樹的遊戲只有兩個規則。第一條規則是這樣，你畫的第一棵樹，只能有一個節點，第二棵樹，不能超過2個節點，第三棵樹不能超過3個節點…第n棵樹，不能超過n個節點。也就是，越到後面，你樹中的節點可以越來越多，但不能多過你畫的樹的序號。

第二個條件，你後面畫的樹，不能「包含」前面的樹。這裡「包含」的概念是這樣的，比如你後面的樹去掉若干葉子後，就是之前的樹，用術語說，就是前面的樹是這顆樹的子樹，那就犯規的。但我們這裡「包含」的意思要比「子樹」的定義更寬泛點，我們還要求以下這種情況也不允許，就是當前的樹中如果取若干節點，這若干節點如果可以跟之前的某棵樹的節點建立一一對應關係，而且兩顆樹中，任意對應兩個節點的最近共同祖先是同一顏色，那也不允許。所謂最近共同「祖先」的概念也是很好理解的，就是兩個葉子同時向根節點回溯，那它們遲早會在某個節點匯合，最遲也是根節點，那這個結點就叫「最近共同祖先」，如果你把樹看作一個家譜的話，那你就更好理解了。現在的要求就是，如果兩棵樹之間，如果對應節點的最近共同祖先是同一顏色，那遊戲結束。其實這種「包含」在數學上有個術語叫inf-embeddable. Embeddable 就是可嵌入的意思，這個詞搞嵌入式系統的再熟悉不過。INF是什麼意思呢，它其實是下確界，或者說最大下界的拉丁文縮寫。為什麼用這個詞，因為如果你把一棵樹某個枝條上的節點當做一個大小排序的話，且根節點最小，那麼兩個節點的最近祖先其實就是最大的且比這兩個節點都小的的節點， 所以叫下確界，INF。這就是inf-embeddable的全部意思。

(下圖：左邊的樹包含右邊的樹)

OK，以上就是畫樹遊戲的全部規則。那我跟大家在節目裡演示下，玩玩看。當然很推薦你現在拿支筆和紙，一起來玩玩看，你可以用不同的符號來表示顏色。那我們先從TREE(1)這個遊戲開始玩，也就是只用一種顏色，假設你用的是紅色。先畫第一棵樹，那你明顯只能畫一個根節點是紅色。你會發現你沒辦法再畫第二棵樹了，因為第二棵樹，你最多畫兩個節點。你重畫一個紅色的根結點，那跟第一棵樹一樣，肯定不行。你如果畫兩個紅色節點，那也包含第一棵樹，也不行。所以遊戲結束，你只能畫出一棵樹，那我們知道TREE(1)=1。

(下圖: TREE(1)遊戲示意，右邊的樹包含左邊的樹，所以遊戲結束。TREE(1)=1)

接下來玩下TREE(2)，用兩種顏色，紅色和綠色。那你第一棵樹，比如還是用紅色畫一個根節點，第二棵樹你如果用綠色畫一個根結點，那你會發現你第三棵樹就沒法畫了，因為第三棵樹無論怎麼畫，必然包含第一顆或第二棵樹。但我們還有一個更好的做法。那就是第二棵樹畫成綠色的根節點接一個綠色的葉子。這樣，我們第三棵樹就可以畫成只有一個綠色根結點的樹，就一個根。因為我們規則只限制後面的樹不能包含前面的樹，沒有規定前面的樹不能包含後面的樹。這樣雖然我們第二棵樹包含了第三棵樹，但是第三棵樹沒有包含之前的樹，所以這是允許的。這之後，你會發現你無法再畫出第四顆樹了。所以TREE(2)=3。

(下圖：TREE(2)遊戲示例，你最多畫出如下三顆樹，所以TREE(2)=3)

 

好TREE(1) ，TREE(2)的遊戲我們都玩過了，現在到見證奇蹟的時刻了，我們要玩TREE(3)了，比如你可以再加入一個顏色，藍色。用紅，綠，藍三色來玩這個畫樹的遊戲。你會發現，這次你似乎發揮餘地大多了，你可以畫非常多的樹。我在節目介紹裡，也放了TREE(3)遊戲開始的12棵樹的可能畫法：

但是我勸你不要繼續了，因為你無法畫到它結束的時刻，因為這個TREE(3)的值實在太大了，大到驚天地泣鬼神，比葛林恆數還大。當然，你可能此時會質疑，你怎麼證明TREE(3)是一個有限值，而不是無窮大的，也就是我可以無窮的玩下去呢？

這裡要用到一個定理，叫克魯斯科爾樹定理。克魯斯科爾這個名字計算機系的聽眾又是太熟悉了，克魯斯科爾算法是考試必考的對不對。克魯斯科爾算我們計算機系學生膜拜的大神了，他已於2010年去世，這裡我們也順帶緬懷一下。我們今天不考最小生成樹算法，而是克魯斯科爾發現的這個樹定理。這個定理有個粗糙但簡單的說法就是如果你給我無窮多個樹，那其中必然有一個樹是另一顆的INF-embeddable，同下確界意義上的嵌入。那TREE(3)是一個有限的數其實就這個定理的直接推論了，是不是？

你可能關心TREE(3)這個有限的數到底有多大？不管你信不信，這其實是今天節目最難點了。上一期葛立恆數我用箭號表示法，大概還能說明下葛立恆數有多大，但是在TREE(3)面前，箭號表示法已經完全不管用了。但是我們還是可以參考下，上期我們說了葛立恆數可以用64重箭號表示法來表示，那TREE(3)如果要用多重箭號表示法表示，那需要的層數將遠遠大於葛立恆數。這大概是我最好的形容了，再往下我都不知道怎麼說了，因為再怎麼用語言或符號表達，我都感覺都是很徒勞了。當然，如果你有興趣還是可以上網搜搜有關TREE(3)的符號表示，為了表示它的大，得用各種專門的運算符號才行，雖然這些符號對普通人來說，已經沒什麼感覺了。

關於TREE(3)還有好玩的一點，就是根據克魯斯科爾樹定理，TREE(4), TREE(5)，TREE(100)都是有限的對不對？那TREE(TREE(3)呢，就是用用TREE(3)個顏色玩這個畫樹遊戲，那它還是有限的。那如果TREE(TREE(3))我如此嵌套TREE(3)重呢? 對這個數我表示我大腦系統崩潰了。

OK，今天有關TREE(3)話題就聊到這了，我還是很喜歡TREE(3)這個數，因為它定義是如此之簡單，而且從平淡無奇的TREE(1)，TREE(2）, 到TREE(3)如同宇宙大爆炸式的轉變，實在太讓人吃驚了。另外各位以後寫情書也可以考慮寫「我愛你TREE(3)年」等等。下周再見！

收聽「大老李聊數學」音頻                                        關注「大老李聊數學」