九頭蛇序列(hydra sequence)可以用這個(gè)“去括號(hào)”游戲說(shuō)明。游戲規(guī)則是：

開(kāi)始時(shí)，構(gòu)造一個(gè)全由"("和")"字符構(gòu)成的括號(hào)字符串，左右括號(hào)必須匹配。比如：

然后按如下規(guī)則對(duì)此括號(hào)串進(jìn)行變換：

1. 步數(shù)=1

2. 去掉一對(duì)最內(nèi)層的括號(hào)，最右側(cè)的優(yōu)先

3. 檢查去掉的括號(hào)的父括號(hào)：

如果該父括號(hào)是最外層括號(hào)，則無(wú)操作；

如果該父括號(hào)不是最外層括號(hào)，則在該父括號(hào)右側(cè)復(fù)制該父括號(hào)全部?jī)?nèi)容。復(fù)制數(shù)量為當(dāng)前步數(shù)。

1. 步數(shù)加一

2. 如果當(dāng)前括號(hào)串只剩下"()"，變換終止；否則回到步驟2.

比如對(duì)："((()))"， 完整變換過(guò)程為：

現(xiàn)在定義hydra(n)序列如下：對(duì)n+1層括號(hào)嵌套，按如上規(guī)則變換所需步驟數(shù)。

比如，之前有關(guān)"((()))"例子，其用了三步變換終止，因此hydra(2)=3。

再比如，對(duì)4層括號(hào)"(((())))" , 它經(jīng)過(guò)37步終止：

因此，hydra(3)=37。

現(xiàn)在的問(wèn)題是，對(duì)hydra(4)，它能在有限步驟內(nèi)結(jié)束嗎？hydra(4)的前100步的括號(hào)字符串長(zhǎng)度變化情況為：

且沒(méi)有終止的跡象。出人意料的是1982年，Kirby, L.和 Paris, J. 證明[1]，對(duì)任意大的n, hydra(n)都是有限的。

更出人意料的是hydra(4)出奇得大，現(xiàn)已證明hydra(4)將遠(yuǎn)大于另一個(gè)出名大數(shù)“葛立恒數(shù)”。

另外hydra(n)的有限性已無(wú)法在皮亞諾算數(shù)公理中證明，因此它也是哥德?tīng)柌煌陚涠ɡ淼囊粋€(gè)例子。

有關(guān)更具體的九頭蛇序列說(shuō)明，請(qǐng)觀(guān)看視頻。

有獎(jiǎng)思考題：

視頻中我有一個(gè)錯(cuò)誤：hydra(n)并不是去括號(hào)游戲的最優(yōu)解法，因?yàn)樗偸莾?yōu)先去除最右邊的括號(hào)，因此這樣的玩法所得步驟數(shù)并不是最少的。那么問(wèn)題來(lái)了，如果我們用optimal_hydra(n)定義為最優(yōu)解法的步數(shù)，那么optimal_hydra(4)的下限是多少？

“去括號(hào)”游戲可能的最優(yōu)玩法是：

總是優(yōu)先去除最內(nèi)層的括號(hào)；

同樣層次的括號(hào)中，總是優(yōu)先去除“兄弟”最多的。因?yàn)檫@些“兄弟”總是要被復(fù)制的，那么提前復(fù)制的話(huà)可以盡量減少?gòu)?fù)制的次數(shù)。

我將對(duì)能給出optimal_hydra(4)最優(yōu)下限甚至確切值的讀者，獎(jiǎng)勵(lì)本人所著《老師沒(méi)教的數(shù)學(xué)》一本。

請(qǐng)將你的計(jì)算結(jié)果和理由發(fā)至dalaoliliaoshuxue@gmail.com ("大老李聊數(shù)學(xué)"的拼音 + @gmail.com)， 截止時(shí)間2021年1月20日。

本文中用到的計(jì)算hydra變化的python代碼：

https://github.com/YouhuaLi/math_misc/blob/master/brackets_hydra_game/bhg.py （隨便寫(xiě)的，效率極差， 見(jiàn)諒。）

參考資料

[1]

Kirby, L.和 Paris, J. 證明: http://logic.amu.edu.pl/images/3/3c/Kirbyparis.pdf