poster489

很简单但还没有解决的Collatz猜想

本文主要介绍了著名的Collatz猜想和数学家为证明这一猜想所作出的努力和成果.
很简单但还没有解决的Collatz猜想
52 人挑战成功
趣味数学挑战

完成本期挑战需要达到:

初中数学水平

题目

Collat​​z猜想是指, 对任何正整数 做如下变换, 如果 是偶数, 则将它变成; 如果 是奇数, 则将它变成 .任何一个正整数 一直按照这个法则变换下去, 最终会变成 .

变到的过程称为 Collat​​z 轨迹.

那么: 存在无穷多个数, 其Collat​​z 轨迹经过. 此判断__________.

选项

作者 | Patrick Honner

译者 | 慕容玖

原载于 | Quanta Magazine

引入

善意提醒:不要尝试解决这个数学问题. 你会受到诱惑的.

这个问题很简单, 很容易理解, 也很吸引人. 只需选择一个数字 :如果是偶数, 则将其减半;如果是奇数, 则将其乘以并加. 得到新数字后再重复以上过程. 最终你会陷入无尽的循环.

为例:

我们回到了, 我们知道接着会发生什么:会变成,再到, 再到, 以此类推,我们陷入了循环.

"臭名昭著"的 Collatz (科拉茨) 猜想说, 从任意正整数开始, 你总是会陷入这个循环. 你可能会忽视本文开头给出的尝试解决它的提醒:它看起来太简单、太有序, 让人无法抗拒. 事实上, 很难找到一个没有研究过这个问题的数学家. 之所以说Collatz猜想"臭名昭著", 是因为尽管尝试过的每个数字最终都陷入了这个循环, 但我们仍然不能确定它一定是正确的. 虽然它广受关注, 但这仍然只是一个猜想.

当然对它的研究也是有进展和成果的. 著名世数学家陶哲轩在2019年给出了一个证明, 在这个问题上取得了几十年来最大的进步. 下面让我们看看是什么让这个简单的问题变得如此复杂.

Collatz猜想

为了理解 Collatz猜想, 我们将从以下函数开始:

这是一个分段函数, 输入自变量, 输出的结果取决于是奇数还是偶数. 该函数 执行我们前面描述的规则:例如, , 因为是偶数, 而, 因为是奇数. 由于奇数输入的规则, Collat​​z 猜想也称为猜想.

Collat​​z 猜想涉及函数的“轨迹”. 如果从一个数字开始并重复应用一个函数, 获取每个输出值并将其作为新的输入值反馈到函数中, 那么你将得到一个轨迹. 我们称为“迭代”函数. 我们已经计算过在作用下数字的轨迹.

表示轨迹的一种简便方法是用带有箭头的序列. 下面是作用下的轨迹:

我们发现最后我们陷入了循环

类似地, 作用下的轨迹可以表示为

我们再次陷入同样的​​循环. 再尝试几个例子, 你会发现轨迹似乎总是稳定在循环中. 初始值是会很有趣. 如果你有几分钟的空闲时间, 请尝试初始值, 如果计算正确, 你将在步后陷入循环.

Collat​​z猜想指出, 在函数作用下, 每个数字的轨迹最终都会到达. 虽然还没有人能证明这一猜想, 但已经验证了对小于的所有数字都是正确的. 因此, 如果你在寻找反例, 你可以从大约开始.

简化版的猜想——Nollat​​z猜想

验证Collat​​z猜想对于任何确定的数字是否正确都很容易:只需计算轨迹直到达到. 但是要证明对任意数字都正确却很难, 让我们探索一个稍微简单的函数.

函数类似, 但对于奇数, 它只是加. 由于是不同的函数, 因此数字在作用下的轨迹与在作用下的轨迹是不同的.

例如, 以下是作用下的轨迹:

请注意, 在的作用下的轨迹到达的速度比在作用下更快. 同样也是.

在这些例子中, 作用下的轨迹似乎也会趋于稳定, 只是在一个更简单的循环中:

我们可能会猜想作用下的轨迹总是能到达数字. 我将其称为“Nollat​​z”(诺拉茨)猜想, 当然我们也可以将其称为猜想. 我们可以通过测试更多的数字来探索这个问题, 但是知道某些数字(甚至是其中的 个数字)是正确的, 并不能证明它对每个数字都正确.

幸运的是, Nollat​​z猜想是可以被证明的.

具体过程如下:

我们知道正整数的一半总是小于该整数本身. 因此, 如果 是偶数且为正数, 则 换句话说, 当一个轨迹到达偶数时, 下一个数字总是更小.

接着, 如果是奇数, 则 但由于 是奇数, 是偶数, 因此我们知道接下来轨迹的走向: 会将 减半. 对于奇数轨迹是:

注意到,当时,

这就说明, 当作用下的轨迹到达大于的奇数时, 两步后我们将始终处于较小的数字.

现在我们可以概述Nollat​​z猜想的证明:对于任意轨迹, 都会呈递减趋势. 唯一的例外是轨迹到达时. 一旦到达, 就会陷入循环.

尝试证明Collat​​z猜想

类似的论证适用于Collat​​z猜想吗?让我们回到原来的函数,

一样, 将应用于偶数结果会变小, 将应用于奇数会产生偶数, 这意味着我们知道接下来会发生什么:会将新数减半. 当为奇数时,下的轨迹如下所示:

但这里就是我们证明不下去的关键点. 不像之前的例子, 这个数字总是比大, 证明Nollatz猜想的关键是奇数必须在两步后变小, 但在Collatz的情况下并非如此. 我们的论点行不通.

你现在可能会对证明Collat​​z猜想是错误的感到兴奋:毕竟, 如果轨迹上的数字继续变大, 那么它怎么会降到呢?但这一论点需要思考接下来的情况, 接下来会发生什么就说明了为什么Collatz猜想如此难以捉摸:我们无法确定是偶数还是奇数.

我们知道是偶数. 如果也能被整除, 那么也是偶数, 轨迹就会递减. 但是如果不能被整除, 那么就是奇数, 轨迹就会递增. 一般来说, 我们无法预测哪个是真的, 所以我们的论点就停滞不前了.

但是这种方法并不是完全无用的. 由于所有正整数中有一半是偶数, 因此的可能性是偶数, 这使得轨迹上的下一步是, 对于这比小, 所以有一半的时间奇数应该会在两步之后变得更小.

同样, 也有的可能性是偶数, 这意味着奇数在三步后有的可能性会减少到不到开始时的一半.

诸如此类. 最终的结果是, 在平均意义上, 当Collatz轨迹遇到奇数时, 数字会递减. 由于Collatz轨迹总是遇偶数递减, 这表明从长远来看, 所有Collatz轨迹都必须递减. 这一概率论据广为人知, 但还没有人能够将其扩展到对这一猜想的完整证明.

数学家研究成果

然而, 几位数学家已经证明, Collatz猜想“几乎总是”正确的. 这意味着他们已经证明, 相对于他们知道的最终到达的那些数字的数量, 他们不确定的数字的数量可以忽略不计. 1976年, 爱沙尼亚裔美国数学家Riho Terras证明, 在反复应用Collatz函数后, 几乎所有的数字最终都会小于它们的初始值. 正如我们在上面看到的, 显示轨迹上的数字不断变小是表明它们最终达到的一条途径.

2019年, 当今世界上最杰出的数学家之一 Terence Tao(陶哲轩)在这一结果的基础上有所改进. 此前Terras证明了对于几乎所有的数字, 的Collatz轨迹最终都会小于. 而陶哲轩证明了对于几乎所有的数字, 的Collatz轨迹最终都要小得多:小于, 小于, 小于(的自然对数), 甚至小于每个其中是任何趋向无穷大的函数. 也就是说, 对于几乎每个数字, 我们可以保证它的Collatz序列是我们想要的那样小. 在一次关于这个问题的谈话中, 陶说这个结果“几乎是在没有真正解决的情况下尽可能接近Collatz猜想的一个结果. ”

即便如此, 这个猜想仍将继续吸引数学家和爱好者. 所以选择一个数字, 任何一个数字, 然后试一试. 只要记住, 你已经被提醒过:不要陷入无休止的循环.

  1. 原文发布于 Quanta Magazine

发布于 2023-06-29 02:13
logo
慕容玖
level4
编辑于 2023-06-29 02:13
logo
慕容玖
level4
这题不难,我会😏
logo 橘子老君
2023-07-04
-

发布于 2023-07-16 13:43
logo
初心
level0
编辑于 2023-07-16 13:43
logo
初心
level0
一直有论文声称证明了该猜想并发表在专业期刊,也就是说他们的证明并不是错误的. 但据我所知尚没有并一个accepted proof.
logo 橘子老君
2023-07-18