如果把 3 · n + 1 问题改为 3x · n + 1 问题

Collatz 猜想也叫做 3 · n + 1 问题。这可能是数学中最为世人所知的未解之谜。它是如此初等,连小学生都能听懂它的内容;但解决它却如此之难,以至于 Paul Erdős 曾说:“或许现在的数学还没准备好去解决这样的问题。”这究竟是一个什么样的问题呢?让我们来看一下 Collatz 猜想的叙述:

任意取一个正整数 n 。如果 n 是奇数,则把 n 变为 3 · n + 1 ;如果 n 是偶数,则把 n 变为 n/2 。不断重复操作,则最终一定会得到 1 。

举个例子,如果 n = 26 ,那么经过下面 10 步之后,它最终变为了 1 :

26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Collatz 猜想说的就是,这个规律对于所有正整数 n 均是如此。这个问题看起来是如此简单,以至于无数的数学家都掉进了这个坑里。光从这个问题的众多别名,便能看出这个问题害人不浅: Collatz 猜想又叫做 Ulam 猜想、 Kakutani 问题、 Thwaites 猜想、 Hasse 算法、 Syracuse 问题……研究这个问题的人很多,解决这个问题的人却一个没有。后来,人们干脆把它叫做 3 · n + 1 问题,让哪个数学家也不沾光。

这个问题有多难呢?我们可以从下面的这个例子中略见一斑。虽然从 26 出发只消 10 步就能变成 1 ,但若换一个数,比如 27 ,情况就大不一样了:

27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可见,当 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) 的区间里。

这个问题出自 http://www.brand.site.co.il/riddles/201508q.html

32 条评论

  • godultimate24

    上述的“无法假设”应该改为“不妨假设”吧?

  • 绥中神宠

    ,很久好久以前就听过这个问题。。对了,问一下顾森老师,怎么保存邮箱啊,每次都打好烦

  • abc

    3n+1问题有这么难?随便想了想感觉就解决了
    从2进制的角度来考虑问题:
    3n+1相当于2n+(n+1)
    2n/2变原数
    (n+1)/2因为n是奇数相当于无条件消除最低位
    这样每次做(3n+1)/2操作相当于n1=n0+(n0\2)(\表示整除)
    可以证明新的n1减少1位的概率大于增加1位:
    n1=n0+(n0\2)
    因为n0的末位是1
    考虑(n0\2)的倒数第2位和倒数第1位(就是n0的倒数第3位和倒数第2位)
    01,11的情况n1能直接/2减少1位
    10的情况n1做一次3n+1后能连续/2两次,相当于抵消3n+1还是减少1位
    00的情况n1才会增加一位
    上面有3/4的概率减少1位,1/4的概率增加一位
    最终长度越来越短就变1了。

  • xiaoying

    轨道划分的分割点可以是任意相位,即任意一段弧都有解
    可以取N=⌈1/log3(1+1/n)⌉,N与n正相关,n越大,必要性来说圆形轨道将划分的越细,但无论n多大,1/N>0,则必定有解
    圆形轨道周长1,轮子周长log3(2),有1>log3(2)>log3(1+1/n),要满足log3(n)+b<alog3(2)<log3(n+1)+b。轮子自滚了a圈,经过单位圆b+⌈log3(n)⌉+(0或1)圈。当然若log3(n)与log3(n+1)整数部分相同,就是b+⌈log3(n)⌉圈了。然而。。并不会出现5.9、6.1这样的情形,因为t=log3(3^t)包含了所有的正整数。。而5.9\6.0取5,6.0\6.1取6,所以其实都是b+⌈log3(n)⌉
    好吧其实以上都是废话。。

  • 吉编辑

    你好,我们是北京源智天下公司,和清华出版社合作的,邀请你写书 ,你有时间吗?微信/qq:702697037

  • OriBeta

    按个引理和这个帖子里的讨论有联系吗?https://www.chaoli.club/index.php/705

  • 古庙游吟诗人

    另外感觉这个跟进制没有关系。解法不应在这上面耗费太多精力。

  • ghi

    不过纠正一下,10对应的才是增加一位的情况

  • 古庙游吟诗人

    陶哲轩太厉害了 希望有一天能读得懂、跟进他的博客……

  • 笨蛋

    陶哲轩错误百出:http://wenku.baidu.com/view/0a2e8f024afe04a1b171de54
    华罗庚与陈景润http://wenku.baidu.com/view/6cfc409a58fb770bf68a5574

  • 卞一寻

    有没有微信公众号啊

  • 迪峰

    最近在看《哥德尔 埃舍尔 巴赫》一书,书中也提到此问题,书中将此数称为“妙极数”,只不过没有给出证明,说是到现在还找不到一个检验妙极性质数的终止测试。

  • jzp

    2a1 × 3b1 + 2a2 × 3b2 + 2a3 × 3b3 + … + 2an × 3bn 这个问题和三进制是有联系的。

  • yycyycyy

    如果所有的3^n+1成立,则所有的正整数都成立。

  • zarda

    3*prime+1=2N

  • 瑟瑟发抖

    请问如果那个引理中a和b可以小于0是否仍然成立?

发表评论