史上最難的奧數競賽題目

史上最難的奧數競賽題目

我們想讓你知道的是

1988年國際數學奧林匹克競賽第6題,是公認史上最精彩也是最困難的競賽題目之一。

玩過奧數或者其他數學競賽的朋友大概都會聽過「傳奇的第6題」,即1988年國際數學奧林匹克競賽(International Mathematical Olympiad,簡稱IMO)第6題,是公認史上最精彩也是最困難的競賽題目。

題目如下:設正整數a, b滿足ab+1可以整除a2+b2,證明(a2+b2)/(ab+1)是某個整數的平方。

例如代入a = 1,b = 1,我們得到 k = (12+12)/(1x1+1) = 1,這顯然是個平方數。跟很多數論問題一樣,這題目很易理解,初中生都可以明白,解答起上來卻出奇地困難。

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

難倒專家的題目

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

話說當年西德是奧數的超級強隊,曾經於1982與83年獲得總分第一,但之後幾年卻被蘇聯、羅馬尼亞及美國超越了,搶奪了其第一的寶座。有人認為也許是出於復仇心態,西德數學家出了這道精心設計、極盡困難的題目。澳洲數學奧林匹克擬題委員會6個成員都未能解到這問題,於是他們只好向主辦國澳洲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分。這條超級難題連當今世上其中一位最出色的數學家都破解不了,令題目更添傳奇色彩。

獲特別獎的解題方法

保加利亞選手Emanouil Atanassov卻得到了該題的特別獎。特別獎的得獎者必須用非常漂亮、精彩獨到的方法解題,答案比標準答案更精彩,通常也更簡潔,才有機會得獎,可以說比得到滿分更困難。他用到的方法叫「韋達跳躍」(Vieta jumping)。史丹福找不到文獻記載這條奧數問題出現前有沒有人用過此方法解題,不過可以肯定的是,這方法在該屆IMO之後聲名大噪,現今已是參加數學比賽者訓練時必定會學到的技巧。

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

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

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

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

言歸正傳,我們就試試用這方法解開傳奇的第6題吧!

ab+1可以整除a2+b2,所以(a2+b2)/(ab+1)是正整數。

設有正整數a及b滿足(a2+b2)/(ab+1)=k,其中k不是平方數,我們將製造出一個矛盾去證明這是不可能的,所以k必為平方數。

在眾多組滿足條件的正整數a、b中,必有一組的和是最小的,我們設它為a1與b1。由於把a1與b1互換,也不會影響(a12+ b12)/(a1b1+1)的值,所以我們不妨假設a1≥ b1

Vieta

根據(1),a2必為整數。

根據(2),a2不可能是0,因為k不是平方數,b12-k不可能是0。

k是正整數,b1是正整數,而且(a22+ b12)/(a2b1+1) = k,顯然a2不可以是負數。[編按]

大家還記得我們假設過a1≥ b1嗎?因此根據(2),a2必定少於a1。綜合來說,我們有一少於a1的正整數a2,令(a22+ b12)/(a2b1+1) = k,其中k不是平方數。因此a2與b1是滿足(a2+b2)/(ab+1)=k(其中k不是平方數)的一組解,但它們的和比a1+b1小,「沒有最小,只有更小」。不過我們之前已經設了a1與b1的和是眾多組解中最小的,這樣就產生矛盾。

因此如果正整數a及b滿足ab+1可以整除a2+b2,則(a2+b2)/(ab+1)必定是平方數。「韋達跳躍」就是這樣簡潔地破解了這超級難題。

這題目令「韋達跳躍」聲名大噪,現在不少競賽數學的書籍,甚至是大學的教科書都會用這「傳奇的第6題」為例子,所以以現今的標準來看這題目不算太困難。如果現在的IMO再出一題有關「韋達跳躍」的數論題目,參加者們也大概會有不錯的成績。不過它在當年難倒整個擬題委員會、四位數論專家、數學天才陶哲軒及很多數學好手,稱這傳奇題目為史上最難的奧數題目絕不為過。

編按︰假設 a2b1+1 = 0,即 a2b1 = -1,由於b1是正整數,唯一解是 a2 = -1, b1 = 1,代入該二次方程中,可得 (-1)2 - k(1)(-1) + (12-k) = 0,即1+k+1-k = 0,得出2=0,矛盾。因此 a2b1+1 ≠ 0,(a22+ b12)/(a2b1+1) = k。

本文獲授權轉載,原文見作者網誌

相關文章︰

責任編輯︰Kayue
核稿編輯︰Alex


猜你喜歡


一圖看懂微電腦瓦斯表:三大安全遮斷功能,守護居家安全「不漏氣」

一圖看懂微電腦瓦斯表:三大安全遮斷功能,守護居家安全「不漏氣」

我們想讓你知道的是

相較於傳統機械式瓦斯表,微電腦瓦斯表可以主動偵測異常情況,在漏氣、超時使用、五級以上地震發生時,自動遮斷瓦斯,以防瓦斯外漏所造成的氣爆、火災等危害,強化居家安全的守護。

你收過瓦斯公司寄來說明可換裝微電腦瓦斯表的通知單嗎?自從2011年天然氣事業法通過之後,政府便開始推廣微電腦瓦斯表,屆齡換裝微電腦瓦斯表完全免費,每個月也只要多40元的基本費,就可以享受微電腦瓦斯表所帶來的安全保障。和傳統瓦斯表相比,微電腦瓦斯表增加了精密微電腦晶片、感震器、壓力開關、緊急遮斷閥等零組件,在偵測到漏氣、超時使用、大地震時,便會進行自動遮斷功能。這些功能對你我的居家安全有什麼保障?一起來搞懂吧!

微電腦瓦斯表_第一篇_完稿

三大安全遮斷-漏氣遮斷

瓦斯管線會因為風吹雨淋日曬、被老鼠嚙咬等原因,而慢慢老化破裂;再加上台灣地震頻繁,也是導致瓦斯管線鬆脫漏氣的原因之一。一般來說,我們可以透過發現家中瓦斯的使用量異常增加,或者是聞到瓦斯特有的臭味,來注意到瓦斯有漏氣的情況。可是,現代家庭的瓦斯管線往往鋪設在室外,又或者大量漏氣的時候沒人在家、或正在其他房間休息,可能不會發現這個危險警訊。

微電腦瓦斯表可以偵測到瓦斯漏氣的問題,並且自動進行「漏氣遮斷」,在第一時間阻止易燃的瓦斯洩漏,以免在不知情的狀況下浪費瓦斯,甚至造成嚴重災禍,全家人每天都能安心生活。

三大安全遮斷-超時遮斷

想必很多人都有急著出門,然後突然想不起自己到底有沒有把爐火關掉的經驗吧?這種不踏實的心情,在忙得抽不開身的時候,特別讓人覺得難受。大家可能也聽說過,家中長輩開了瓦斯爐燒水泡茶,結果朋友打電話來聊天,講著講著就忘記瓦斯爐的火還開著,如果爐火一直燒下去,可能真的會導致一發不可收拾的憾事。

微電腦瓦斯表可以偵測瓦斯的使用量與時間的關係,開大火的話,用氣的時間會縮短;開小火的時候,時間就會相對拉長。這個功能可以在家人使用瓦斯,但忘了關火時,自動判斷是不是應該要啟動「超時遮斷」的功能。

三大安全遮斷-地震遮斷

發生五級以上的地震時,如果正好在使用瓦斯,微電腦瓦斯表就會馬上停止供氣,這就是「地震遮斷」功能。說到地震,其實和微電腦瓦斯表的發明及推廣有著非常密切的連結。日本早在1987年就開始推廣使用微電腦瓦斯表,因為有這項設備,所以不管是1995年的阪神大地震,或者2011年的311大地震,都因為「地震遮斷」發揮作用,才不至於因為瓦斯而引起更多事故。

同樣位於地震帶上的台灣,我們向來十分在乎房屋的結構和材料是否防震,如果能更進一步裝設微電腦瓦斯表,在地震發生時發揮作用,自動遮斷瓦斯,就能防止因為設備損壞所造成的瓦斯外洩以及氣爆、火災等事故。

微電腦瓦斯表在日本目前已有將近100%之普及率。在台灣,目前的年度裝置率則從2014年的8.43%,提升至2022年第2季的48%。所謂多一份用心,就是多一份保障。在我們小心用氣、用火的同時,再加上微電腦瓦斯表的主動防護,家人的生命安全和財產保障,就更加完整了!

經濟部能源局廣告


猜你喜歡