史上最难奥数题

luyuanhong

史上最难奥数题

难倒整个议题委员会、四位数论专家，还有数学天才陶哲轩的传奇奥数题目到底有多难？

撰文 | 史丹福狂想曲

玩过奥数或者其他数学竞赛的朋友大概都会听过”传奇的第6题”。这条题目出自1988年国际数学奥林匹克竞赛（International Mathematical Olympiad，简称IMO）的第6题，是公认的史上最精彩、也是最困难的其中一道竞赛题目。

题目如下：

设正整数 a, b 满足 ab+1 可以整除 a^2+b^2，证明 (a^2+b^2)/(ab+1) 是某个整数的平方。

例如代入 a = 1，b = 1，我们得到 k = (1^2+1^2)/(1x1+1) = 1，显然这是一个平方数。正如很多数论问题一样，这题目很容易理解，初中生都可以明白，但解答起来却出奇地困难。

1 传奇的第6题

这题目究竟有多困难呢？ 我们先简介一下IMO的题目来源，好让大家对这比赛有更多的认识。

IMO竞赛是让全世界不同国家的中学生参与的数学比赛，共有6道题目，比赛分两天，每天做三题，总共时间为9小时。题目基本上都是证明类题目，每题值7分，共42分。试题大致上会分为简单、中等与困难三个等级，第1与第4题属简单，第2与第5题属中等，第3与第6题属困难。题目由主办国外的各参赛国提供，由主办国组成拟题委员会，从提交题目中挑选候选题目。各国领队先于队员提前数天抵达，共同商议问题及官方答案。

话说当年西德是奥数的超级强队，曾经于1982与1983年获得总分第一。但之后几年却被苏联、罗马尼亚及美国超越了，抢夺了第一的宝座。有人认为也许是出于复仇心态，西德数学家就出了这道精心设计、极尽困难的题目。澳大利亚数学奥林匹克议题委员会的六个成员都未能解决这道由西德数学家提供的问题，于是他们只好向主办国澳大利亚的4位最好的数论专家求肋，委员会希望专家能于6小时内解决问题，令人尴尬的是，专家经过一轮苦战都未能解出题目。于是，议题委员竟然够勇气把问题寄往国际数学奥林匹克委员会，不过他们特意在问题旁加上两颗星，代表这是超难题目——也许难到不应用作竞赛题目。委员会作了长时间的考虑后，又竟然真的斗胆敢采用此题，结果这个题目就成了第29届国际数学奥林匹克竞赛的第6题。

委员会有人觉得这可能会成为破纪录的没有选手解出的国际奥数问题。然而事实上结果却并不是那么悲观：虽然268名选手在这道题目上的平均得分只有0.6分，为IMO举办29年以来平均得分最低的一题，但这个难倒4位数论专家的题目，却被11位中学生以7分满分的成绩解答出来。

陶哲轩被誉为当今世上最出色的年轻数学家之一。他自小已是数学天才，于10岁、11岁及12岁参加了三次国际数学奥林匹克竞赛，分别得了铜奖、银奖与金奖，是铜奖、银奖与金奖的最年轻得奖纪录保持者。他于16岁得到学士学位，21岁得到普林斯大学博士学位，并在24岁成了加州大学洛杉矶分校（University of California, Los Angeles，简称UCLA）数学系的终身教授，是该校史上最年轻的终身教授。  他于31岁获得菲尔兹奖。菲尔兹奖是数学界最高的荣誉，由于诺贝尔奖不设数学奖，所以菲尔兹奖基本上就是等同于数学界的诺贝尔奖。

为何我突然花这么多的时间介绍陶哲轩呢？因为他参与了1988年的国际数学奥林匹克竞赛并获得金奖，他于头5题都全取7分，最后的第6题却只有1分。这条超级难题连当今世上其中一位最出色的数学家都破解不了，令题目更添传奇色彩。


当年12岁的陶哲轩获得1988年国际数学奥林匹克竞赛金奖。| 来源：国际数学奥林匹克竞赛网站

有一位参赛者，保加利亚选手Emanouil Atanassov却得到了该题的特别奖。特别奖的得奖者必须要用一种非常漂亮、精彩独到的方法解题，答案比标准答案更精彩，常常也更简洁，才有机会得奖，可以说是比得到满分更困难。而他用到的方法叫“韦达跳跃”（Vieta jumping）。笔者找不到文献记载中，在这道奥数问题出现以前有没有人用过此方法解数学题，不过可以肯定的是，这方法在该届IMO之后变得声名大噪，现今已是参加数学比赛者训练时必定会学到的技巧。

2 韦达跳跃

“韦达跳跃”的概念其实都只是来自高中数学，没有什么高深的，只不过是利用了极尽巧妙的方法，把初等数学的威力发挥得淋漓尽致而已。这技巧牵涉到两个重要数学知识：一是韦达定理（Vieta’s theorem），一是无穷递降法（method of infinite descent）。

韦达定理其实就是二次方程中根的和与积及系数的关系：

设一元二次方程 ax^2+bx+c=0 有根 α 与 β ，那么 α+β = -b/a，αβ=c/a 。

这应该是DSE（香港中学文凭考试）高中数学第一课的内容，是广为人知的（虽然课程没有用到韦达定理这个很专业的名称）。

至于无穷递降法则是一种反证法，用的是“没有最小，只有更小”的概念。如果我们假设，一方程式如果有一正整数解，那么应该有一最小的解。然后我们再证明“如果有一解，必有另一个更小的解”，也就是说“没有最小，只有更小”，这与方程式有最小解互相矛盾。唯一的可能性就是我们的假设出错，方程式根本上没有解。

这个方法最先由大数学家费马使用，他据此证明了 x^4+y^4=z^4 没有正整数解，也就是费马大定理中 n=4 的情况。欧拉也用无穷递降法证明过，每个除4后余数为1的质数都可以表达为两个平方之和。值得一提的是，这定理也是由费马最先提出的，虽然他没有提出证明。

3 破解难题

言归正传，我们就试试用这种方法解开传奇的第6题吧！

ab+1 可以整除 a^2+b^2，所以 (a^2+b^2)/(ab+1) 是正整数。设有正整数 a 及 b 满足 (a^2+b^2)/(ab+1)=k，其中 k 不是平方数，我们将制造出一个矛盾去证明这是不可能的，所以 k 必为平方数。



这个题目令“韦达跳跃”声名大噪，现在不少数学竞赛的书籍，甚至是大学的教科书都会用这“传奇的第6题”为例子，所以以现今的标准来看这题目不算太困难。如果现在的IMO再出一道有关“韦达跳跃”的数论题目，参加者们也大概会有不错的成绩。不过它在当年难倒整个议题委员会、四位数论专家、数学天才陶哲轩及很多数学好手，称这传奇题目为史上最难的奥数题目绝不为过。

后 记

by 文小刚

还没完......

虽然证明之后好像就完事了，但我们还可以进一步探索。

下面我们做一下“实验”，用计算机寻找满足 ab+1 可以整除 a^2+b^2 的正整数对 a,b（只列 a<=b）。如果你真的做了计算，马上会发现有两类解。第1类解中的 a 可以是任意的正整数 n，而 b 是 a 的三次方：

(a，b)=(n，n^3)；

第2类解中，a 是某一正整数 n 的三次方：

(a，b)=(n^3，n(n^4-1))；

对于这两类解我们有

(a^2+b^2)/(ab+1)=n^2。

但这两类并不是所有的解，我们还有其他的解：



具体实验又给我们带来新的问题，让我们可以继续探索。如何理解这第3类看似不规则的解，有兴趣的读者接下来可以进一步考虑，看能不能系统地构造出所有的解。

波斯猫猫

这是理念胜于知识的一个典型案例，也是未出茅庐的嫩芽打败久经沙场的“大家”的典型案例。用来挑战人类智慧的极限莫过于数学。

蔡家雄

史上最难奥数题

设 k0=n , ( n>=2 )

设 k1=n^3 ,

得 k2=(n^2)*k1 - k0 ,

得 k3=(n^2)*k2 - k1 ,

得 k4=(n^2)*k3 - k2 ,

如此类推，

设 a, b 为 k 数列中两个连续的数，

则 (a^2+b^2) / (a*b+1) = n^2 .

蔡家雄

，，，，，，，，，，，，，，，，，，，，

蔡家雄

蔡家雄 发表于 2020-3-14 11:11
求证(1) n^2 = (a^2+b^2) / (a+b+2) 均有整数解。

求证(2) n^2+(n+1)^2 = (a^2+b^2) / (a+b+2) 均有整 ...

即 (a^2+b^2) / (a+b+2) ，

既 包括所有的平方数：n^2，

又 包括所有的两个连续平方和：n^2+(n+1)^2，

蔡家雄

求 n*(n+1)= (a^2+b^2 - 1) / (2a+2b+4) 的通解公式，

则 { a, b }={ n, (2n+1)(2n+2)/2 } ,

及 { a, b }={ 2n(2n+1)/2, (2n+1)(2n+2)/2 }.

蔡家雄

求 n*(n+1) -1= (a^2+b^2 - 3) / (2a+2b+4) 的通解公式，

则 { a, b }={ n, (n+1)(2n+1) -2 } ,

及 { a, b }={ n*(2n+1) -2, (n+1)(2n+1) -2 }.

蔡家雄

求 n*(n+1)+1= (a^2+b^2+1) / (2a+2b+4) 的通解公式，

则 { a, b }={ n, (n+1)(2n+1)+2 } ,

及 { a, b }={ n*(2n+1)+2, (n+1)(2n+1)+2 }.

蔡家雄

求 n^2= (a^2+b^2) / (a+b+2) 的通解公式，

则 { a, b }={ n, n*(n+1) } ,

及 { a, b }={ n*(n -1), n*(n+1) }.

蔡家雄

求 n^2+(n+1)^2= (a^2+b^2) / (a+b+2) 的通解公式，

则 { a, b }={ n, (n+1)(2n+1)+1 } ,

及 { a, b }={ n*(2n+1)+1, (n+1)(2n+1)+1 }.