首页 >> 数学 >> 文章

本文删改版刊登于微信公众号“果壳少年”,未经许可不得进行商业转载

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

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

图片来自pixabay

图片来自pixabay

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

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

埃及分数表示法,下面的符号表示整数,上面的符号表示“……分之一”。图片编辑自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增长而越变越大没有界限,所以自然可以要多大有多大。这个和在数学中又叫调和级数,有着广泛的应用。

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

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

这个问题并不简单。虽然古埃及人广泛使用埃及分数来表示各种有理数,但他们似乎没有一套完整的方法,可以将任意的有理数都转化为埃及分数的和。对于一些特殊的有理数,古埃及人通常会以某种固定的形式书写它们,比如说,对于正整数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的最小整数,记作\( \lceil n/m \rceil \)。将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的有理数a又应该怎么办呢?我们之前提到,将正有理数写成不同的单位分数时,无论这个有理数有多大,单位分数都不会不够用。那么,我们只要将单位分数按照1+1/2+1/3……这样写出来,直到这个和延伸到小于a的最大值,然后再按照贪心算法来操作,就能将有理数a写成单位分数的和了。我们可以证明,这样写出来的单位分数各不相同,符合之前提到的要求。当然,如果a很大的话,需要的单位分数的个数也会很多,但毕竟总是有限个。

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

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

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

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

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

但仔细观察中间步骤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,体会一下为什么贪心是不好的。

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

那么,将有理数写成单位分数的和,这种写法可以有多简单呢?数学家为了这个问题煞费了苦心。他们证明了,对于任意在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

埃尔德什(左)与陶哲轩(右),图片来自Wikipedia

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

0
为您推荐

5 Responses to “麻烦的埃及人,以及他们的单位分数”

  1. 匿名说道:

    不错,理解了贪心算法

  2. 匿名说道:

    这位老师让我重新回到对数学的恐惧之中。。。尤其恐惧代数微积分这一类 如果有人开发一些软件来减轻这种恐惧就好了 我学拓扑的时候一路哈皮 一到代数相关 各种卡壳 蛋疼死

  3. 匿名说道:

    用Excel手动贪心算法来算31/311,叠加到第5次,后面余数分子直接变成0,算不出来了

  4. 匿名说道:

    又看了一遍 不但对n恐惧 还对猜想恐惧 深渊对我回眸了吗

  5. geek42说道:

    感觉埃及人这种玩法有点像是他们有某种并发算法 但是难道底数不应该选择质数嘛

Leave a Reply