通常我們拿到一份紙質版的地圖
都是這樣折疊起來的
展開後是這樣
我們開箱一樣新買的小電器
裡面通常有這樣折疊好的說明書
而且
現在越來越多的說明書折疊得非常新穎
獨具風格
於是
這在數學上給我們帶來了一個有趣的問題
比如說，展開後是這樣2X4格子的地圖
有多少種不同的折疊方法呢？
也許你會覺得這是一個很簡單的數學問題
隨便一個中學生稍微細緻一點
都可以毫不費力地得到正確答案
但是，如果我告訴你
計算這樣的地圖折疊方法數
截止目前仍然是還未解決的數學難題
你會怎麼想呢？
說不定，這會反過來激發出你的鬥志
那麼，就請你暫停視頻
挑戰一下這個問題
熟悉咱們頻道風格的朋友都知道
我們一向的方法都是先簡化問題
從最簡單的角度出發來嘗試回答問題
一個2X4格子的地圖
有一種方法是我們先將地圖對折為一個長條
看看1X4的格子有多少種不同的折疊方法
在數學界
計算把一張方形紙折疊為mXn的格子的方法數量
被稱之為地圖折疊問題
計算把一張長條紙折疊為n格的方法數量
被稱之為郵票折疊問題
顯然，郵票折疊問題要簡單得多
我們就先來研究郵票折疊問題
這實際上是一個一維問題
也就是將一條直線
折疊為n條線段的方法數
首先我們來看看n=1
也就是不需要折疊
這當然只有一種狀態
我們就記為S1=1
n=2，我們可以這麼折疊過來
也可以反向折疊
或許有人會說，這兩種方法是一樣的
如果這代表的紙或者說郵票有正反面
那麼它當然就不是一樣的折疊方法
如果沒有正反面之分
從對稱角度來說
當然是一樣的折疊
為了避免一開始的麻煩
我們先不考慮對稱相等的問題
稍後我們再來討論對稱性
所以，我們認為S2=2
到n=3，就需要動一些腦筋了
有沒有人認為，多了一次折疊的機會
就是在原來折疊的基礎上
分別多了一次正疊和反疊的機會
於是乘以2就可以，得到S3=S2X2=4呢？
但是
如果你用身邊的紙條實際折疊一下
或者你仔細注意到我們剛剛的演示動畫
就會發現這麼思考是錯誤的
實際上多出的這一次折疊機會
在原有基礎上多出的不僅僅是一次正疊和一次反疊
這種情況下的反疊是有兩種不同的結果
反疊後的線條所處位置可以不一樣
而在這種情況下反疊是一次
正疊是兩次
所以S3=6
雖然，剛剛的想法不是完全正確的
但是，多一次折疊機會
一定可以在原有折疊方法的基礎上
至少形成一個正疊和一個反疊
這個思考是正確的
也就是說Sn+1一定是大於等於2倍Sn的
考慮到S1=1，S2=2
所以我們可以得到Sn≥2的n-1次方這個結論
我們再來多看一看n=3的這6種不同的折疊方法
如果將這3疊編上1、2、3的號碼
可以很明顯地發現，6種不同的折疊
對應的其實就是1、2、3的不同排序方式
3個數的排序方法數
對我們來說就太簡單了
就是3的階乘，當然等於6
而且，我們知道，這不是一種巧合
所謂的不同折疊方法
不就是想辦法讓每一段的紙片排在不同的位置嗎？
如果我們依據n=1、2、3的經驗
能夠得到Sn=n！
那麼這個問題也算不上什麼難題
接下來我們就來檢驗一下這個結論是否適合n=4
4！=24，把一張紙條折成4疊
能夠折出不同的狀態
我們從n=3的6種狀態出發
依次添加，結果是這樣的
數一下，一共有16種
很顯然，4！
這個計算方法是不對的
同樣編上號，我們馬上就能看出
這樣的4個數排序是不可能折疊出來的
但是，明顯的結論是
不論怎樣折疊
不同的折疊方法對應的都是不同的排序方式
也就是說，不論如何折疊
折疊的方法數最大是n！。
於是我們得到一個結論
2的n-1次方小於等於Sn
小於等於n！。
還有其他方法能夠幫助我們
確切地知道Sn和n之間的關係嗎？
我們能夠從n個折疊增加到n+1個折疊的過程中
總結出遞推規律
進而計算出Sn嗎？
從剛才n=3到n=4的演變過程中
我們發現
多一次折疊機會
增加的折疊方式有可能是兩倍
也有可能是三倍
繼續觀察從n=4到n=5
這次我們不畫出具體的結果
只是統計每一種狀態多一次折疊機會帶來的變化
得到的結果是這樣的
分別有兩倍、三倍、四倍的情況出現
得到S5=50
觀察這些過程
我們除了能夠清晰看到
每多一次折疊機會
至少會帶來兩種變化以外
很難得到其他的固定規律
多一次機會
可以帶來的變化數量是沒有上限的
比如n=6的這個狀態到n=7
可以帶來5種變化
所以
我們暫時沒辦法從遞推關係計算出Sn的表達式
當然，我們可以換一個角度來思考
折疊紙條
只有向內折疊和向外折疊兩種方式
從折痕來看
就是所謂的峰和谷的差別
對於任意的n
形成的折痕數量都是n-1個
這n-1個折痕都有可能是峰或者谷
組合方式就一共有2的n-1次方種
我們可以用1和0分別來表示峰和谷
也就是用一個二進制的數對應了一種折痕狀態
剛才我們已經說了
折疊種類是不小於2的n-1次方的
也就是有的二進制數對應了不止一種折疊方式
從這個角度我們能看出什麼規律來嗎？
很遺憾，如果說這也是一個函數的話
我們依然不知道這個函數的表達式
既然無法從一個固定的表達式計算出Sn
人類可以依靠的就是計算機了
借助計算機
數學家得到了數列Sn前面若干項的數值
那我們再換一個角度
從已知的這些結果中能夠得到什麼規律嗎？
最簡單的是
如果後一項和前一項的比值能夠相同
或者趨向於某個數值
或者呈現出某種規律
對於我們的計算
或許對估算也能有所幫助
然而，這個比值同樣是變幻莫測的
我們只是知道它大致處於3.2到4.0之間
並沒有表現出趨向於某一個固定值的特徵
如果用對數坐標來表示它的變化趨勢的話
可以看出它大致是一條直線
所以，對於一張紙條折成n疊
有多少種不同折疊方式的問題
看起來非常簡單，實際上到目前為止
這仍然是一匹未經馴服的野馬
我們無法得到Sn的準確軌跡
只知道它處於2的n-1次方和n！之間
討論了這麼多
雖然沒有得到明確的結論
但是我們對於郵票折疊問題的瞭解還是深入了很多
接下來我們就要看看，如果不是郵票
而是沒有正反面和前後區別的紙條
那麼這些不同的折疊方法通過對稱變換
其實都是同一種
以n=4為例，考慮到對稱性後
不同的折疊方法就只剩下5鐘了
同樣用計算機
我們可以得出考慮對稱性後一張紙條折為n疊
不同的折疊方法數是這樣的
解釋了郵票折疊問題
我們再來看地圖折疊的問題
實際上是將一個一維問題擴展為二維問題
一張地圖，如果折疊為mXn個方格
不同的折疊方式有多少種呢？
理論上數學家的目標是要找到一個函數f(m n)來計算
但是，如同我們剛剛介紹的
這個函數的具體表現形式
目前來說，還離我們非常遙遠
當前我們只能借助計算機
得到一些特定的m和n對應的方法數
在這裡羅列了m=2
也就是橫向只是對折一次的情況下
這樣的折疊方法數
我們可以計算一下，它和m=1
也就是郵票折疊數的比值
很不幸
這個比值並不能讓我們看到什麼規律
甚至它都不是一個整數
說明地圖折疊比起郵票折疊要複雜得多
我們甚至不能簡單地利用郵票折疊的結果
介紹到這裡
不知道大家是否能夠充分理解
地圖折疊是一個仍然沒有被解決的數學難題
最近幾期視頻
大家都在討論為什麼數學家要研究這樣的數學
當然，標準答案是不需要回答為什麼
就像登山家回答為什麼要登山的問題
唯一的理由就是它在這裡
然而，對於地圖折疊研究的成果
居然就馬上被工業界利用了
一個最直接的例子就是掃地機器人的線路規劃問題
當掃地機器人探索清楚地面的邊界之後
如何高效地一次性、
盡可能不重復地清掃完所有地面？
這個問題和地圖折疊問題高度相似
當然
掃地機器人並不需要羅列出所有的折疊可能性
它需要借助的是判斷一個折疊是否存在的算法
如果你對此感興趣，不妨思考一下
對於一個nXn的地圖折疊問題
利用計算機
應該如何來計算它一共有多少種不同的折疊方法呢？
在我們前面的介紹中
大家多多少少能夠看到
即便用最笨的方法，從n到n+1
計算機是可以用枚舉的方法解決1Xn的郵票折疊問題
但是，對於nXn的地圖折疊
枚舉這種笨辦法已經失靈
或者說將耗費巨大的算力
可以看到，當n=7的時候
這個數字已經高達一百萬億以上
而且
問題的關鍵還不是這個天文數字的巨大
而是得到這個數字要耗費的計算機算力遠超過想象
乃至於，在沒有更優的算法之前
數學家拒絕用寶貴的算力去計算n=8的結果
一件更有意思的事情是
數學家雖然沒有搞清楚一維、二維的地圖折疊問題
但是並不妨礙他們已經開始研究
三維、四維、乃至更高維的地圖折疊問題
如何得到更優的算法
請大家在評論區分享你們的想法
如果喜歡
請點贊、收藏、轉發我們的視頻
並訂閱我們的頻道
你的支持就是我們前行的動力
发表回复