史上最難的奧數競賽題目

史上最難的奧數競賽題目

我們想讓你知道的是

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


猜你喜歡


36歲身價千萬仍然沒有安全感?善用「負債」,縮短與財富自由的距離

36歲身價千萬仍然沒有安全感?善用「負債」,縮短與財富自由的距離
photo credit:VI College價值投資學院

我們想讓你知道的是

本文以VI College價值投資學院的學員案例來分析推導,說明透過系統性的分析、目標設定及投資規劃,財富自由並非遙不可及的夢想,甚至能藉此達成財富自由與志業圓滿的雙重目標。

財富自由是許多人共同夢想,如果可以擁有足夠被動收入讓生活無虞,甚至還能每月度假,相信這是許多人欣羨的生活。然而,財富自由確實是很好的理財目標,卻未必是「快樂」的終點。

36歲的心怡過去時常在各地飛來飛去長達八年,高壓工作、生活作息日夜顛倒,也為自己累積下遠高於同齡人的資產。分析心怡的資產負債現況:現金活存、股票、外幣存款、美股、債券、保險,包含名下一棟房地產,即便房子還有500多萬房貸,但總資產淨值有1300多萬。

她的夢想跟許多人相同,希望能靠著理財就不需要工作,每月有10萬元用來度假、15萬生活開銷資金和給家裡5萬的孝親費,同時維持目前每個月公益捐款的好習慣。現階段生活看似豐盛,但是距離自己設定的3億身家還有相當長一段距離,特別是盤點目前可動用初始資金只有美金3萬元,更讓心怡覺得目標難以達成。而在離開上一份工作後就因為帳面不缺錢而始終待業中,也讓心怡對未來不時感到不安。

擁有千萬身價,想要過上相對充裕、財富自由的生活是否是件難事?或許關鍵就在於資產負債組合當中的「負債」!

六月第二篇_(1)
photo credit:VI College價值投資學院
VI College價值投資學院台灣區總經理黃士豪建議心怡善用負債,打造財富自由並進而追求人生使命感。

給心怡的建議一:財富自由的關鍵在於善用「負債」。

與多數諮詢的學員相比,心怡的投資體質跟觀念都算相當完善,特別是本身資產分配方向十分多元,表現出對於投資她是有長期研究且願意嘗試的。而透過完整檢視「資產負債」「資產損益」及「投資組合」三張表格,我可以在短時間內理解學員本身屬於哪種類型投資者,目前於投資理財方面存在什麼問題通常也能一目了然。

財務問題一定是出在負債嗎?以心怡這個案例來看,反而是卡在分配最多資產於「保險」上,而能讓自己加速達成財富自由的機會,反倒是唯一且最大的負債「房貸」。

心怡的房子目前剩餘房貸已經低於房價50%,我建議她可以尋找銀行重新談30年換貸並加上使用三年房貸寬限期,這樣除了立即將每月10,000多元房貸支出減輕為幾千元,對待業中的心怡來說可減輕相當大支出負擔,還能取得一筆不小的資金將防守型資產轉為進攻型資產。如果又進一步將那些投資報酬率過低的儲蓄險贖回,將資金都投入進攻型投資項目中,能在三年寬限期內靠著投資達成每月10,000多元的被動收入,等同於用手邊資金幫自己繳未來每月房貸。

給心怡的建議二:明確財務目標,距離財富自由其實很近。

但想要財富自由真有那麼困難嗎?或許單靠心怡目前手邊資產能在60歲前達成願望。

如果以心怡目前保障型資產高達518萬、防守型資產1400多萬、進攻型資產僅有250萬,分配比例為24:64:12現況來看,如果維持投資組合現況每年約8%獲利計算,要達到3億身家需要40年9個月。

圖表_1_
photo credit:VI College價值投資學院
資產配置比例分配示意圖

但如果能將保障型資產降低至6%,防守型資產降低為31%,進攻型資產提高到63%,就目前心怡於美股平均獲利為15%,只需要將獲利提高至20%,16年又8個月就能實現3億身家目標。

圖表_2
photo credit:VI College價值投資學院
資產配置比例分配示意圖

但事實上3億真的是必要目標嗎?如果以心怡希望的未來生活來看,即使加上換房、換車及新房裝修等開銷,也只需要1億3千多萬資產,同樣投資組合、同樣獲利只需要13年,心怡於50歲前就能實現財富自由夢想。

給大家的財富建議:比起追求金錢,更該追求使命。

雖然心怡有相當大機會達成財富自由的夢想,但在諮詢過程中我也發現她對未來的不安感,主要原因來自缺乏「使命」。即使可以靠著理財就擁有不錯的生活,但缺乏使命可能會讓人覺得人生沒有重量感。除了追求財富自由,我常常建議學員建議一定要找到「沒有錢也會願意做」的事情,才有辦法創造更多財富,所以建議目前待業中的心怡可以趁著目前還沒有生活壓力,找到「使命」並做為主動收入來源。

我也會透過一連串問題引導學員,從這些問題的答案中找到一個方向後確實執行,無論透過創業、找到相關產業或相關職位,建立屬於自己的中長期志業規劃。在執行跟學習過程當中,也能夠找到更多元的新道路,這是每個成功者在找到財富事業前必經之路,藉由系統性的分析、規劃及目標設定,讓自己找到真正的人生快樂泉源。關鍵在於:你有找到屬於自己的「使命」了嗎?

4_mobile_banner_300x250
photo credit:VI College價值投資學院

本文章內容由「VI College價值投資學院」提供,經關鍵評論網媒體集團廣編企劃編審。


猜你喜歡