3 · n 1 問題

Collatz 猜想也叫做 3 · n 1 問題。這可能是數學中最為世人所知的未解之謎。它是如此初等，連小學生都能聽懂它的內容；但解決它卻如此之難，以至于 Paul Erd?s 曾說：“或許現在的數學還沒準備好去解決這樣的問題。”這究竟是一個什么樣的問題呢？讓我們來看一下 Collatz 猜想的敘述：

舉個例子，如果 n = 26 ，那么經過下面 10 步之后，它最終變為了 1 ：

隨便取一個其他的自然數，對它進行這一系列的變換，或遲或早，你總會掉到4→2→1這個循環中，或者說，你總會得到1。已經有人對所有小于100*2^50=112589990684262400的自然數進行驗算，無一例外。Collatz 猜想說的就是，這個規律對于所有正整數 n 均是如此。

這個問題大約是在二十世紀五十年代被提出來的。在西方它常被稱為西拉古斯(Syracuse)猜想，因為據說這個問題首先是在美國的西拉古斯大學被研究的；而在東方，這個問題由將它帶到日本的日本數學家角谷靜夫的名字命名，被稱作角谷猜想。

這個問題看起來是如此簡單，以至于無數的數學家都掉進了這個坑里。光從這個問題的眾多別名，便能看出這個問題害人不淺： Collatz 猜想又叫做 Ulam 猜想、 Kakutani 問題、 Thwaites 猜想、 Hasse 算法、 Syracuse 問題……研究這個問題的人很多，解決這個問題的人卻一個沒有。后來，人們干脆把它叫做 3 · n 1 問題，讓哪個數學家也不沾光。

角谷靜夫在談到這個猜想的歷史時講：'一個月里，耶魯大學的所有人都著力于解決這個問題，毫無結果。同樣的事情好象也在芝加哥大學發生了。有人猜想，這個問題是蘇聯克格勃的陰謀，目的是要阻礙美國數學的發展。'不過我對克格勃有如此遠大的數學眼光表示懷疑。這種形式如此簡單，解決起來卻又如此困難的問題，實在是可遇而不可求。

數學家們已經發表了不少篇嚴肅的關于3 · n 1 問題的數論論文，對這個問題進行了各方面的探討，可是這個問題的本身始終沒有被解決，我們還是不知道，'到底是不是總會得到1？'

要是真的有這么一個自然數，對它反復作上面所說的變換，而我們永遠也得不到1，那只可能有兩種情況：

1)它掉到另一個有別于4→2→1的循環中去了。我們在后面可以看到，要是真存在這種情況，這樣一個循環中的數字，和這個循環的長度，都會是非常巨大的；

2)不存在循環。也就是說，每次變換的結果都和以前所得到的所有結果不同。這樣我們得到的結果就會越來越大（當然其中也有可能有暫時減小的現象，但是總趨勢是所得的結果趨向無窮大）。

圖片源自豆瓣

這個問題有多難呢？我們可以從下面的這個例子中略見一斑。雖然從 26 出發只消 10 步就能變成 1 ，但若換一個數，比如 27 ，情況就大不一樣了：

可見，當 n 的值不同時，從 n 變到 1 的路子是很沒規律的。

有趣的是，如果我們把 Collatz 猜想中的乘以 3 改為乘以任意一個 3x （其中 x 的值可由你自由選擇），那么 Collatz 猜想就是正確的了。下面我們就來證明這一點。

首先我們證明一個引理：任何一個正整數都可以表示成下面這樣：

2a1 × 3b1  2a2 × 3b2  2a3 × 3b3  … 2an × 3bn

其中 0 ≤ a1 < a2 < a3 < … < an ，并且 b1 > b2 > b3 > … > bn ≥ 0 。舉個例子， 213 = 34  22 × 32  25 × 3 就是一種合法的表示法。

反證，假設有的數不能用這種方法來表示，那么一定存在一個最小的不能用這種方法來表示的數，不妨把它叫做 y 。顯然 y 不能是偶數，否則把 y/2 的表示法中的每一項都再乘以一個 2 ，就能得到 y 的一種合法表示了。如果 y 是奇數呢？無妨假設 3i ≤ y < 3i 1 ，其中 i 是某個適當的正整數。于是， y′ = y – 3i 就是一個偶數，并且 y′/2 < 3i 。把 y′/2 的表示法中的每一項都再乘以一個 2 ，再在最前面加上一個 3i ，就能得到 y 的一種合法表示了。

下面我們就來證明，不斷地執行 n → 3x · n 1 （當 n 為奇數時）以及 n → n/2 （當 n 為偶數時）的變換，任何一個正整數最終都能變為 1 。還是以 27 為例。問題改版后，把 27 變成 1 的步驟數能大大減少：

(((((27 × 32  1) / 22 × 3 1) / 23 × 32  1) / 24 × 3 1) / 23 × 3 1) / 24 = 1

在這個過程中，我們一共除以了 16 個 2 。也就是說，上式中所有 2 頭上的指數之和是 16 。想一想，如果等式兩邊同時乘以 216 ，結果會怎樣？結果是，等式左邊就不再有除法了：

27 × 37  35  22 × 34  25 × 32  29 × 3 212 = 216

其中，等式左邊的 35  … 212 ，正好是 216 – 27 × 37 的一個合法的表示法！

所以，為了證明某個正整數 n 最終能變為 1 ，我們只需要證明，存在適當的 a 和 b ，使得 2a – n · 3b 有一個合法的表示法，并且表示法第一項里 3 的指數小于 b 。

由于 log32 為無理數，因而很容易看出，對于任意的正整數 n ，我們總能找到一個 b ，使得 [n · 3b, (n 1) · 3b) 區間內包含某個 2 的整數次冪。把這個 2 的整數次冪記作 2a 。既然每一個正整數都有一個合法的表示法，那么 2a – n · 3b 也有一個合法的表示法。而 2a – n · 3b < 3b ，因而它的表示法第一項里 3 的指數一定小于 b 。

本文最后，讓我們再對上一段中第一句話的結論作出一些額外的解釋。設想有一個總長為 1 的圓形軌道，軌道上有一個周長為 r 的輪子，其中 r 為某個大于 0 的無理數。在輪子上的某個位置涂一個墨點。讓輪子從圓形軌道上的某一位置出發，沿著軌道往前滾動。每次墨點接觸軌道時，都會在軌道上留下一個記號（輪子上的墨點不會干掉，滾過已有的記號時也不會反過來沾上墨點）。我們可以證明一個結論：輪子沿著軌道一圈一圈地滾動下去之后，軌道上的各個地方都會稠密地分布著記號。

首先，任意兩個記號的位置都不會重合，否則某個整數倍的 r 就會等于某個整數，這與 r 的無理性相矛盾。因此，輪子轉了無窮多圈之后，軌道上也會留下無窮多個記號。取任意大的正整數 N ，把軌道平均分成 N 份，每份的長度都是 1/N 。根據鴿籠原理，一定有兩個記號落入了同一份里。這兩個記號之間的距離 d 小于 1/N 。不妨假設輪子從先產生的那個記號出發，轉了 k 圈之后來到了后產生的那個記號；那么，從此處出發再轉上 k, 2k, 3k, …圈，就會繼續得到一系列間隔為 d 的記號。如果正整數 N 足夠大，間隔 d 就會足夠小，由此產生的記號也就會足夠密地分布在整個軌道上了。

為什么對于任意的正整數 n ，我們總能找到一個 b ，使得 [n · 3b, (n 1) · 3b) 區間內包

含某個 2 的整數次冪呢？

在對數尺度下，這就化為了剛才討論的問題。 [n × 30, n × 31), [n × 31, n × 32), [n × 32, n × 33), … 成為了一個個等長的區間，區間的長度都是 log(3) 。而 20, 21, 22, … 也就成了一系列的等距點，相鄰兩個點之間的距離是 log(2) 。如果把 log(3) 的長度看作 1 個單位，那么 log(2) 的長度就是 log(2) / log(3) = log32 個單位，這是一個無理數。這就完全相當于周長為 log32 的輪子沿著總長為 1 的圓形軌道滾動。根據剛才的結論，由此得到的標記將會稠密地分布在這些等長區間內的各種位置，當然也就會有不少標記落進了形如 [n · 3b, (n 1) · 3b) 的區間里。

via：Matrix67，百度百科

模型研究、文章投稿歡迎聯系數模君：

supermodeling@163.com