|
|
|
[color=#00008B]3x+1问题
作者：异调 文章来源：http://www.oursci.org
一、一个简单的问题
当我们阅读数学史时，会有这样一种印象，数学家们首先研究简单的问题，然后研究越来越复杂的问题。经常性地，高深的数学问题是非常复杂的。只是为了理解问题，我们就得学习非常多的数学知识；而为了解决它，那就得用更复杂的数学知识了。就算我们在学校里的数学考试也是如此，最后一题经常被叫做“最后一大题”，“一大题”是说它表达复杂，里面还有一二三四的小题，要理解题意就得几分钟的时间。弄不好还理解错了，搞得整道题都白白做，被扣去许多分。
可是数学里不只有这些吓人的“大题”——我是说，数学里还有吓人的“小题”。这样的“小题”理解起来非常容易，却让无数数学家大跌眼镜，怎么冥思苦想也不得其解。3x+1问题大概就是其中最著名而又最简单的一个。它简单到大概任何一个会除2和会乘3的人（比如说，没文化但是经常买菜的老奶奶）都能理解它的意思，但是困难得让数学家至今也没有找到好好对付它的方法。
任取一个自然数，如果它是偶数，我们就把它除以2，如果它是奇数，我们就把它乘3再加上1。在这样一个变换下，我们就得到了一个新的自然数。如果反复使用这个变换，我们就会得到一串自然数。
比如说我们先取5，首先我们得到3*5+1=16，然后是16/2=8，接下去是4，2和1，由1我们又得到4，于是我们就陷在4→2→1这个循环中了。
再举个例子，最开始的数取7，我们得到下面的序列：
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
这次复杂了一点，但是我们最终还是陷在4→2→1这个循环中。
随便取一个其他的自然数，对它进行这一系列的变换，或迟或早，你总会掉到4→2→1这个循环中，或者说，你总会得到1。已经有人对所有小于100*250=112589990684262400的自然数进行验算，无一例外。
那么，是否对于所有的自然数都是如此呢？
这看起来是个多么简单的问题啊！
二、克格勃的阴谋？
这个问题大约是在二十世纪五十年代被提出来的。在西方它常被称为西拉古斯(Syracuse)猜想，因为据说这个问题首先是在美国的西拉古斯大学被研究的；而在东方，这个问题由将它带到日本的日本数学家角谷静夫的名字命名，被称作角谷猜想。除此之外它还有着一大堆其他各种各样的名字，大概都和研究和传播它的数学家或者地点有关的：克拉兹(Collatz)问题，哈斯(Hasse)算法问题，乌拉姆(Ulam)问题等等。今天在数学文献里，大家就简单地把它称作“3x+1问题”。
角谷静夫在谈到这个猜想的历史时讲：“一个月里，耶鲁大学的所有人都着力于解决这个问题，毫无结果。同样的事情好象也在芝加哥大学发生了。有人猜想，这个问题是苏联克格勃的阴谋，目的是要阻碍美国数学的发展。”不过我对克格勃有如此远大的数学眼光表示怀疑。这种形式如此简单，解决起来却又如此困难的问题，实在是可遇而不可求。
数学家们已经发表了不少篇严肃的关于3x+1问题的数论论文，对这个问题进行了各方面的探讨，在后面我会对这些进展作一些介绍。可是这个问题的本身始终没有被解决，我们还是不知道，“到底是不是总会得到1？”
在1996年B. Thwaites悬赏1100英镑来解决这个问题。我写一下这个悬赏的文献：Thwaites, B. “Two Conjectures, or How to win ￡1100.”Math.Gaz. 80, 35-36, 1996，好在大家万一证出来时知道跑哪里去领奖。看在钱大爷的份上，3x+1问题于是又多了个名字，叫Thwaites猜想。要是真的有这么一个自然数，对它反复作上面所说的变换，而我们永远也得不到1，那只可能有两种情况。
1)它掉到另一个有别于4→2→1的循环中去了。我们在后面可以看到，要是真存在这种情况，这样一个循环中的数字，和这个循环的长度，都会是非常巨大的；
2)不存在循环。也就是说，每次变换的结果都和以前所得到的所有结果不同。这样我们得到的结果就会越来越大（当然其中也有可能有暂时减小的现象，但是总趋势是所得的结果趋向无穷大）。
因为这是个形式上很简单的问题，要理解这个问题所需要的知识不超过小学三年级的水平，所以每一个数学爱好者都可以来碰碰运气，试试是不是能证明它。不过在这里我要提醒大家的是，已经有无数数学家和数学爱好者尝试过，其中不乏天才和世界上第一流的数学家，他们都没有成功。如果你在几小时内就找到了一个“证明”，那么把它一步一步地严格地写下来，看看是不是严密正确（我可以肯定它是错的，我这样的肯定要冒的危险绝不超过连续中十次彩票头奖的概率，既然我不买彩票，我就没道理不这么肯定:-)）。事实上，在互联网上已经有一些错误的“证明”。据说还有个数学爱好者跑到公证处去公证他的“证明”，生怕别人把他的好主意偷跑了。
二十多年前，有人向伟大的数论学家保尔·厄尔多斯(Paul Erdos)介绍了这个问题，并且问他怎么看待现代数学对这问题无能为力的现象，厄尔多斯回答说：“数学还没有准备好来回答这样的问题。”
三、一些概念，一些纪录
虽然证不出猜想，但是数学家们还是得到了许多很可能很有用的结论。让我们先来定义几个概念，然后再来介绍这些结论。
从一个自然数开始，用上面这个变换，我们可以计算出一串自然数的序列。为了形象起见，我们把这串数列叫做以最初用来开始计算的那个自然数命名的“航班”。比如说，第6次航班就是
6→3→10→5→16→8→4→2→1
我们把一个航班里的最大数字，叫做这个航班的“最大飞行高度”。比如说，第6次航班的最大飞行高度就是16。我们把航班在数字1“着陆”之前的数字个数（最初的数字包含在内，但1不包含在内），叫做这个航班的“航程”（特别定义第1次航班的航程为0）。第6次航班的航程就是8。如果真有自然数在此变换下永远达不到1，那么这个航班的航程就是无穷了。
接下去的概念稍微有点复杂。我们把从起点开始（但不包括起点）连续的不小于起点的数字的个数，叫作“保持高度航程”。举一个例子来说明这个概念比较方便：第11次航班是
11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
我们看到从起点开始，34，17，52，26，13，40，20都不小于起点11，共有7个数字，所以第11次航班的保持高度航程为7。后面的航程中虽然还有数字16大于起始点11，但是它不被算在保持高度航程里了。一个最简单的推论就是，偶数次航班的保持高度航程总是0，因为开始就除以2，跌到较低的高度去了。
为什么我们对一个航班的保持高度航程感兴趣？因为如果所有航班的保持高度航程都是有限的话，3x+1问题就成立了。让我们假设已知所有航班的保持高度航程都是有限的，用数学归纳法来证明3x+1问题，也就是所有的航班都在1上“着陆”。我们已经知道第1到第5航班都是在1上着陆的，现在假设对于所有小于n的数字k，第k次航班都在1上着陆，我们来看看第n次航班的情况：由于按假设它的保持高度航程是有限的，所以它迟早会降落在一个比n小的数字上——于是按归纳假设它就会降落在1上！
我们可以对开始的30班航班列出一个相关数据表来：
航班 航程 保持高度航程 最大飞行高度
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
下面要说说几个记录。在上面我们已经说过，目前3x+1问题已经被检验到100*250=112589990684262400，都没有发现反例。这是葡萄牙阿弗罗(Aveiro)大学的Tomas Oliveira e Silva的工作，用了很巧妙的编程方法。他的主页在http://www.ieeta.pt/~tos/3x+1.html
如果一个航班的航程大于所有它前面的航班的航程，我们就把它叫作“航程纪录航班”，比方说第7航班，它的航程是16，比第1到6次航班的航程都长，所以第7航班是个航程纪录航班。今天我们已经知道的航程纪录航班有118个，航程最长的是2234047405400065次航班，它的航程是1871，这是Eric Roosendaal发现的，他有个个人网站http://personal.computrain.nl/eric/wondrous/，里面有各种各样关于3x+1问题的信息，下面的记录也都来自这个网站。
同样的，如果一个航班的保持高度航程大于所有它前面的航班的保持高度航程，我们就把它叫作“保持高度航程纪录航班”，比方说从上面的表中我们看到第7航班也是个保持高度航程纪录航班。今天已知的保持高度航程纪录航班有30个，航程最长是1008932249296231次航班，它的保持高度航程是1445。
最大飞行高度记录航班就是那些最大飞行高度记录大于所有它前面的航班的那些航班，现在已知的有76个，最大的是10709980568908647次航班，到达了350589187937078188831873920282244的高度。
对于一个固定航班N，考虑它在1着陆之前所作的变换，如果把其中除以2的变换称为“偶变换”并记为E(N)，而把乘以3再加1的变换称为“奇变换”并记为O(N)。数学家已经证明，O(N)/E(N) |
|
IP卡
狗仔卡
发表于 2012-12-22 10:46
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主