史上最難的奧數題目

玩過奧數或者其他數學競賽的朋友大概都會聽過「傳奇的第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，顯然這是一個平方數。正如很多數論問題一樣，這題目很易理解，初中生都可以明白，但解答起上來卻出奇地困難。

究竟這題目有多困難呢？或者讓史丹福先簡介一下IMO的題目來源，好讓大家對這比賽有更多的認識。

IMO競賽是讓全世界不同國家的中學生參與的數學比賽，共有6題題目，比賽分兩天，每天做三題，總共時間為9小時。題目基本上都是證明類題目，每題值7分，共42分。試題大致上會分為簡單、中等與困難，第1與第4題屬簡單，第2與第5題屬中等，第3與第6題屬困難。題目由主辦國外的各參賽國提供，由主辦國組成擬題委員會，從提交題目中挑選候選題目。各國領隊在隊員前數天抵達，共同商議出問題及官方答案。

話說當年西德是奧數的超級強隊，曾經於1982與83年獲得總分第一。但之後幾年卻被蘇聯、羅馬尼亞及美國超越了，搶奪了其第一的寶座。有人認為也許是出於復仇心態，西德數學家就出了這道精心設計，極盡困難的題目。澳洲的數學奧林匹克議題委員會的六個成員都未能解到這題由西德數學家提供的問題。於是他們只好向主辦國澳洲的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之後變聲名大噪，現今已是參加數學比賽者訓練時必定會學到的技巧。

「韋達跳躍」的概念其實都只是來自高中數學，沒有甚麼高深，只不過是利用了極盡巧妙的方法，把初等數學的威力發揮得淋漓盡致而已。

這技巧牽涉到兩個重要數學，一是韋達定理（Vieta’s theorem），一是無窮遞降法（method of infinite descent）。

韋達定理其實就是二次方程中根的和與積及項數的關係，設ax²+bx+c=0有根α與β，α+β = -b/a，αβ=c/a。這應該是DSE高中數學第一課的內容，是廣為人知的（雖然課程沒有用到韋達定理這個很專業的名稱）。

至於無窮遞降法是一種反證法，用的是「沒有最小，只有更小」的概念。如果我們假設一方程式有一正整數解，那麼應該有一最小的解。然後我們再證明「如果有一解，必有另一個更少的解」，也就是說「沒有最小，只有更小」，這與方程式有最小解互相矛盾。唯一的可能性就是我們的假設出錯，方程式根本上沒有解。 這個方法最先由大數學家費馬使用，證明了x⁴+y⁴=z⁴沒有正整數解，也就是費馬大定理中n=4的情況。歐拉也用無窮遞降法證明過每個除4的餘數為1的質數都可以表達為兩個平方之和，值得一提的是這定理也是由費馬最先提出的，雖然他沒有提出證明。

言歸正傳，我們就試試用這方法解開傳奇的第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₁。

根據(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再出一題有關「韋達跳躍」的數論題目，參加者們也大概會有不錯的成績。不過它在當年難到整個議題委員會、四位數論專家、數學天才陶哲軒及很多數學好手，稱這傳奇題目為史上最難的奧數題目絕不為過。