角谷猜想（3x+1猜想）著名的數(shù)學(xué)猜想 2010-03-11 19:06:38 閱讀175 評(píng)論1 字號(hào)：大中小 訂閱 3x+1問(wèn)題
一、一個(gè)簡(jiǎn)單的問(wèn)題
當(dāng)我們閱讀數(shù)學(xué)史時(shí)，會(huì)有這樣一種印象，數(shù)學(xué)家們首先研究簡(jiǎn)單的 問(wèn)題，然后研究越來(lái)越復(fù)雜的問(wèn)題。經(jīng)常性地，高深的數(shù)學(xué)問(wèn)題是非 常復(fù)雜的。只是為了理解問(wèn)題，我們就得學(xué)習(xí)非常多的數(shù)學(xué)知識(shí)；而 為了解決它，那就得用更復(fù)雜的數(shù)學(xué)知識(shí)了。就算我們?cè)趯W(xué)校里的數(shù) 學(xué)考試也是如此，最后一題經(jīng)常被叫做“最后一大題”，“一大題” 是說(shuō)它表達(dá)復(fù)雜，里面還有一二三四的小題，要理解題意就得幾分鐘 的時(shí)間。弄不好還理解錯(cuò)了，搞得整道題都白白做，被扣去許多分。 可是數(shù)學(xué)里不只有這些嚇人的“大題”——我是說(shuō)，數(shù)學(xué)里還有嚇人 的“小題”。這樣的“小題”理解起來(lái)非常容易，卻讓無(wú)數(shù)數(shù)學(xué)家大 跌眼鏡，怎么冥思苦想也不得其解。3x+1問(wèn)題大概就是其中最著名而 又最簡(jiǎn)單的一個(gè)。它簡(jiǎn)單到大概任何一個(gè)會(huì)除2和會(huì)乘3的人（比如說(shuō)， 沒(méi)文化但是經(jīng)常買菜的老奶奶）都能理解它的意思，但是困難得讓數(shù) 學(xué)家至今也沒(méi)有找到好好對(duì)付它的方法。 任取一個(gè)自然數(shù)，如果它是偶數(shù)，我們就把它除以2，如果它是奇數(shù)， 我們就把它乘3再加上1。在這樣一個(gè)變換下，我們就得到了一個(gè)新的 自然數(shù)。如果反復(fù)使用這個(gè)變換，我們就會(huì)得到一串自然數(shù)。 比如說(shuō)我們先取5，首先我們得到3*5+1=16，然后是16/2=8，接下去 是4，2和1，由1我們又得到4，于是我們就陷在4→2→1這個(gè)循環(huán)中了。 再舉個(gè)例子，最開始的數(shù)取7，我們得到下面的序列： 7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 這次復(fù)雜了一點(diǎn)，但是我們最終還是陷在4→2→1這個(gè)循環(huán)中。 隨便取一個(gè)其他的自然數(shù)，對(duì)它進(jìn)行這一系列的變換，或遲或早，你 總會(huì)掉到4→2→1這個(gè)循環(huán)中，或者說(shuō)，你總會(huì)得到1。已經(jīng)有人對(duì)所 有小于100*250=112589990684262400的自然數(shù)進(jìn)行驗(yàn)算，無(wú)一例外。 那么，是否對(duì)于所有的自然數(shù)都是如此呢？ 這看起來(lái)是個(gè)多么簡(jiǎn)單的問(wèn)題?。?br>二、克格勃的陰謀？ 這個(gè)問(wèn)題大約是在二十世紀(jì)五十年代被提出來(lái)的。在西方它常被稱為 西拉古斯(Syracuse)猜想，因?yàn)閾?jù)說(shuō)這個(gè)問(wèn)題首先是在美國(guó)的西拉古 斯大學(xué)被研究的；而在東方，這個(gè)問(wèn)題由將它帶到日本的日本數(shù)學(xué)家 角谷靜夫的名字命名，被稱作角谷猜想。除此之外它還有著一大堆其 他各種各樣的名字，大概都和研究和傳播它的數(shù)學(xué)家或者地點(diǎn)有關(guān)的： 克拉茲(Collatz)問(wèn)題，哈斯(Hasse)算法問(wèn)題，烏拉姆(Ulam)問(wèn)題等 等。今天在數(shù)學(xué)文獻(xiàn)里，大家就簡(jiǎn)單地把它稱作“3x+1問(wèn)題”。 角谷靜夫在談到這個(gè)猜想的歷史時(shí)講：“一個(gè)月里，耶魯大學(xué)的所有 人都著力于解決這個(gè)問(wèn)題，毫無(wú)結(jié)果。同樣的事情好象也在芝加哥大 學(xué)發(fā)生了。有人猜想，這個(gè)問(wèn)題是蘇聯(lián)克格勃的陰謀，目的是要阻礙 美國(guó)數(shù)學(xué)的發(fā)展。”不過(guò)我對(duì)克格勃有如此遠(yuǎn)大的數(shù)學(xué)眼光表示懷疑。 這種形式如此簡(jiǎn)單，解決起來(lái)卻又如此困難的問(wèn)題，實(shí)在是可遇而不 可求。 數(shù)學(xué)家們已經(jīng)發(fā)表了不少篇嚴(yán)肅的關(guān)于3x+1問(wèn)題的數(shù)論論文，對(duì)這個(gè) 問(wèn)題進(jìn)行了各方面的探討，在后面我會(huì)對(duì)這些進(jìn)展作一些介紹。可是 這個(gè)問(wèn)題的本身始終沒(méi)有被解決，我們還是不知道，“到底是不是總 會(huì)得到1？” 在1996年B. Thwaites懸賞1100英鎊來(lái)解決這個(gè)問(wèn)題。我寫一下這個(gè) 懸賞的文獻(xiàn)：Thwaites, B. “Two Conjectures, or How to win ￡1100.”Math.Gaz. 80, 35-36, 1996，好在大家萬(wàn)一證出來(lái)時(shí)知 道跑哪里去領(lǐng)獎(jiǎng)。看在錢大爺?shù)姆萆希?x+1問(wèn)題于是又多了個(gè)名字， 叫Thwaites猜想。 要是真的有這么一個(gè)自然數(shù)，對(duì)它反復(fù)作上面所說(shuō)的變換，而我們永 遠(yuǎn)也得不到1，那只可能有兩種情況。 1)它掉到另一個(gè)有別于4→2→1的循環(huán)中去了。我們?cè)诤竺婵梢钥吹剑?br>要是真存在這種情況，這樣一個(gè)循環(huán)中的數(shù)字，和這個(gè)循環(huán)的長(zhǎng)度， 都會(huì)是非常巨大的； 2)不存在循環(huán)。也就是說(shuō)，每次變換的結(jié)果都和以前所得到的所有結(jié) 果不同。這樣我們得到的結(jié)果就會(huì)越來(lái)越大（當(dāng)然其中也有可能有暫 時(shí)減小的現(xiàn)象，但是總趨勢(shì)是所得的結(jié)果趨向無(wú)窮大）。 因?yàn)檫@是個(gè)形式上很簡(jiǎn)單的問(wèn)題，要理解這個(gè)問(wèn)題所需要的知識(shí)不超 過(guò)小學(xué)三年級(jí)的水平，所以每一個(gè)數(shù)學(xué)愛好者都可以來(lái)碰碰運(yùn)氣，試 試是不是能證明它。不過(guò)在這里我要提醒大家的是，已經(jīng)有無(wú)數(shù)數(shù)學(xué) 家和數(shù)學(xué)愛好者嘗試過(guò)，其中不乏天才和世界上第一流的數(shù)學(xué)家，他 們都沒(méi)有成功。如果你在幾小時(shí)內(nèi)就找到了一個(gè)“證明”，那么把它 一步一步地嚴(yán)格地寫下來(lái)，看看是不是嚴(yán)密正確（我可以肯定它是錯(cuò) 的，我這樣的肯定要冒的危險(xiǎn)絕不超過(guò)連續(xù)中十次彩票頭獎(jiǎng)的概率， 既然我不買彩票，我就沒(méi)道理不這么肯定:-)）。事實(shí)上，在互聯(lián)網(wǎng)上 已經(jīng)有一些錯(cuò)誤的“證明”。據(jù)說(shuō)還有個(gè)數(shù)學(xué)愛好者跑到公證處去公 證他的“證明”，生怕別人把他的好主意偷跑了。 二十多年前，有人向偉大的數(shù)論學(xué)家保爾·厄爾多斯(Paul Erdos)介 紹了這個(gè)問(wèn)題，并且問(wèn)他怎么看待現(xiàn)代數(shù)學(xué)對(duì)這問(wèn)題無(wú)能為力的現(xiàn)象， 厄爾多斯回答說(shuō)：“數(shù)學(xué)還沒(méi)有準(zhǔn)備好來(lái)回答這樣的問(wèn)題。” 三、一些概念，一些紀(jì)錄 雖然證不出猜想，但是數(shù)學(xué)家們還是得到了許多很可能很有用的結(jié)論。 讓我們先來(lái)定義幾個(gè)概念，然后再來(lái)介紹這些結(jié)論。 從一個(gè)自然數(shù)開始，用上面這個(gè)變換，我們可以計(jì)算出一串自然數(shù)的 序列。為了形象起見，我們把這串?dāng)?shù)列叫做以最初用來(lái)開始計(jì)算的那 個(gè)自然數(shù)命名的“航班”。比如說(shuō)，第6次航班就是 6→3→10→5→16→8→4→2→1 我們把一個(gè)航班里的最大數(shù)字，叫做這個(gè)航班的“最大飛行高度”。 比如說(shuō)，第6次航班的最大飛行高度就是16。我們把航班在數(shù)字1“著 陸”之前的數(shù)字個(gè)數(shù)（最初的數(shù)字包含在內(nèi)，但1不包含在內(nèi)），叫 做這個(gè)航班的“航程”（特別定義第1次航班的航程為0）。第6次航 班的航程就是8。如果真有自然數(shù)在此變換下永遠(yuǎn)達(dá)不到1，那么這個(gè) 航班的航程就是無(wú)窮了。 接下去的概念稍微有點(diǎn)復(fù)雜。我們把從起點(diǎn)開始（但不包括起點(diǎn)）連 續(xù)的不小于起點(diǎn)的數(shù)字的個(gè)數(shù)，叫作“保持高度航程”。舉一個(gè)例子 來(lái)說(shuō)明這個(gè)概念比較方便：第11次航班是 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 我們看到從起點(diǎn)開始，34，17，52，26，13，40，20都不小于起點(diǎn)11， 共有7個(gè)數(shù)字，所以第11次航班的保持高度航程為7。后面的航程中雖 然還有數(shù)字16大于起始點(diǎn)11，但是它不被算在保持高度航程里了。一 個(gè)最簡(jiǎn)單的推論就是，偶數(shù)次航班的保持高度航程總是0，因?yàn)殚_始就 除以2，跌到較低的高度去了。 為什么我們對(duì)一個(gè)航班的保持高度航程感興趣？因?yàn)槿绻泻桨嗟?br>保持高度航程都是有限的話，3x+1問(wèn)題就成立了。讓我們假設(shè)已知所 有航班的保持高度航程都是有限的，用數(shù)學(xué)歸納法來(lái)證明3x+1問(wèn)題， 也就是所有的航班都在1上“著陸”。我們已經(jīng)知道第1到第5航班都 是在1上著陸的，現(xiàn)在假設(shè)對(duì)于所有小于n的數(shù)字k，第k次航班都在1 上著陸，我們來(lái)看看第n次航班的情況：由于按假設(shè)它的保持高度航 程是有限的，所以它遲早會(huì)降落在一個(gè)比n小的數(shù)字上——于是按歸 納假設(shè)它就會(huì)降落在1上！ 我們可以對(duì)開始的30班航班列出一個(gè)相關(guān)數(shù)據(jù)表來(lái)： 航班 航程 保持高度航程 最大飛行高度 1 0 0 1 2 1 0 2 3 7 5 16 4 2 0 4 5 5 2 16 6 8 0 16 7 16 10 52 8 3 0 8 9 19 2 52 10 6 0 16 11 14 7 52 12 9 0 16 13 9 2 40 14 17 0 52 15 17 10 160 16 4 0 16 17 12 2 52 18 20 0 52 19 20 5 88 20 7 0 20 21 7 2 64 22 15 0 52 23 15 7 160 24 10 0 24 25 23 2 88 26 10 0 40 27 111 95 9232 28 18 0 52 29 18 2 88 30 18 0 160 下面要說(shuō)說(shuō)幾個(gè)記錄。在上面我們已經(jīng)說(shuō)過(guò)，目前3x+1問(wèn)題已經(jīng)被檢 驗(yàn)到100*250=112589990684262400，都沒(méi)有發(fā)現(xiàn)反例。這是葡萄牙阿 弗羅(Aveiro)大學(xué)的Tomas Oliveira e Silva的工作，用了很巧妙 的編程方法。他的主頁(yè)在http://www./~tos/3x+1.html 如果一個(gè)航班的航程大于所有它前面的航班的航程，我們就把它叫作 “航程紀(jì)錄航班”，比方說(shuō)第7航班，它的航程是16，比第1到6次航班 的航程都長(zhǎng)，所以第7航班是個(gè)航程紀(jì)錄航班。今天我們已經(jīng)知道的航 程紀(jì)錄航班有118個(gè)，航程最長(zhǎng)的是2234047405400065次航班，它的 航程是1871，這是Eric Roosendaal發(fā)現(xiàn)的，他有個(gè)個(gè)人網(wǎng)站 http://personal./eric/wondrous/， 里面有各種各樣關(guān)于3x+1問(wèn)題的信息，下面的記錄也都來(lái)自這個(gè)網(wǎng)站。 同樣的，如果一個(gè)航班的保持高度航程大于所有它前面的航班的保持 高度航程，我們就把它叫作“保持高度航程紀(jì)錄航班”，比方說(shuō)從上 面的表中我們看到第7航班也是個(gè)保持高度航程紀(jì)錄航班。今天已知的 保持高度航程紀(jì)錄航班有30個(gè)，航程最長(zhǎng)是1008932249296231次航班， 它的保持高度航程是1445。 最大飛行高度記錄航班就是那些最大飛行高度記錄大于所有它前面的 航班的那些航班，現(xiàn)在已知的有76個(gè)，最大的是10709980568908647 次航班，到達(dá)了350589187937078188831873920282244的高度。 對(duì)于一個(gè)固定航班N，考慮它在1著陸之前所作的變換，如果把其中除 以2的變換稱為“偶變換”并記為E(N)，而把乘以3再加1的變換稱為 “奇變換”并記為O(N)。數(shù)學(xué)家已經(jīng)證明，O(N)/E(N) 我們注意到，對(duì)有些航班來(lái)說(shuō)，O(N)/E(N)非常接近于log2/log3≈ 0.63092975……。有猜想認(rèn)為它會(huì)越來(lái)越接近這個(gè)數(shù)字（也有相反的 猜想，認(rèn)為不會(huì)無(wú)限接近），所以大家為此設(shè)立了另一個(gè)紀(jì)錄，就是 這個(gè)比值比所有以前的航班更接近log2/log3的航班。這樣的紀(jì)錄不多， 現(xiàn)在已知的有15個(gè)，其中最后一個(gè)是N=100759293214567，I(N)/P(N) ≈0.604938。值得一提的是N=104899295810901231，它的這個(gè)比值 還要更靠近，達(dá)到0.605413，但是我們不知道它是否是一個(gè)紀(jì)錄，也 就是說(shuō)，我們不知道所有比它小的航班里，是否還有比這個(gè)比值更靠 近log2/log3的。 我們知道，對(duì)于任何p，總有至少一個(gè)航班，它的航程是p： 2p→2p-1→2p-2→……→4→2→1 但是一般并不需要這么大的航班，就可以達(dá)到航程p。在2000年有人提 出要找到最小的航班號(hào)，使得它的航程恰好是2000?，F(xiàn)在最好的紀(jì)錄 是第67457283406188652次航班，但誰(shuí)都不知道這是不是最小的航程為 2000的航班。 計(jì)算一個(gè)航班的算法是非常簡(jiǎn)單的——只要除2或乘3加1。但是為了檢 驗(yàn)大量的和航次巨大的航班，巧妙的編程方法是非常重要的。上面的 那些紀(jì)錄都是由幾臺(tái)類似于我們平時(shí)使用的那樣的計(jì)算機(jī)得到的結(jié)果。 但是如果沒(méi)有好好地思考和編程，光是硬算，那么使用最先進(jìn)的計(jì)算 機(jī)恐怕也得不到這樣的結(jié)果。 為了驗(yàn)證一個(gè)航班的確在1上著陸，并不一定需要把結(jié)果計(jì)算到1。如 果你已經(jīng)驗(yàn)證了所有航次小于n的航班都在1上著陸，那么對(duì)于第n次航 班，你只要把結(jié)果計(jì)算到一個(gè)小于n的數(shù)m就可以了——我們已經(jīng)驗(yàn)證 過(guò)第m次航班在1上著陸。事實(shí)上，如果我們只要計(jì)算到一個(gè)以前的航 班飛行時(shí)到達(dá)過(guò)的數(shù)值就可以了，當(dāng)然這需要記住以前已經(jīng)到達(dá)過(guò)的 比較高的高度，這里也必須巧妙地編程使得這樣的記憶所使用的內(nèi)存 比較少。 更重要的是使用數(shù)學(xué)方法去減少計(jì)算量。比如說(shuō)，任何n=4k+1的航班 最終都會(huì)飛到一個(gè)比n更小的高度。首先這是奇數(shù)，我們乘3加1得到 12k+4，然后連除兩次2，就有3k+1 證4k+1型的航班。另外偶數(shù)次航班第一次變換就被除以2，降低了高 度，所以同樣也不需專門驗(yàn)證。只用這樣一個(gè)小技巧，我們就使計(jì)算 量減少到原來(lái)的25%。 如果按照這樣的思路下去，我們同樣不需要考慮16k+3型的航班，只 要考慮到前面的飛行記錄： 16k+3→48k+10→24k+5→72k+16→36k+8→18k+4→9k+2→…… 而9k+2 我們可以這樣追蹤下去，考慮256k+i型的航班，其中i取0到255，那 么我們會(huì)發(fā)現(xiàn)我們需要考慮的類型只有i=27、31、47、63、71、91、 103、111、127、155、159、167、191、207、223、231、239、251、 255。這樣我們要作的計(jì)算只有最初的8%不到。 而Eric Roosendaal得到上面那些紀(jì)錄的程序，是建立在對(duì)65536k+i 型航班分析的基礎(chǔ)上的，其中只有1729種航班需要真正的檢驗(yàn)（只有 原來(lái)計(jì)算量的2.6%）。他的程序還使用了其它的算術(shù)技巧，以及可以 同時(shí)計(jì)算好幾個(gè)航班。Tomas Oliveira e Silva進(jìn)一步改進(jìn)了這些技 巧，從而使得他成為現(xiàn)在3x+1問(wèn)題驗(yàn)證的世界紀(jì)錄保持者（他的計(jì)算 從1996年8月開始，到2000年4月結(jié)束，其間使用了兩臺(tái)133MHz和兩臺(tái) 266MHz的DEC Alpha計(jì)算機(jī)）。Eric Roosendaal還在和其他人一起 合作進(jìn)行計(jì)算（包括再次驗(yàn)證以前的結(jié)果），如果你愿意加入這個(gè)研 究項(xiàng)目的話，可以去訪問(wèn)上面給出的他的主頁(yè)。 四、理論結(jié)果 只要稍微動(dòng)一下腦筋，我們就知道3x+1問(wèn)題和下面幾個(gè)命題都是等價(jià) 的： 1)所有的航班的航程都有限； 2)所有的航班的保持高度航程都有限； 3)所有的航班中的偶變換的次數(shù)都有限； 4)所有的航班中的奇變換的次數(shù)都有限； 5)所有的航班的保持高度航程中偶變換的次數(shù)都有限； 5)所有的航班的保持高度航程中奇變換的次數(shù)都有限。 R. Terra和C. Everett證明了，“幾乎所有的航班都會(huì)下降到它的起 始點(diǎn)以下”，也就是說(shuō)“幾乎所有的航班的保持高度航程都有限”。 這里的“幾乎所有”是有確定的數(shù)學(xué)意義的，它是指： ——存在一個(gè)自然數(shù)n1，在所有小于n1的航班里，最多只可能有1/10 的航班，它們的保持高度航程無(wú)限； ——存在一個(gè)自然數(shù)n2，它比上面的n1要大，在所有小于n2的航班里， 最多只可能有1/100的航班，它們的保持高度航程無(wú)限； ——存在一個(gè)自然數(shù)n3，它比上面的n2要大，在所有小于n3的航班里， 最多只可能有1/1000的航班，它們的保持高度航程無(wú)限； ——等等等等…… 這好象很接近證明“所有的航班的保持高度航程都有限”了，于是很 接近證明猜想本身了。但是好好想想，這個(gè)結(jié)論只不過(guò)是說(shuō)明保持高 度航程無(wú)限的航班會(huì)越來(lái)越稀少罷了，它們還是有可能存在的……更 糟糕的是，這個(gè)結(jié)論一點(diǎn)也沒(méi)有排除有其它循環(huán)存在的可能。 對(duì)于在1上著陸的航班，數(shù)學(xué)家們也得到了一些結(jié)果。他們證明了，存 在一個(gè)常數(shù)c，當(dāng)n足夠大的時(shí)候，在比n小的航班中，能夠在1上著陸 的航班的個(gè)數(shù)大于等于nc。在1978年R. Crandal首先給出c=0.05，雖 然小了點(diǎn)，但畢竟是開頭一步；然后J. Sander給出c=0.3；在1989年 I. Krasikov得到c=0.43；1993年G. Wirsching得到c=0.48；最后在 1995年D. Applegate和J. Lagarias得到c=0.81。看起來(lái)我們?cè)絹?lái)越 接近c(diǎn)=1這個(gè)最終目標(biāo)了?？墒俏覀儾恢垃F(xiàn)在用來(lái)得到c的方法是否 還可以再用下去，就好象在試圖征服哥德巴赫猜想的過(guò)程中，陳景潤(rùn) 用來(lái)證明1+2的方法，似乎不能用來(lái)證明1+1了。 1995年的這個(gè)證明相當(dāng)特殊。它使用了計(jì)算機(jī)程序來(lái)解一個(gè)十分巨大 的方程組，所以這個(gè)證明不能用手工來(lái)驗(yàn)證。在論文中，我們看見的 不是一個(gè)關(guān)于c=0.81的定理的證明，而是一個(gè)關(guān)于如何寫出這個(gè)巨大 方程組的說(shuō)明，和由程序計(jì)算出來(lái)的結(jié)果，以及如何使用這些結(jié)果來(lái) 解釋c=0.81。其他的數(shù)學(xué)家如果想驗(yàn)證這個(gè)結(jié)果，必須首先看懂關(guān)于 方程組的證明和那些解釋，再按照里面的說(shuō)明來(lái)寫一個(gè)程序（很復(fù)雜 的?。?，運(yùn)行它，再看看結(jié)果是否和文章中的相同。目前四色定理的 證明也是如此，所以數(shù)學(xué)家對(duì)此很不滿意。 還有一些結(jié)果是關(guān)于如果有其他不同于4→2→1的循環(huán)存在時(shí)，對(duì)這樣 的循環(huán)的性質(zhì)的研究。R. Crandal和N. Yoneda在1978年證明，如果 這樣一個(gè)另外的循環(huán)存在的話，那么它的長(zhǎng)度（就是在這個(gè)循環(huán)中數(shù)字 的個(gè)數(shù)，比如說(shuō)循環(huán)4→2→1的長(zhǎng)度就是3）一定要大于275000。1993 年這個(gè)體積增大到17087915，最近的結(jié)果是102225496。這些結(jié)果是 通過(guò)分析包括我們前面提到的各種紀(jì)錄得到的，所以這些結(jié)果我們還 是不能完全通過(guò)手工來(lái)驗(yàn)證。我們看到，如果真有另外的循環(huán)存在的 話，那一定是非常非常巨大的！ 五、啟發(fā)式論證 數(shù)學(xué)中有一種叫“啟發(fā)式”的論證方法，建立在估計(jì)和概率的手段上。 比如說(shuō)底下的論證方法就是這個(gè)類型的： “每個(gè)數(shù)字要么是奇數(shù)要么是偶數(shù)，如果隨便取一個(gè)自然數(shù)，碰到奇 數(shù)和偶數(shù)的可能性是一樣的。如果我們把一次航班中這一系列數(shù)值看 作是隨機(jī)的話，那么使用奇變換和偶變換的可能性也是一樣的，所以 平均在每?jī)纱巫儞Q中我們有一次是n→3n+1，有一次是n→n/2。所以平 均起來(lái)，每次飛行高度的變化就是乘以3/2，于是……就會(huì)越飛越高。” 這樣的啟發(fā)式論證就推翻了原來(lái)的猜想！但是這個(gè)論證顯然比較幼稚， 因?yàn)樗鼪](méi)有考慮到，每一次奇變換后隨即而來(lái)的一定是一次偶變換， 因?yàn)槿绻鹡是奇數(shù)的話，3n+1一定是偶數(shù)；而每一次偶變換后隨即而 來(lái)的卻不一定是一次奇變換。J. Lagarias改進(jìn)了這個(gè)啟發(fā)式論證。 他指出，如果我們把奇變換后再作偶變換考慮在一起，那么這樣得到 的結(jié)果可以看作是真的“很隨機(jī)”。于是有1/2的可能性它是奇數(shù)， 有1/4的可能性是一個(gè)奇數(shù)的2倍，有1/8的可能性是一個(gè)奇數(shù)的4倍， 等等。于是飛行高度的變化就是以下變換的“平均效應(yīng)”； ——n乘以3/2，這有1/2的可能（奇變換后再作偶變換的結(jié)果為奇數(shù)）； ——n乘以3/4，這有1/4的可能（奇變換后再作兩次偶變換）； ——n乘以3/8，這有1/8的可能（奇變換后再作三次偶變換）； ………… 于是平均來(lái)講，每次變換后高度的變化就是 c=(3/2)1/2(3/4)1/4(3/8)1/8(3/16)1/16……=3/4 所以高度在總體上來(lái)說(shuō)應(yīng)該是越來(lái)越低，每次大約低25%，最終降到 一個(gè)循環(huán)上（不過(guò)這個(gè)論證沒(méi)有排除有除了4→2→1以外的其他循環(huán)）。 這個(gè)論證可以使我們使用論證中的模型來(lái)計(jì)算出，從一個(gè)自然數(shù)開始， 平均要多少步的這樣的飛行（就是保持高度航程中奇變換的次數(shù)）， 可以使飛行高度降到起始點(diǎn)以下。理論上的數(shù)值是3.49265……。如 果我們對(duì)3到2000000000（二十億）之間的航班的保持高度航程中奇 變換的次數(shù)取平均值，我們得到3.4926……。這兩個(gè)結(jié)果驚人的一致 性使我們相信上面的啟發(fā)性模型是正確的。如果它是正確的，那么就 意味著沒(méi)有保持高度航程無(wú)限的航班，于是3x+1猜想就是正確的，至 少可以得出沒(méi)有飛得越來(lái)越高的航班的結(jié)論。 可是一個(gè)啟發(fā)性論證，就算再有實(shí)驗(yàn)證據(jù)來(lái)表明它是對(duì)的，也只不過(guò) 是個(gè)論證，只能使我們對(duì)猜想的正確性更充滿信心。它不能代替真正 的數(shù)學(xué)證明。比如說(shuō)，數(shù)學(xué)家猜想在π的十進(jìn)位小數(shù)表示當(dāng)中，出現(xiàn) 0到9各個(gè)數(shù)字的可能性是一樣的，對(duì)π的數(shù)值計(jì)算也強(qiáng)烈支持這個(gè)猜 想，可是如果沒(méi)有數(shù)學(xué)證明，它還是得被叫做一個(gè)猜想，而不是定理。 用上面這個(gè)啟發(fā)式的概率模型，我們還可以預(yù)言，對(duì)于第n次航班，它 的最大飛行高度不會(huì)超過(guò)Kn2（對(duì)于某個(gè)常數(shù)K）。數(shù)值計(jì)算表明對(duì)于 K=8，這個(gè)公式是正確的（同樣地，這可以讓我們提出猜想，而不是證 明定理）。 六、會(huì)不會(huì)永遠(yuǎn)證不出來(lái)？ 自從哥德爾發(fā)表了他的著名的不完備性定理以來(lái)，每次碰到一個(gè)十分 困難的問(wèn)題時(shí)，數(shù)學(xué)家們就免不了疑神疑鬼——這會(huì)不會(huì)證不出來(lái)？ 哥德爾的不完備性定理說(shuō)，在包含皮亞諾的自然數(shù)公理的數(shù)學(xué)公理系 統(tǒng)中，總有不可證明的命題存在。公理系統(tǒng)的這種性質(zhì)叫不完備性。 比如說(shuō)，如果我們只取歐氏幾何的前四條公理，那么平行公理是不能 用這前四條公理證明出來(lái)的，也就是說(shuō)只有前四條公理的平面幾何是 不完備的（這個(gè)例子不是很嚴(yán)格，因?yàn)闅W幾里德的公理系統(tǒng)在現(xiàn)代觀 點(diǎn)下是不嚴(yán)密的，但是我舉這個(gè)例子只是為了說(shuō)明不完備性這個(gè)概念， 所以關(guān)系不大）。 所以說(shuō)，如果我們只用皮亞諾的自然數(shù)公理，甚至再加上現(xiàn)代的集合 論公理系統(tǒng)，也有可能不能證明3x+1問(wèn)題。甚至即使3x+1猜想其實(shí)是 錯(cuò)誤的，我們也有可能不能證明這一點(diǎn)。比如說(shuō)，我們可能發(fā)現(xiàn)一個(gè) 航班，我們對(duì)它進(jìn)行計(jì)算，發(fā)現(xiàn)它飛得越來(lái)越高，但是無(wú)論如何不能 證明它永遠(yuǎn)也不會(huì)回到1上來(lái)。 當(dāng)然無(wú)論什么數(shù)論問(wèn)題都有可能搞得數(shù)學(xué)家們這樣疑神疑鬼，雖然其 實(shí)是他們還沒(méi)有發(fā)現(xiàn)證明。不過(guò)有一些蛛絲馬跡表明我們有必要稍微 嚴(yán)肅點(diǎn)看待此問(wèn)題，因?yàn)?x+1問(wèn)題離不可證明的問(wèn)題并不太遠(yuǎn)。 J. Conway（喜歡數(shù)學(xué)游戲的朋友可能會(huì)記起這個(gè)名字來(lái)，著名的生命 游戲就是他發(fā)明的）在1972年考慮了3x+1問(wèn)題的推廣形式。在3x+1問(wèn) 題里，我們把數(shù)字除以2，然后得到了2種可能的余數(shù)（0或者1），按 照余數(shù)我們使用2個(gè)公式（除以2或者乘3加1）。Conway考慮了除以一 個(gè)固定的p，按照余數(shù)的不同（這時(shí)就有p種不同的余數(shù)）分別使用p個(gè) 公式的情況。然后他提出了一個(gè)類似“在1著陸”的猜想。他在論文中 證明了，這個(gè)猜想在集合論公理系統(tǒng)中是不可證的。 事實(shí)上，在任何一個(gè)包含了皮亞諾的自然數(shù)公理的數(shù)學(xué)公理系統(tǒng)中， Conway的方法都可以定義一個(gè)類似于3x+1問(wèn)題的不可證命題。當(dāng)然這 不是說(shuō)有一個(gè)在所有公理系統(tǒng)中都不可證的命題。“不可證”總是相 對(duì)于某公理系統(tǒng)而言的。當(dāng)然，Conway的方法并沒(méi)有說(shuō)明3x+1問(wèn)題本 身是不可證的，也沒(méi)有說(shuō)它一定是很困難的（事實(shí)上有些3x+1問(wèn)題的 變種是很容易解決的），但是這畢竟說(shuō)明，有些很象3x+1問(wèn)題的命題 是不可證的，這把事情搞得很可疑。 1993年，法國(guó)里爾(Lille)的基礎(chǔ)信息實(shí)驗(yàn)室使用了Conway的方法來(lái) 演示一套基于邏輯規(guī)則的編程形式的威力。同許多數(shù)學(xué)中的例子一樣， 先頭看上去最沒(méi)用的課題，會(huì)有很具體的用處。 七、各種變種 數(shù)學(xué)家總喜歡把問(wèn)題推廣，使它更抽象化和一般化，因?yàn)檫@樣可以把 一種在具體某個(gè)問(wèn)題上使用的方法的威力應(yīng)用到一般的情況上去，從 而得到很有可能是出乎意料的結(jié)論。 數(shù)學(xué)家們首先考慮，如果把3x+1問(wèn)題的規(guī)則運(yùn)用到負(fù)整數(shù)上去，會(huì)產(chǎn) 生什么現(xiàn)象。他們發(fā)現(xiàn)了三個(gè)不同的循環(huán)： 1)-1→-2 2)-5→-14→-7→-20→-10 3)-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122 →-61→-182→-91→-272→-136→-68→-34 他們猜想，這就是所有的循環(huán)，而所有的負(fù)整數(shù)都會(huì)掉進(jìn)其中一個(gè)里。 他們還提出了5x+1問(wèn)題，也就是在奇數(shù)的情況下用5x+1來(lái)取代3x+1。 這下又有好幾個(gè)循環(huán)： 1)6→3→16→8→4→2→1 2)13→66→33→166→83→416→208→104→52→26 3)17→86→43→216→108→54→27→136→68→34 但是5x+1問(wèn)題中的第7次航班好象老在那里飛啊飛，怎么也跑不到一個(gè) 循環(huán)里去，但是誰(shuí)都不能證明的確如此。 上面Lagarias的那個(gè)啟發(fā)式論證使得數(shù)學(xué)家猜想，如果q是大于3的奇 數(shù)的話，對(duì)于qx+1問(wèn)題，總存在至少一個(gè)航程無(wú)窮的航班，這看起來(lái) 很象是一個(gè)“反3x+1問(wèn)題”。 還有許多其他的3x+1問(wèn)題的推廣，一些結(jié)果把它們和其它數(shù)學(xué)領(lǐng)域聯(lián) 系起來(lái)，比如說(shuō)素?cái)?shù)理論，某些丟番圖方程（求解系數(shù)為整數(shù)的方程 的整數(shù)根，比如著名的費(fèi)爾馬大定理就是一個(gè)丟番圖問(wèn)題），馬爾可 夫鏈（概率論中的遞歸理論），遍歷理論（一種關(guān)于函數(shù)混合遞歸的 理論）。 就算3x+1問(wèn)題終于被解決了，看看所有這些變種，也夠數(shù)學(xué)家們自?shī)?br> |
|
|
來(lái)自： 天成98 > 《數(shù)學(xué)》
