考拉茲猜想：數學還不知如何應對的問題

上面這幅看著像是正在野蠻生長的水藻，又像正在綻放的禮炮的動畫，實際上展示的是一個複雜的數學問題——它為考拉茲猜想(Collatz conjecture)提供了一個新視角。

考拉茲猜想是數學中最引人注目的難題之一，它也被稱為奇偶歸一猜想、3n+1猜想、冰雹猜想還有角谷猜想等等。這個猜想的很容易掌握，你只需要知道如何加1，如何除以2，以及何乘以3就行了。

然而，這般的簡單性卻與證明猜想本身的難度形成了鮮明的對比。著名數學家保羅·埃爾德什（Paul Erdös）曾說：「數學還沒有做好準備面對這樣的問題。」上圖中的動畫就為大家展示了為什麼這是一個如此難於破解的問題。

（保羅•埃爾德什是發表過論文數量最多的數學家，論文總數約1500多篇，與511位數學家合作編寫過論文。也是著名數學華裔家陶哲軒的伯樂）

它的運算規則非常簡單：首先，取一個任意正整數，根據以下規則進行運算

• 若數字為偶數，則將其除以2;

• 若數字為奇數，則讓其乘以3，再加1，再除以2;

• 重複上述過程。

我們以數字13為例：

• 13是奇數，所以我們將其乘以3倍得到39，加1得到40，減半后得到20;

• 再用20來重複這個計算，20是偶數，所以只需減半得到10；

• 10也是偶數，除以2后得到5；

• 5是奇數，乘以3、再加1再減半，得到8；

• 8為偶數，除以2等於4；

• 4再減半得到2；

• 最後2除以2得到1。

因此13的完整序列為：13 → 20 → 10 → 5 → 8 → 4 → 2 → 1

考拉茲猜想首先由德國數學家Lothar Collatz在1937年提出：無論選擇什麼正整數作為開始，通過應用上述的規則，最終都會得到1。

大多數數學家都認為這是正確的。我們已經可以通過計算機來檢測非常龐大的數字，就目前結果來看還沒發現任何反例。但至今也仍沒有人知道該如何證明這個猜想。

上圖顯示的是我們一般在討論該猜想的書籍或論文中常常看到的樹形圖。對於樹中的每個數字在分支以從上往下的方向顯示考拉茲序列中的數字， 例如之前列舉的數字13，順著13往下找便能找到根據考拉茲規則計算出的那一系列數字。由於迄今為止調查到的所有數字都會到達4、2，最後再到1，因此所有數字都是起源於同一樹中的分支。

為了說明這個問題為何如此複雜，費耶特維爾的阿肯色大學的數學藝術家埃德蒙·哈里斯(Edmund Harriss)在標準圖的基礎上新添了一條關於分支方向的規則，用來反映一個數字是由兩種演算法中的哪一種運算而生成，如上圖所示。

這種曲折揭示了從一個給定數字到1的路徑有多難以預測。無論你處在樹枝中的哪個數字，如果在你上面的數字是你的兩倍，則上端分支會以固定角度向順時針方向轉動；如果不是兩倍，則以固定角度向逆時針方向轉動。

我們將數字去掉，並將分支的線條加粗(如上右圖)，就得到了文章開頭的動畫中所顯示的大致樣子。這幅動畫顯示樹在包含10000以下的所有數字時會如何生長。它完美的為我們展示了一個簡單有序的規則是如何造成嚴重的混亂和無序的：整個結構看起來自然又野蠻。哈里斯所製作的這些圖像讓我們順接了解到，為什麼要解決考拉茲猜想會如此困難。

有什麼是我們已經可以證明的呢？

首先，我們可以證明，4、2、1是唯一簡單的固定循環模式。一個簡單的循環模式意味著它只涉及到一個奇數，因此 3n + 1在這個過程中只使用一次。在4、2、1中，唯一的奇數是1，唯一一次需要用到 3n + 1 的機會是將1轉換為4。

假設一個簡單的循環模式包含奇數n，那麼 3n + 1 必須是 2n 的倍數。因為我們必須能夠從 3n + 1 除以 2 這個過程中返回到數字 n。也就是說：

3n + 1 = y2n，

其中 y 是一個正整數。

若 y 是正整數，那麼可取到的最小的值是1，即如果 y = 1，那麼

3n + 1 = 2n。

這個等式顯然不對，因為 n 是一個正整數。取下一個最小正整數y，即 y = 2，我們得到等式：

3n + 1 = 4n，

得出 n = 1。從而得到重複模式1、4、2、1、4、2.…… 如果繼續增加 y 的值，讓 y ≥ 3，則有

3n + 1 =y2n ≥ 6n，

這意味著

1 ≥ 3n，

所以

1/3 ≥ n。

同樣，因為 n 是正整數，所以這個不等式也不對。因此，我們已經證明4、2、1是唯一簡單的重複模式。如果一個考拉茲序列最終落在一個簡單的循環模式上，那麼這個模式必須是4、2、1…… 然而，這並不能證明沒有含有多於一個奇數的重複模式。

另外一件可以證明的事是，有無數的數字能產生循環性模式4、2、1。實際上，任何以 n = 2^m 的形式的數字 n，其中 m 是正整數時，最終都會產生循環在4、2、1周期上的序列。顯然這樣的數字 n 為偶數，所以對 n 來說考拉茲過程的第一步是將它除以 2 得到 2^(m-1) 。如果 m-1 = 0，那麼 2^(m-1) = 1，證明已經到達4、2、1周期；如果 m-1> 0，那麼 2^(m-1) 是偶數，所以下一步運算也是除以2。

重複這個過程表明序列中的所有數字均為偶數，所以進程中的所有步驟都是除以2，所以最終都會降至4、2、1。這對於任何正整數m都成立的，因此證明了有無限多的數字在考拉茲序列中最終落在這個周期上。但同樣的道理，這並不能證明每個數字在考拉茲運算中都會產生一個4，2，1的序列。如果你覺得這聽上去有點拗口，這有一個簡單的類比：偶數有無窮個，但並不是每一個數字都是偶數。

考拉茲猜想看似簡單，實際卻如此複雜。真心期待能早日看到全部的證明過程。

參考來源：