关于ZAKER 融媒体解决方案 合作 加入

麻烦的埃及人,以及他们的单位分数

科学松鼠会 09-18 1

你还能想起小学时被分数加法支配的恐怖吗?对于整数,加法比乘法容易,到了分数却好像反过来了。两个分数相乘,分子分母各自乘一下就完事了。两个分数相加,却要先通个分,一共要做三次整数乘法,真是麻烦。

但世界上就偏偏有自找麻烦的人,连表达再简单的分数,都偏要写成几个分数的和,那就是古埃及人。他们创造了金字塔这样的世界奇观,由此见得他们的数学水平也相当不错。但在有理数的运算上,他们却另辟了一条麻烦的蹊径。

埃及人发明了 "n 分之一 " 的写法,但却没有发明 "n 分之 m" 的写法。取而代之的是,他们将所有的分数都写成好几个不同的 "n 分之一 " 的和,3/4 可以写成 1/2+1/4,而 2/5 可以写成 1/4+1/10+1/20。类似 "n 分之一 " 的分数是最简单的分数,它们又叫做单位分数,这种简单也许就是古埃及人选择用它们表达其他分数的原因,但只能说这种选择是捡了芝麻丢了西瓜……要算一下这些分数到底是多少,还得掰弄半天。

埃及分数表示法,下面的符号表示整数,上面的符号表示 " ……分之一 "| 图片编辑自 Wikipedia

也许是出于对古埃及人谜样坚持的敬佩,数学家常常将单位分数称为埃及分数,尤其是涉及将有理数写成单位分数的问题中更是如此。

单位分数够用吗?

那么,一个自然的问题就是:是不是任何正有理数都可以写成有限个不同的单位分数的和呢?

你可能会说:单位分数会越变越小,如果有理数很大的话,难道不会出现单位分数不够用的情况吗?这个问题相当于在问:1+1/2+1/3+ ……一项一项加起来的话,能达到要多大有多大的值吗?

答案是肯定的!

对于任意的正整数 n,我们来考虑从 1/ ( 2^n+1 ) 到 1/2^ ( n+1 ) 的所有单位分数,它们一共有 2^n 个,而且都大于 1/2^ ( n+1 ) ,所以它们的和至少是 1/2。然后,如果我们考虑 n 的不同的值的话,n=0 就是从 1/2 加到 1/4,n=1 就是从 1/5 加到 1/8,n=2 就是从 1/9 加到 1/16。对于每一个的 n,我们得到的和都至少是 1/2。如果我们将 n=0 到 n=k 的所有情况加起来,也就是从 1/2 加到 1/2^ ( k+1 ) ,那么得到的和就至少是 ( k+1 ) /2。因为 k 可以要多大有多大,所以这些单位分数的和也可以要多大有多大,不需要担心单位分数不够用的事情。

实际上,如果用上一点高等数学的话,我们可以证明,从 1 加到 1/n,当 n 越来越大,这个和也会越来越接近 ln ( n ) + γ,这里 ln ( n ) 是 n 的自然对数,而 γ 被称为欧拉 - 马歇罗尼常数。因为对数 ln ( n ) 会随着 n 增长而越变越大没有界限,所以自然可以要多大有多大。这个和在数学中又叫调和级数,有着广泛的应用。

怎么把有理数写成单位分数的和?

既然知道单位分数够用,我们就可以重新回到原来的问题了:用埃及人的做法,能表达所有正有理数吗?

怎么算呢?| pexels

这个问题并不简单。虽然古埃及人广泛使用埃及分数来表示各种有理数,但他们似乎没有一套完整的方法,可以将任意的有理数都转化为埃及分数的和。对于一些特殊的有理数,古埃及人通常会以某种固定的形式书写它们,比如说,对于正整数 k,有理数 2/ ( 2k+1 ) 就可以写成 1/k+1/k ( 2k+1 ) 。这样的公式还有很多,但是远远没有包含所有有理数。

这时我们可以换个角度:如果给你一个有理数 m/n,非要你把它写成单位分数的和,你会怎么做呢?

我们先来考虑 m/n 小于 1 的情况。最自然的办法,可能就是先找最大的但不超过 m/n 的单位分数,把它写下来,然后看看剩下了多少,如果是单位分数的话,那就完事了;如果还不是的话,那就重复之前的操作。这种方法又叫贪心算法,因为每一步我们写下的都是最大的可能性。

举个例子,如果我们要将 5/22 写成单位分数的和,那应该怎么写呢?

首先,我们看看最大的不超过 5/22 的单位分数是多少。假设分母是 k,那么我们就有以下的不等式:

1/k < 5/22 所以我们有 k>22/5=4.4,而符合这个条件的最小的 k,也就是使单位分数最大的 k,就是 k=5。所以,我们写出的第一项就是 1/5,也就是

5/22 = 1/5 + 3/110

3/110 还不是单位分数,所以我们要对 3/110 进行相同的操作。假设最大的不超过 3/110 的单位分数是 1/k,那么它满足

1/k < 3/110 所以我们有 k>110/3=36.666666 ……符合这个条件最小的 k 是 37,所以接下来的一项就是 1/37,也就是

5/22 = 1/5 + 1/37 + 1/4070

这回凑巧的是,剩下的恰好是个单位分数 1/4070,所以我们就成功将 5/22 写成了单位分数的和。

那么,是不是所有小于 1 的正有理数都能用这种贪心算法写成有限个单位分数的和呢?这个问题似乎很难回答,如果每次都取最大的单位分数的话,怎么知道会不会每一次都会剩下一点点,而这一点点都不凑巧不是单位分数呢?幸好,我们可以证明这个算法必定会结束,对于任何小于 1 的正有理数,都必定会在某一步剩下一个单位分数。

怎么证明呢?我们来看每一步的操作具体是怎么样的。从 m/n 开始,我们假设最大的不超过 m/n 的单位分数是 1/k,那么我们有以下的不等式:1/k < m/n,也就是 k > n/m。因为 k 是整数,为了使 1/k 最大,k 应该是大于 n/m 的最小整数,记作 n/m n/m 。将 1/k 写出来之后,剩下的就是

m/n = 1/k + ( mk-n ) /kn

但我们注意到,因为 k 是大于 n/m 的最小整数,所以我们有 n/m ≤ k < n/m + 1,也就是 n ≤ mk < n+m,所以 mk-n 在 0 和 m-1 之间。如果是 0 的话,那就意味着 m/n 本身就是单位分数 1/k 了,我们的任务也就此完成;如果是 1 的话,剩下的是一个单位分数,我们的任务同样完成;否则,mk-n 这个分子至多是 m-1,严格小于原来的分子 m。所以说,每写下一项新的单位分数,剩下部分的分子会比原来有理数的分子要小,约分之后就更加小了。因为分子不能无限减小,所以在某一步之后,剩下的数的分子必定会变成 1,这时我们就将原来的数写成好几个单位分数的和了。

从这个证明,我们还能看出来,如果 m/n 小于 1,那么最多只需要 m 步,贪心算法就会完结,而写出来的表达式也最多有 m 个单位分数。这是因为每一步剩下来的数的分子都至少会减少 1,所以贪心算法最多只能执行 m 步。另外,我们可以证明这个贪心算法写出的所有单位分数都不一样(想一想为什么?),所以,这个算法实际上告诉我们,每个小于 1 的正有理数都可以写成有限个不同的单位分数的和,而且给出了具体怎么写的一种方法。在数学中,这又被称为构造性证明

大于 1 的数也可以吗? | pexels

那么,对于大于 1 的有理数 a 又应该怎么办呢?我们之前提到,将正有理数写成不同的单位分数时,无论这个有理数有多大,单位分数都不会不够用。那么,我们只要将单位分数按照 1+1/2+1/3 ……这样写出来,直到这个和延伸到小于 a 的最大值,然后再按照贪心算法来操作,就能将有理数 a 写成单位分数的和了。我们可以证明,这样写出来的单位分数各不相同,符合之前提到的要求。当然,如果 a 很大的话,需要的单位分数的个数也会很多,但毕竟总是有限个。

所以,埃及人的做法还是有一些道理的,既然所有有理数都可以写成不同的单位分数的和,那么用单位分数来表达有理数也没什么毛病,除了写起来可能复杂一点。

为什么贪心不是件好事情?

当然,贪心算法给出的结果不一定是最好的。如果我们要将有理数写成单位分数的和,我们自然希望这个和越简单越好。这个 " 简单 " 有两个条件:是单位分数的分母越小越好,是用到的单位分数越少越好。很遗憾的是,贪心算法对这两点都做不到。

首先是第一点,在之前的例子里,我们用贪心算法将 5/22 写成了这几个单位分数的和:

但仔细观察中间步骤 5/22 = 1/5 + 3/110 的话,我们可以发现一个分母更小的写法:

5/22 = 1/5 + 1/55 + 1/110

分母一下子变成了原来的四十分之一!所以说,有时候太贪心也不是什么好事。

然后是第二点,虽然我们知道,如果将 m/n 用贪心算法写成单位分数的和,这个和最多用到 m 个单位分数,但有时候我们可以做得比贪心算法更好。举个例子,如果要将 5/121 写成单位分数的和,那么贪心算法给出的结果是

5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225

这里边包括了五个单位分数,外加大得吓人的分母。但其实如果思考一下的话,会发现 5/121 可以写成简单得多的形式:

5/121 = 1/33 + 1/121 + 1/363

如果举一个更加极端的例子,我们可以考虑 31/311,它可以写成

31/311 = 1/12 + 1/63 + 1/2799 + 1/8708

这个写法的分母有点大,但不算特别吓人。大家可以试一下用贪心算法来处理 31/311,体会一下为什么贪心是不好的。

手指肯定是不够用了 | Giphy

最简单的写法,能有多简单?

那么,将有理数写成单位分数的和,这种写法可以有多简单呢?数学家为了这个问题煞费了苦心。他们证明了,对于任意在 0 和 1 之间的有理数 m/n,都能写成分母不超过 O ( n ln n ( ln ln n ) ^4 ( ln ln ln n ) ^3 ) 的单位分数的和,又或者是写成最多需要 O ( ( ln n ) ^ ( 1/2 ) ) 项单位分数的和。这些界限大概有多大呢?我们知道,对数函数 ln 的增长非常非常慢,十的对数 ln ( 10 ) 比 2 大一点点,一万的对数 ln ( 10^4 ) 也只比 9 大一点点,一百万亿的对数 ln ( 10^15 ) 也只是 34.5 多一点,即使到了 10^100,它的对数也只是 230。所以,n 的对数在 n 面前基本上可以忽略。也就是说,任意在 0 和 1 之间的有理数,都能写成分母比原来大好几倍但远远小于原来分母平方的单位分数的和。它也有一种表达方法,最多需要对数开平方这个数量级那么多项,对于我们能想象的范围,大概就是个几十项的样子。数学家还猜想,其实项数不需要那么多,只需要 O ( ln ln n ) ,也就是对数的对数这么多项就可以了,但到目前为止还没有人能证明这一点。

有些数学家甚至将 " 省事 " 推到了极致。大数学家埃尔德什和施特劳斯猜想,任意形如 4/n 的有理数,都能写成最多 3 个单位分数的和:

4/n = 1/a + 1/b + 1/c

埃尔德什(左)与陶哲轩(右)| Wikipedia

对于所有小于 10^14 的数,这个猜想都成立,而且数学家也证明了这个猜想对几乎所有的 n 都成立。但是不是真的对所有 n 都成立呢?这还是个未解之谜。也许你可以试试找出一些公式,给出一部分 n 的解答。

题图来源:wikipedia

欢迎个人转发到朋友圈

微信:SquirrelClub

微博:科学松鼠会

科学松鼠会,是一家以推动科学传播行业发展为己任

的非营利组织,成立于 2008 年 4 月。我们希望像松鼠

一样,帮助公众剥开科学的坚果,分享科学的美妙。

喜欢记得点 " 在看 "

以上内容由"科学松鼠会"上传发布 查看原文

最新评论

没有更多评论了

觉得文章不错,微信扫描分享好友

扫码分享