这是一道网上流传的题目,解这道题给了我2个感悟:
第一,看上去简单的事情,往往十分复杂,其复杂程度甚至远远超过了你的想象;
第二,你绝望的时候,不代表没有希望。
希望,往往就在远方,
虽然可能很远,很远。
一、声明
首先声明,这个题目的解是由 Quora 上的作者 Alon Amit 给出的。 这里按照这个思路进行了转译,同时增加了很多内容,其目的是让初级数学水平的人都尽量能够理解。
第一次看到这个题目的时候,我以为是一个小学生题目,甚至以为是幼儿园的智力题。然而当试图算出答案的时候,发现问题不简单。试验了一个又一个数字,得出的结论是这道题大概率没有正整数解。当然这是猜的。最终在网上找到了答案,却惊奇地发现,其中涉及到的数学知识令人发指,这哪里是小学生的题目,用 Alon Amit 的原话说:
大概99.99995%的人解不开这道题,甚至一大帮顶尖学府里的数学家,如果他正好不是数论专家的话,他们也不会做。
Roughly 99.999995% of the people don’t stand a chance at solving it, and that includes a good number of mathematicians at leading universities who just don’t happen to be number theorists.
如果你对数学不感兴趣,你可以直接跳到文章第八段的最后看一眼答案了。
不过如果你感一点兴趣,虽然它很难,但我相信你能看得懂。
二、几个初步结论
书归正传,开始解题。
首先,为了方便,我们把原题描述为下面的形式:
(1)
要求的是a、b、c这3个变量的正整数解(因为苹果凤梨香蕉的个数总不至于为负数嘛,这也符合一般表述的常识)。
注意,从这个式子中我们可以得出几个初步结论:
初步结论一:只要有一个解,就有无穷多个解。
为什么呢?我们在第一个分式的分子和分母同时乘上一个正整数t,可以发现:
那么也就是说,只要(a, b, c)是原来方程的解,那么(7a, 7b, 7c)也必然是这个方程的解(这是t=7的情况,t还可以等于其他正整数)。这样也就等于有了无穷多个解。
初步结论二:如果有解,(a,b,c) 三个未知数的解是对称的。
也就是说调换a、b、c的位置,不影响结果。
这个是显而易见的,如果我们得到一个解(a, b, c) ,那么(b, a ,c)也一定是它的解,(c, b ,a)也一定是它的解。
初步结论三:3个变量中不能有0。
这个我们来证明一下。假设某一个变量是0,不妨是a吧(因为是对称的嘛,谁是0都一样)。那么原式(1)就变成:
这里显然b和c不能再有0了,否则等式没有意义了。
这个方程等同于
这是初中的一元二次方程题目,解出来
很明显,这是无理数,而两个整数b和c相除等于一个有理数,并不是无理数。
所以假设不成立,也就是说a、b、c中任何一个数字都不能为0。
初步结论四:求解(a,b,c)的正整数解,实际是求这三个未知数的正有理数解。
这是因为:有理数都可以表现为分数的形式,如果我们得到a、b、c的正有理数的解,那么我们同时把这3个数字乘以它们的公分母,那么我们就得到了3个整数。根据前面的初步结论一,我们很容易知道,这3个整数就是原方程(1)的解。
好了,研究完一些初步结论,我们来开始解剖原题。如果我们在原方程(1)的两边同时乘以他们的公分母(b+c)(a+b)(a+c),然后再移项、合并同类项,虽然有点繁琐,但我们可以得到下面这个方程:
(2)
这是与原方程(1)等价的,我们求它的解就可以了。
根据前面的结论四,我们只需要求出他们的有理数解。
麻烦来了,这个方程看起来很复杂,而且几乎无从下手啊。
解高次方程有多难呢?
如果我们碰到一个一次方程,比如,这个非常容易,这个难度打个比方大约相当于一碗水;
如果我们碰到一个二次方程,比如前面碰到的这个,这个也有初等数学的方法去解决,也比较简单,这个难度大约相当于一个小池塘;
但如果我们碰到的是一个3次方程,比如这个样子的,不好意思,你一下子就来到了马里亚纳海沟,你面对的是一个非常深奥的题目,而且这个领域有无穷的问题等着去解决;
如果再高次方,那真是。。。太难了。有兴趣的话去看看费马大定理吧(对,就是那个困扰了人类350多年的超级大难题)。
本题,就是一个三次方的方程。
而且,并不是简单地求解,而是要求出有理数解。
有理数解,是什么意思?怎么个求法?
三、不定方程的基本知识——什么叫特解与通解
求一个方程的有理数解或者整数解,往往是数论方面的题目。而要解出本题,还要用到椭圆曲线。
我们先了解一些简单的数论知识。
打个比方说,我想求出下面这个方程的解:
(3)
你肯定会说,这有无穷多组解啊, x 也好, y 也好,可能是任何数字。
没错。但如果是求整数解呢?似乎也是有无穷多组解。但是,你有没有什么办法把所有的解都描述出来呢?
有的。首先我们可以很容易看出(x=2,y=4)是它的一组解,这个呢,叫做“特解”。当然,特解有很多个。
然后我们利用这个“特解”,我们设计一个式子:
,其中t是任意整数。
我们可以很容易地验证,首先上面这个解是满足方程(3)的,另外我们还可以发现,上面的这个式子也包括了方程(3)的所有整数解,所以这个解就叫做“通解”。
这就是一次不定方程,又叫丢番图方程(Diophantine Equation)。
我们不需要太深入了解数论的知识,只要知道“特解”、“通解”的概念就可以了,并且求取这样方程的“通解”,常常就是从一个“特解”入手的。
刚才解的是一次的丢番图方程,然而我们现在面对的方程(2),是3次的。
四、神奇的“降维”操作——3元变2元,曲面变曲线
不得不说,后面的变化,确实有点复杂,也很有些难度。但总的来说,如果暂时不考虑其“所以然”的话,“知其然”还是大致可以做到的。
在现代数学,有一个分支,叫”代数几何学“(algebraic geometry),注意这个不是中学学习的代数和几何,而是研究的代数和几何之间相互关联对应问题的学科。
其中,就有一个重要的理论,是发现了代数问题在几何上的对应性,从而可以用”几何“的方法来解决”代数“的问题。说得直白一点,就是我们遇到一个无法下手的代数方程的时候,我们或许可以用”几何“的方式来解决。
今天,我们正好碰到的就是这个问题。我们再看一眼方程(2):
(2)
这是一个有着3个变量的方程。它是3维的,对应的是一个曲面;
现在有一个好消息,就是我们可以通过某一种变换,将其变为一个只有x和y两个变量的方程,一种叫做维尔斯特拉斯典范型(Weierstrass form)的方程,像下面这种形式的:
或是(注意,此处的a、b、c非方程(2)的变量,这里是方程系数)
并且我们可以描述出(a, b, c) 和(x, y)之间的关系。
,
那么方程(2)就转化成了:
(4)
而方程(2)中的未知数a, b, c则分别为:
(5)
这样的好处呢,是把有a、b、c3个变量的方程,转化成了x、y两个变量的方程。(用专业术语说,其实是把一个三维平面“映射”到了一条二维曲线上)
还有一个重大的好处,就是方程(4)是一个椭圆曲线的方程。
现在的问题转化为:我们只需要解方程(4)的有理数解,然后就可以根据上述公式对应地计算出a、b、c。
你看到这里可能觉得像是在变戏法,但其实真不是。推导的过程非常复杂,这里就暂时不写出来了。好在我们验证它对不对还是比较方便的。
运用一些技巧,我们可以发现(x= -100, y=260)是方程(4)的一个“特解”。虽然这个过程也有点复杂,但好歹我们验证它还是容易的。我们把这两个数代入方程(4),首先发现它是成立的;再代入到上述等式(5),可以求出
,,
同时乘以14,得到 a=4, b=-1, c=11,代入到,发现果然等于4。
不过这个里面有个负数,肯定是不行的。
那么我们有没有办法通过这样一个“特解”,来找到更多的“特解”呢?如果我们找到更多的特解,会不会最终就能够让a、b、c变为正数呢?
我们试一下吧。
五、双有理等价——通过2个有理数解寻找3次方程的第3个有理数解
我们先来看一下3次方程,如果一个有理数系数的3次方程,我们知道其中的2个有理数解,我们有没有办法找出它的第3个有理数解?
那当然是可以的。假设我有一个3次方程,其中p、q、r都是有理数,我有它的2个有理数解。
那么它一定可以表示为,其中x1、x2、x3,分别是3个方程的根。我在知道x1和x2的情况下,是可以通过用多项式除法来求出x3。怎么个操作法呢?我们来看个例子:
假设我们有这样一个方程,我们知道x1 = 1,以及x2 = 2是它的两个解,那么等号左边实际是包含了(x-1)和(x-2)这两个因式,所以我们用类似除法的方法来计算一下(仅仅用每一项的系数即可):
等号左边的多项式对应的系数是(1 -6 11 -6),(x-1)对应的系数是(1, -1)
除下来我们就可以得到,继续拿右边括号的多项式除以(x-2)
于是我们得到,这样第三个根就是 x = 3 。
通过上面的操作我们可以看出,所有的操作都是加减乘除的操作,在系数和已知的两个根都是有理数的情况下,在没有无理数参与、也没有开根号、取对数等操作的前提下,这第三个根必然也是有理数。
回到我们的原题。
没错,你一定发现了,我们现在并没有2个根,我们只有一个根(x = -100,y = 260),那怎么办呢?我们可以把它当作是2个根(也就是“重根”,在几何上可以理解为两个点无限接近),然后通过它来找出第三个根。再通过其中两个根,再找出不同的其他根,如此往复。
要理解这个事情,我们得回到图形上来,也就是几何方法。
六、目标函数——椭圆曲线
我们现在要解的是方程(4),我们要找出它的有理数点,并且我们要让a、b、c成为整数,现在我们已知(x = -100, y = 260)是一个特解。
我们先将它画出来,看看是什么样子。由于左边是y2,这个图显然是关于x轴对称的。画出来的图形近看这样的,就像一条小鱼:
不过注意了,这条“鱼”的身体跟尾巴有一点点分离,因为在原点的左边有一小块区域y2为负值,在实数范围内没有意义,所以也就没有y值。
当然这是近看,如果我们拉远一点,发现它更像一个”绳结“:
再远看,其实这个曲线整体是两根“辫子”:
当然这两根“辫子”是伸向了无穷远。
至于这个近看像小鱼、中看像绳结、远看像辫子的曲线为什么叫“椭圆曲线”,这是因为它的一些数学性质跟椭圆、抛物线等曲线有相同的地方,所以一起被归到了椭圆曲线的类别。这是题外话,我们不需要太关注。
七、双有理等价的几何表示
那么我们前面所提到的双有理等价(就是通过2个有理点,寻找第三个有理点),在图形上面是什么意思呢?
我们来看下图:假设P1、P2是曲线上的两个有理点(即横竖坐标都是有理数),我们通过这两点做连线,那么有两种情况,一种是跟这个椭圆曲线相交到了第三点(如图P3),另一种是比如正好跟y轴平行,因而无论如何也不会跟曲线有第三个交点。后一种情况属于特殊情况,我们只需要适当规避。我们考虑前一种情况,这时注意了:
因为P1(x1, y1) 、P2(x2, y2)是有理点,所以其斜率必然也是有理数。也就是说P1、P2所定义的直线,其系数都是有理数。
我们将代入到,整理后我们可以发现,这就是一个关于x的3次方程。而它的三个根就对应于P1、P2、P3的3个横坐标。
既然x1、x2都是有理数,这个方程的系数也都是有理数,根据前面第五块双有理等价的结论,可以断定x3也是有理数,从而y3也是有理数,从而P3也是有理点。
巧妙的是,由于曲线关于x轴的对称性,P3关于x轴的镜像点,必然也是有理点(因为仅仅是y坐标乘以-1)。而在代数几何领域,这个点被称为“P1+P2”。我们首先不用纠结于加法的重新定义。我们只需要知道这个新的有理点意义非凡,因为用这个“P1+P2"点,我们与P1连线的话(图中黄线),我们又得到了一个有理点A!也就是说,我们又找到了一个(x, y)的有理数解,也就是又找到了(a, b, c)的整数解。虽然(a, b, c)中仍然有可能有负数,但只要我们不停地迭代下去,就可能可以找到全部为正数的解!
回到我们的题上来。现在我们只有一个有理点(-100,260),我们将其想象为P1与P2无限接近,产生了“重根”,那么由P1、P2所确定的直线将会是椭圆曲线在该点处的切线,而其切线的斜率将是该处的导数(此处对中学的小朋友可能略微有一些超纲)。我们推导一下这个导数的计算过程:
对两边求导,得到,进而得到,这个就是斜率k。
将x=-100,y=260代入,得到斜率。从而经过P点的直线函数为
我们将此y值代入到椭圆曲线中,得到一个看起来有点复杂的方程:
合并同类项,得到这样一个关于x的三次方程:
这个方程的系数看起来有点大,好在我们知道它有两个根都是x=-100,我们运用上面提到的多项式除法,两次除以(x+100)项,最终得到的另一个交点的x值:
代入到直线方程,从而得出该交点为
该点关于X轴的镜像点即为P+P=2P, 其坐标为
,如下图。
我们将得到的x和y值代入上述式(5),计算出a、b、c的值,并乘以它们的公分母,得到的整数值分别为:
a = 9499
b = -8784
c = 5165
经过验算,确实满足
不过,还是有负数!工作还得继续。
下面要做的,是把点P和2P连线,再去寻找3P的有理点,再算出a、b、c,再去检查是否全部正整数。
不过你一定发现,式子越来越复杂,靠手算已经行不通了。
八、寻找终极答案——计算的事情交给PYTHON
用计算机来计算,还是比较方便的。下面是迭代计算的python代码。
""" Created on Sun Dec 6 13:21:48 2020 @author: jacky """ from fractions import Fraction import math # 多项式的辗转相除法 def duc(p, poly_nrt): rv = [1, -p[0]] if len(poly_nrt) == 4: result = [1] result.append(poly_nrt[1] - rv[1]) result.append(poly_nrt[2] - result[1] * rv[1]) result.append(poly_nrt[3] - result[2] * rv[1]) elif len(poly_nrt) == 3: result = [1] result.append(poly_nrt[1] - rv[1]) result.append(poly_nrt[2] - result[1] * rv[1]) else: print('Error! Length of coefficients does not match.') return(0) if result[-1] != 0: print('Error! Result is Wrong.') return(0) return result[:-1] #定义加法 def add(p1, p2): #如果p1、p2是同一个点,那么该处斜率是该点的导数。如果不是同一个点,那么通过坐标可以计算出斜率 if p1 == p2: slope = Fraction(1,2) / p1[1] * (3*p1[0]**2 + 218*p1[0] + 224) else: slope = Fraction((p2[1] - p1[1]) / (p2[0] - p1[0])) #Function: y - p1[1] = slope * (x - p1[0]) #直线方程的系数(y = kx + b),k、b即为系数 coe_line = [slope, p1[1] - slope * p1[0]] #直线方程代入椭圆方程,计算方程系数 coe_ellipse = [1, 109 - coe_line[0] **2, 224 - 2 * coe_line[0] * coe_line[1], -coe_line[1]**2] res_1 = duc(p1, coe_ellipse) res_2 = duc(p2, res_1) x = -res_2[1] y = (slope * (x +100) +260) * (-1) return ([x,y]) p1 = [-100, 260] p2 = [-100, 260] a=0 b=0 c=0 #循环数 k=2 #寻找到a、b、c全部大于零为止 while not (a>0 and b>0 and c>0): p2 = add(p1,p2) x = p2[0] y = p2[1] a = Fraction(56-x+y, 56-14*x) b = Fraction(56-x-y, 56-14*x) c = Fraction(-28-6*x, 28-7*x) a/(b+c) + b/(a+c) + c/(a+b) #公分母 common_deno = a.denominator * b.denominator * c.denominator a = a * common_deno b = b * common_deno c = c * common_deno #分子最大公约数 gcd_numerator = math.gcd(math.gcd(a.numerator, b.numerator), math.gcd(a.numerator, c.numerator)) a = a / gcd_numerator b = b / gcd_numerator c = c / gcd_numerator print('循环数 k = ',k) print('a = ',a) print('b = ',b) print('c = ',c) print('验算结果:',a/(b+c) + b/(a+c) + c/(a+b)) k+=1
得出的结果是这样的:
循环数 k = 2
a = 9499
b = -8784
c = 5165
验算结果: 4
循环数 k = 3
a = 679733219
b = -375326521
c = 883659076
验算结果: 4
循环数 k = 4
a = 6696085890501216
b = -6531563383962071
c = 6334630576523495
验算结果: 4
循环数 k = 5
a = 5824662475191962424632819
b = -2798662276711559924688956
c = 5048384306267455380784631
验算结果: 4
循环数 k = 6
a = 287663048897224554337446918344405429
b = -399866258624438737232493646244383709
c = 434021404091091140782000234591618320
验算结果: 4
循环数 k = 7
a = 3386928246329327259763849184510185031406211324804
b = -678266970930133923578916161648350398206354101381
c = 1637627722378544613543242758851617912968156867151
验算结果: 4
循环数 k = 8
a = 343258303254635343211175484588572430575289938927656972201563791
b = -2054217703980198940765993621567260834791816664149006217306067776
c = 2110760649231325855047088974560468667532616164397520142622104465
验算结果: 4
循环数 k = 9
a = 154476802108746166441951315019919837485664325669565431700026634898253202035277999
b = 36875131794129999827197811565225474825492979968971970996283137471637224634055579
c = 4373612677928697257861252602371390152816537558161613618621437993378423467772036
验算结果: 4
当算到9P的时候,所有的a、b、c的结果为正。
至此,我们得到了最终的结果。
不过,a值已经高达80位数(b值79位,c值78位)。80位数是什么概念呢, 就是每8位是1亿,要连续说出9个“亿”字才能表达,亿亿亿亿亿亿亿亿亿。
这个数字大到什么程度呢,就是假如我跟你的距离是1米,那么这个数字所代表的距离在1053个宇宙之外(一个宇宙的直径是930亿光年)。注意,是10的53次方个。
如果不是用数学方法,即使是世界上最快的计算机,也完全不可能用暴力的方法(就是一个数字一个数字地尝试)得到最终的解。
九、进一步的探索
上面所用的方法就叫“弦切法”,好比你绷了一条弦,不停地在曲线上找第三个交点(有理点)。我们从上面的程序结果可以看出,随着过程的推进,a、b、c的数值快速增长,而这个80位数的结果,确实也是最小的结果。
此外,想要3者全部为正也并不是容易的事,这当然是跟x、y的取值有关系的。事实上,只有下图的绿色部分才是a、b、c可以取到正值的位置。看样子,我们能在第8次迭代(9P)的时候进入这个区域还算运气不错了。
你可能会觉得,80位数的结果令人发指。但如果我们把原方程的4替换为178,我们的结果将是几亿位(这意味者屏幕远远不能满足显示需求);而如果把4替换为896,那么结果将是万亿位的。
我们上面用到的计算椭圆曲线kP的算法,在现代密码学方面有着极其重要的应用(也就是正向的计算很容易,反向的计算非常困难)。椭圆曲线加密算法称为三大加密算法之一,著名的、稳定运行十余年的比特币就是采用的椭圆曲线加密算法。
十、说明及感悟
最后,我想读者中可能还是有不少存疑,即:
1、为什么我们可以在第四部分做那样的变换,把a、b、c的方程变换成了x、y的椭圆曲线?
2、到底通过什么方式找到(-100,260)这个椭圆曲线的特解?
3、为什么我们最终这个80位的解就是最小解?
这些都是本文没有解决的问题。因为这些都是很庞大的问题,本人争取以后能给出容易理解的答案。
但幸好,就本题而言,首先我们找到了解(这是根本性的),其次我们确实了解了整个求解过程,并对其内在逻辑有了全面的认识。
解这个题目,有一种以为到楼下打个酱油,结果却到大海上绕了一圈的感觉,差一点找不到回来的路。
然而数学之美,正在于她以极其精确的方式,告诉了你正确的方向。
最后,恭喜你,你看完了。
Quora上Alon Amit的英文解答链接在此:https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4/answer/Alon-Amit,不过你可能需要一点科学的办法才能打开。
本人才疏学浅,解题中可能有不少不够严谨的地方,欢迎指正。