31. 畫(huà)樹(shù)畫(huà)出一個(gè)大數(shù)--TREE(3)漫談

大家好，上期我們講了一個(gè)大數(shù)，叫葛立恒數(shù)。今天我們?cè)俳釉賲枺僦v一個(gè)超大數(shù)，叫TREE(3)。這里TREE就是英文里樹(shù)木的那個(gè)單詞TREE。TREE(3)其實(shí)就是一個(gè)函數(shù)，函數(shù)名稱叫TREE，而函數(shù)自變量取值是3。

上期講過(guò)，TREE(3)跟葛立恒數(shù)比的話，葛立恒數(shù)是屬于忽略不計(jì)的。更為神奇的是，TREE(3)的定義比葛立恒數(shù)更簡(jiǎn)單，簡(jiǎn)單來(lái)說(shuō)，它就是一個(gè)畫(huà)“樹(shù)”的游戲，樹(shù)林的樹(shù)。這里，這個(gè)“樹(shù)”的概念，對(duì)計(jì)算機(jī)專業(yè)的聽(tīng)眾來(lái)說(shuō)再熟悉不過(guò)了，什么二叉樹(shù)，查找樹(shù)等等。如果你不是計(jì)算機(jī)專業(yè)的，也不要緊。你應(yīng)該也看到過(guò)公司的組織架構(gòu)圖，或是某個(gè)人的家譜等等，也是用類似一棵樹(shù)的結(jié)構(gòu)展示的，這就是我們今天要談的樹(shù)的概念。我在節(jié)目介紹里也放了一個(gè)樹(shù)的簡(jiǎn)單示意圖。

TREE(3)游戲的開(kāi)始的可能步數(shù)：

你可能關(guān)心TREE(3)這個(gè)有限的數(shù)到底有多大？不管你信不信，這其實(shí)是今天節(jié)目最難點(diǎn)了。上一期葛立恒數(shù)我用箭號(hào)表示法，大概還能說(shuō)明下葛立恒數(shù)有多大，但是在TREE(3)面前，箭號(hào)表示法已經(jīng)完全不管用了。但是我們還是可以參考下，上期我們說(shuō)了葛立恒數(shù)可以用64重箭號(hào)表示法來(lái)表示，那TREE(3)如果要用多重箭號(hào)表示法表示，那需要的層數(shù)將遠(yuǎn)遠(yuǎn)大于葛立恒數(shù)。

(每周一題)

本周題目：保險(xiǎn)箱大盜

你是個(gè)保險(xiǎn)箱大盜，你想打開(kāi)一個(gè)保險(xiǎn)箱。這個(gè)保險(xiǎn)箱有三個(gè)鎖（稱為1,2,3號(hào)鎖），每個(gè)鎖都獨(dú)立工作。你已經(jīng)得到了可以開(kāi)鎖的三把鑰匙（稱為A,B,C鑰匙），但是你并不知道A,B,C對(duì)應(yīng)哪把鎖。

保險(xiǎn)箱工作機(jī)制是這樣的，箱子外有一個(gè)開(kāi)鎖按鈕，當(dāng)你按開(kāi)鎖按鈕，每把鎖會(huì)檢查插入的鑰匙。如果是插入的是正確的鑰匙，且原先是鎖定狀態(tài)，這把鎖就會(huì)打開(kāi)；若原先是打開(kāi)狀態(tài)，這把鎖就會(huì)關(guān)閉。如果插入是錯(cuò)誤的鑰匙，這把鎖狀態(tài)保持不變（不管之前是打開(kāi)還是鎖定狀態(tài)）。只有三把鎖狀態(tài)都變成打開(kāi)時(shí)，保險(xiǎn)箱會(huì)自動(dòng)開(kāi)門。但只要有至少一個(gè)鎖是關(guān)閉狀態(tài)，整個(gè)保險(xiǎn)箱維持關(guān)閉狀態(tài)，而且你在任何時(shí)候都不知道某把鎖是關(guān)閉還是打開(kāi)的狀態(tài)，你也不知道每次嘗試開(kāi)鎖時(shí)，有幾把鎖發(fā)生了狀態(tài)變化。

作為一個(gè)出色的的大盜，你想用最少的嘗試次數(shù)打開(kāi)保險(xiǎn)箱，請(qǐng)問(wèn)你最少要嘗試多少次，才可以確保能夠打開(kāi)保險(xiǎn)箱？

提示：保險(xiǎn)箱初始狀態(tài)也未知，可能有某幾鎖開(kāi)始時(shí)已經(jīng)處于打開(kāi)狀態(tài)。

上期答案：

上周題目是：

張三和李四分一塊餅吃，兩個(gè)人都餓壞了，想多分點(diǎn)。他們約定這種分餅方法：張三先切一刀，分成兩片；李四從兩片中任選一片切一刀，剩下三片；張三從三片中任選一片，再切一刀，剩下四片。

然后張三得到最大和最小的一片，李四得到中間大小的兩片。問(wèn)張三采取什么樣的切法，可以得到最大比例的餅？這個(gè)比例是多少？

正確答案是張三可以到的3/5的餅。恭喜1106711411, Magician, 王森，今年不買表答對(duì)了！ 完整過(guò)程是張三先切成1/5和4/5，李四切4/5，變成1/5, 2/5, 2/5。張三再切2/5，變成1/5, 1/5, 1/5和2/5。這樣張三可得3/5。

簡(jiǎn)單證明如下：

設(shè)張三將餅切成s和1-s兩部分，且s<1/2。接下來(lái)有四種情形：

對(duì)s<=1/5，李四切完變成s, (1-s)/2和（1-s)/2。張三再切，變成s, (1-s)/4,(1-s)/4和(1-s)/2四部分。張三可得s+(1-s)/2，在s=1/5時(shí)，取得最大值3/5。

對(duì)1/5<=s<=1/3。李四切完變成s, (1-s)/2和（1-s)/2。張三再切，變成(1-s)/4,(1-s)/4和(1-s)/2四部分。張三可得3(1 – s)/4。當(dāng)s=1/5時(shí)，取得最大值3/5。

對(duì)1/3<=s<=3/7。李四切完變成s, (1-s)/2和（1-s)/2。張三再切，變成(1-s)/4,(1-s)/4和(1-s)/2四部分。張三可得(1 + 3s)/4。當(dāng)s=3/7時(shí)，取得最大值4/7。

對(duì)3/7<=s<=1/2。李四切下一塊e大小的餅，變成e, s和1-s-e，其中e是任意小。張三任意切一下s大小的塊，最后得到e+1-s-e=1-s。當(dāng)s=3/7時(shí)，取得最大值4/7。

綜上所述，張三的最佳策略是可以得到3/5大小的餅。下期再見(jiàn)！

收聽(tīng)“大老李聊數(shù)學(xué)”音頻??????????????????????????????????????? 關(guān)注“大老李聊數(shù)學(xué)”