史上最难奥数题

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

撰文 | 史丹福狂想曲

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

题目如下：

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

例如代入a = 1，b = 1，我们得到 k = (1²+1²)/(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²+bx+c=0 有根α与β，那么α+β = -b/a，αβ=c/a。

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

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

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

3破解难题

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

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

在众多组满足条件的正整数a、b中，必有一组的和是最小的，我们设它为a₁与b₁。由于把a₁与b₁互换，也不会影响 (a₁²+ b₁²)/(a₁b₁ +1) 的值，所以我们不妨假设a₁>= b₁。

将a₁与b₁代入上面的式子得到，

a₁是一元二次方程 x² - kb₁ x+ (b₁²-k) = 0 的一个根，设方程的另一个根为a₂。根据韦达定理，我们得到

由此进一步得到a₂需要满足的条件，

根据 (1)，a₂必为整数。

根据 (2)，a₂不可能是0，因为k不是平方数，b₁²-k不可能是0。

k是正整数，b₁是正整数，(a₂²+ b₁²)/(a₂b₁+1) = k，显然a₂不可以是负数。

大家还记得我们假设过 a₁>= b₁ 吗？因此根据 (2)，a₂必定小于a₁。

综合来说，我们有一小于a₁的正整数a₂，令(a₂²+ b₁²)/(a₂b₁ +1) = k，其中k不是平方数。a₂与b₁是满足(a²+b²)/(ab+1)=k（其中k不是平方数）的一组解，但它们的和比a₁与b₁小，“没有最小，只有更小”。不过我们之前已经假设了a₁与b₁的和是众多组解中最小的，这样就产生矛盾了。因此如果正整数a, b满足ab+1可以整除a²+b²，(a²+b²)/(ab+1)必定是平方数。“韦达跳跃”就是这样简洁地破解了这道超级难题。

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

by 文小刚还没完......虽然证明之后好像就完事了，但我们还可以进一步探索。下面我们做一下“实验”，用计算机寻找满足ab+1可以整除a2+b2的正整数对a,b（只列a<=b）。如果你真的做了计算，马上会发现有两类解。第1类解中的a可以是任意的正整数n，而b是a的三次方： (a，b)=(n，n3)；第2类解中，a是某一正整数n的三次方： (a，b)=(n3，n(n4-1))；对于这两类解我们有(a2+b2)/(ab+1)=n2。但这两类并不是所有的解，我们还有其他的解：具体实验又给我们带来新的问题，让我们可以继续探索。如何理解这第3类看似不规则的解，有兴趣的读者接下来可以进一步考虑，看能不能系统地构造出所有的解。

本文除“后记”外转载自博客“史丹福狂想曲”，原文题目为“史上最难的奥数题目”，原文链接https://drstanford.blogspot.com/2020/02/blog-post.html 。

想要继续挑战吗？1988年国际数学奥林匹克竞赛的完整试题在这里：

https://www.imo-official.org/year_info.aspx?year=1988

来源：返朴

END

往期精彩回顾

数学的惊艳之美
数学——看不见的文化
中国人的数学为什么这么好？

我就知道你在看！