【史上最難的奧數題目】理論數學家解不開,但神人用高中數學輕鬆破解

「傳奇第 6 題」的題目內容,截圖自 MATHEMATICS

在數學界中,有一道很經典的難題叫「傳奇的第 6 題」(The Legend of Question Six)。它是國際數學奧林匹亞當中,公認史上最困難的題目。

這道題目是這樣的:

假設正整數 a、b,滿足 ab + 1 可以整除 a^2 + b^2,證明 (a^2 + b^2) / (ab + 1) 是某個整數的平方。

Let a and b be positive integers such that ab + 1 divides a^2 + b^2. Show that (a^2 + b^2) / (ab + 1) is the square of an integer.

這道題目,當年的奧林匹亞數學議題委員會,以及 4 位數論專家都解不開,被認為「不適合放到競賽題目中」。最後它還是變成了比賽題目,而且還被參賽者解開。

傳奇的第 6 題,當年的理論數學家也解不出來

首先,我們來認識國際數學奧林匹亞競賽。

國際數學奧林匹亞(International Mathematical Olympiad,IMO,下文簡稱奧數)是全球性的數學競賽,參賽對象為全球的中學生,可說是數學界的奧運,從 1959 年開始舉辦,至今已有 60 年的歷史,是國際科學奧林匹亞當中歷史最長的賽事。奧數競賽共有 6 道題目,基本上都是證明題,分為簡單、中等與困難 3 個等級,第 1 與第 4 題屬於簡單題,第 2 與第 5 題屬於中等題,第 3 與第 6 則是困難題。每題滿分為 7 分,總分 42 分。

奧數每年都由不同的國家主辦(台灣曾擔任 1998 年的主辦國),題目由主辦國外的其他參賽國提供,主辦國會組織擬題委員會,從題目當中選出候選題目,再由參賽各國一同商議出最終競賽題目與官方解答。

而「傳奇的第 6 題」是 1988 年的題目,是由西德數學家提供的。西德曾獲 1982 和 1983 年的奧數冠軍,後來被美國、蘇聯、羅馬尼亞等國奪去冠軍頭銜,西德數學家就在 1988 年,精心設計超難的「傳奇的第 6 題」。

當年主辦國是澳洲,結果擬題委員會的 6 個成員都無法解開這道難題,他們向國內最強的 4 位數論專家求助,他們也無法解題。但是擬題委員會仍然把這道題目列為候選題,結果各國商議過後,竟然真的採用這道題目,成為第 29 屆奧數的第 6 題。

更驚人的是,竟然有參賽選手解開這道題目。雖然 268 位選手的平均得分只有 0.6,是奧數 29 年來分數最低的一題,卻有 11 名選手取得滿分。要特別強調的是,奧數是辦給「中學生」的數學競賽,那些中學生能夠解開理論數學家解不開的題目,真的非常驚人。

他們是怎麼破解「傳奇的第 6 題」的?

奧數選手用高中程度的「韋達跳躍」,破解傳奇的第 6 題

其實他們用的並不是微積分、離散數學、線性代數等高等數學技術,而是高中數學程度的「韋達跳躍」(Vieta jumping)。韋達跳躍包含兩個部分:韋達定理(Vieta’s theorem)、無窮遞降法(method of infinite descent)。

韋達定理描述二次方程式當中,兩根的和、積與項數之間的關係,這是台灣高一數學課的內容。韋達定理是這樣的:

假設一元二次方程式 ax^2 + bx + c = 0 有兩根 α、β,則 α + β = -b/a,αβ = c/a。

無窮遞降法則是一種反證法,台灣高中數學不特別教無窮遞降法,因此對高中生來說,這的確是一種艱深的數學技術;但高一數學的「數學歸納法」會提到反證法,可能還是會有些「神人」懂無窮遞降法。無窮遞降法是這樣的:

先假設方程式有解,並假設 X 為最小解;接著再從 X 出發,嘗試推導出另一個更小的解 Y。若能推導成功,代表與前題假設「X 為最小解」矛盾,因此能證明此方程式無解。

使用上述方法,解答「傳奇的第 6 題」的思維會是:

1. 根據題目敘述,ab + 1 可以整除 a^2 + b^2,所以 (a^2 + b^2) / (ab + 1) 是正整數;假設該正整數為 k。

2. 接著,假設有正整數 a、b 滿足 (a^2 + b^2) / (ab + 1) = k,而 k 不是平方數。

3. 最後,假設在所有滿足條件的正整數中,有一組是 a1、b1,它們擁有最小的和;假設 a1 >= b1。

解題時,就可以製造一個矛盾,證明還有比 a1、b1 小的值,因此前一個假設「k 不是平方數」也不成立。最後就可以證明「k 是平方數」,(a^2 + b^2) / (ab + 1) 的值必定是某個數字的平方數。

我們可以開始解題了:

根據 (1),由於 k、b1、a1 皆為整數,因此 a2 必為整數。
根據 (2),由於 k 不是平方數,(b1)^2- k 不可能是 0,因此 a2 不可能是 0。
根據 (a2^2 + b1^2) / (a2b1 + 1) = k,由於 k、b1 是正整數,因此 a2 不可能是負數。

也就是說,a2 是個正整數。

前面,我們假設過 a1 >= b1,因此根據 (2),a2 一定小於 a1,因此 a2 + b1 為更小值,與「a1 + b1 為最小整數解」的假設矛盾,也因此「k 不是平方數」是錯誤的假設。可以證明,(a^2 + b^2) / (ab + 1) 的值必定是某個數字的平方數。

雖然高中生不會記得「韋達定理」這個名稱,但它是高中數學很基本的解題技巧,是小考、段考考到爛掉,學測、指考也會出現的概念。「無窮遞降法」的難度較高,但背後的原則「反證法」也是高中證明題常用到的技術。然而就是會有厲害的人,能夠用這些基本的技術,搭配巧思,解答理論數學家無法解答的難題。

看到這麼乾淨的思維與解題流程,真的是佩服那些奧數的參賽選手(跪了)。

參考資料來源:
1.《史丹福狂想曲》:〈 史上最難的奧數題目
2.《Science Alert》:〈The Legend of Question Six: One of The Hardest Maths Problems Ever
3.《MATHEMATICS》:〈Simple solution to Question 6 from the 1988 Math Olympiad [duplicate]
(本文提供合作夥伴轉載。首圖截至 MATHEMATICS

延伸閱讀

工程師別惹怒數學家!25 年前,「布朗常數」讓英特爾賠 145 億台幣
集結 50 萬台電腦算力,數學家終於破解困擾 65 年的難題:三立方數和
教你如何用 Python 執行蒙地卡羅方法,證明圓周率等於 3.1415926


IT x OT 資安攻防戰!

工廠轉型最常碰到的「系統整合難題」怎麼迎刃而解?

馬上破解

 

點關鍵字看更多相關文章: