主题：【文摘】【动脑筋】一道有意思的“小题”：3x+1问题（上） -- 1001n

四、理论结果

只要稍微动一下脑筋，我们就知道3x+1问题和下面几个命题都是等价的：

1)所有的航班的航程都有限；

2)所有的航班的保持高度航程都有限；

3)所有的航班中的偶变换的次数都有限；

4)所有的航班中的奇变换的次数都有限；

5)所有的航班的保持高度航程中偶变换的次数都有限；

5)所有的航班的保持高度航程中奇变换的次数都有限。

R. Terra和C. Everett证明了，“几乎所有的航班都会下降到它的起始点以下”，也就是说“几乎所有的航班的保持高度航程都有限”。这里的“几乎所有”是有确定的数学意义的，它是指：

――存在一个自然数n1，在所有小于n1的航班里，最多只可能有1/10的航班，

它们的保持高度航程无限；

――存在一个自然数n2，它比上面的n1要大，在所有小于n2的航班里，

最多只可能有1/100的航班，它们的保持高度航程无限；

――存在一个自然数n3，它比上面的n2要大，在所有小于n3的航班里，

最多只可能有1/1000的航班，它们的保持高度航程无限；

――等等等等……

这好象很接近证明“所有的航班的保持高度航程都有限”了，于是很接近证明猜想本身了。但是好好想想，这个结论只不过是说明保持高度航程无限的航班会越来越稀少罢了，它们还是有可能存在的……更糟糕的是，这个结论一点也没有排除有其它循环存在的可能。

对于在1上着陆的航班，数学家们也得到了一些结果。他们证明了，存在一个常数c，当n足够大的时候，在比n小的航班中，能够在1上着陆的航班的个数大于等于nc。在1978年R. Crandal首先给出c=0.05，虽然小了点，但毕竟是开头一步；然后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。看起来我们越来越接近c=1这个最终目标了。可是我们不知道现在用来得到c的方法是否还可以再用下去，就好象在试图征服哥德巴赫猜想的过程中，陈景润用来证明1+2的方法，似乎不能用来证明1+1了。

1995年的这个证明相当特殊。它使用了计算机程序来解一个十分巨大的方程组，所以这个证明不能用手工来验证。在论文中，我们看见的不是一个关于c=0.81的定理的证明，而是一个关于如何写出这个巨大方程组的说明，和由程序计算出来的结果，以及如何使用这些结果来解释c=0.81。其他的数学家如果想验证这个结果，必须首先看懂关于方程组的证明和那些解释，再按照里面的说明来写一个程序（很复杂的！），运行它，再看看结果是否和文章中的相同。目前四色定理的证明也是如此，所以数学家对此很不满意。

还有一些结果是关于如果有其他不同于4 → 2 → 1的循环存在时，对这样的循环的性质的研究。R. Crandal和N. Yoneda在1978年证明，如果这样一个另外的循环存在的话，那么它的长度（就是在这个循环中数字的个数，比如说循环4 → 2 → 1的长度就是3）一定要大于275000。1993年这个体积增大到17087915，最近的结果是102225496。这些结果是通过分析包括我们前面提到的各种纪录得到的，所以这些结果我们还是不能完全通过手工来验证。我们看到，如果真有另外的循环存在的话，那一定是非常非常巨大的！

五、启发式论证

数学中有一种叫“启发式”的论证方法，建立在估计和概率的手段上。比如说底下的论证方法就是这个类型的：

“每个数字要么是奇数要么是偶数，如果随便取一个自然数，碰到奇数和偶数的可能性是一样的。如果我们把一次航班中这一系列数值看作是随机的话，那么使用奇变换和偶变换的可能性也是一样的，所以平均在每两次变换中我们有一次是n → 3n+1，有一次是n → n/2。所以平均起来，每次飞行高度的变化就是乘以3/2，于是……就会越飞越高。”

这样的启发式论证就推翻了原来的猜想！但是这个论证显然比较幼稚，因为它没有考虑到，每一次奇变换后随即而来的一定是一次偶变换，因为如果n是奇数的话，3n+1一定是偶数；而每一次偶变换后随即而来的却不一定是一次奇变换。J. Lagarias改进了这个启发式论证。

他指出，如果我们把奇变换后再作偶变换考虑在一起，那么这样得到的结果可以看作是真的“很随机”。于是有1/2的可能性它是奇数，有1/4的可能性是一个奇数的2倍，有1/8的可能性是一个奇数的4倍，等等。于是飞行高度的变化就是以下变换的“平均效应”；

――n乘以3/2，这有1/2的可能（奇变换后再作偶变换的结果为奇数）；

――n乘以3/4，这有1/4的可能（奇变换后再作两次偶变换）；

――n乘以3/8，这有1/8的可能（奇变换后再作三次偶变换）；

…………

于是平均来讲，每次变换后高度的变化就是c=(3/2)1/2(3/4)1/4(3/8)1/8(3/16)1/16……=3/4 [注：等式中，括号外的数字是前一个括号内的幂次；西西不支持这些符号，粘上来就变形了。。]

所以高度在总体上来说应该是越来越低，每次大约低25%，最终降到一个循环上（不过这个论证没有排除有除了4 → 2 → 1以外的其他循环）。这个论证可以使我们使用论证中的模型来计算出，从一个自然数开始，平均要多少步的这样的飞行（就是保持高度航程中奇变换的次数），可以使飞行高度降到起始点以下。理论上的数值是3.49265……。如果我们对3到2000000000（二十亿）之间的航班的保持高度航程中奇变换的次数取平均值，我们得到3.4926……。这两个结果惊人的一致性使我们相信上面的启发性模型是正确的。如果它是正确的，那么就意味着没有保持高度航程无限的航班，于是3x+1猜想就是正确的，至少可以得出没有飞得越来越高的航班的结论。

可是一个启发性论证，就算再有实验证据来表明它是对的，也只不过是个论证，只能使我们对猜想的正确性更充满信心。它不能代替真正的数学证明。比如说，数学家猜想在π的十进位小数表示当中，出现0到9各个数字的可能性是一样的，对π的数值计算也强烈支持这个猜想，可是如果没有数学证明，它还是得被叫做一个猜想，而不是定理。

用上面这个启发式的概率模型，我们还可以预言，对于第n次航班，它的最大飞行高度不会超过Kn2（对于某个常数K）。数值计算表明对于K=8，这个公式是正确的（同样地，这可以让我们提出猜想，而不是证明定理）。

六、会不会永远证不出来？

自从哥德尔发表了他的著名的不完备性定理以来，每次碰到一个十分困难的问题时，数学家们就免不了疑神疑鬼――这会不会证不出来？

哥德尔的不完备性定理说，在包含皮亚诺的自然数公理的数学公理系统中，总有不可证明的命题存在。公理系统的这种性质叫不完备性。比如说，如果我们只取欧氏几何的前四条公理，那么平行公理是不能用这前四条公理证明出来的，也就是说只有前四条公理的平面几何是

不完备的（这个例子不是很严格，因为欧几里德的公理系统在现代观点下是不严密的，但是我举这个例子只是为了说明不完备性这个概念，所以关系不大）。

所以说，如果我们只用皮亚诺的自然数公理，甚至再加上现代的集合论公理系统，也有可能不能证明3x+1问题。甚至即使3x+1猜想其实是错误的，我们也有可能不能证明这一点。比如说，我们可能发现一个航班，我们对它进行计算，发现它飞得越来越高，但是无论如何不能证明它永远也不会回到1上来。

当然无论什么数论问题都有可能搞得数学家们这样疑神疑鬼，虽然其实是他们还没有发现证明。不过有一些蛛丝马迹表明我们有必要稍微严肃点看待此问题，因为3x+1问题离不可证明的问题并不太远。

J. Conway（喜欢数学游戏的朋友可能会记起这个名字来，著名的生命游戏就是他发明的）在1972年考虑了3x+1问题的推广形式。在3x+1问题里，我们把数字除以2，然后得到了2种可能的余数（0或者1），按照余数我们使用2个公式（除以2或者乘3加1）。Conway考虑了除以一个固定的p，按照余数的不同（这时就有p种不同的余数）分别使用p个公式的情况。然后他提出了一个类似“在1着陆”的猜想。他在论文中证明了，这个猜想在集合论公理系统中是不可证的。

事实上，在任何一个包含了皮亚诺的自然数公理的数学公理系统中，Conway的方法都可以定义一个类似于3x+1问题的不可证命题。当然这不是说有一个在所有公理系统中都不可证的命题。“不可证”总是相对于某公理系统而言的。当然，Conway的方法并没有说明3x+1问题本身是不可证的，也没有说它一定是很困难的（事实上有些3x+1问题的变种是很容易解决的），但是这毕竟说明，有些很象3x+1问题的命题是不可证的，这把事情搞得很可疑。

1993年，法国里尔(Lille)的基础信息实验室使用了Conway的方法来演示一套基于逻辑规则的编程形式的威力。同许多数学中的例子一样，先头看上去最没用的课题，会有很具体的用处。

七、各种变种

数学家总喜欢把问题推广，使它更抽象化和一般化，因为这样可以把一种在具体某个问题上使用的方法的威力应用到一般的情况上去，从而得到很有可能是出乎意料的结论。

数学家们首先考虑，如果把3x+1问题的规则运用到负整数上去，会产生什么现象。他们发现了三个不同的循环：

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

他们猜想，这就是所有的循环，而所有的负整数都会掉进其中一个里。

他们还提出了5x+1问题，也就是在奇数的情况下用5x+1来取代3x+1。

这下又有好几个循环：

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问题中的第7次航班好象老在那里飞啊飞，怎么也跑不到一个循环里去，但是谁都不能证明的确如此。

上面Lagarias的那个启发式论证使得数学家猜想，如果q是大于3的奇数的话，对于qx+1问题，总存在至少一个航程无穷的航班，这看起来很象是一个“反3x+1问题”。

还有许多其他的3x+1问题的推广，一些结果把它们和其它数学领域联系起来，比如说素数理论，某些丢番图方程（求解系数为整数的方程的整数根，比如著名的费尔马大定理就是一个丢番图问题），马尔可夫链（概率论中的递归理论），遍历理论（一种关于函数混合递归的

理论）。

就算3x+1问题终于被解决了，看看所有这些变种，也够数学家们自娱自乐上几百年的了。