說(shuō)說(shuō)羅馬尼亞數(shù)學(xué)賽中國(guó)隊(duì)團(tuán)滅的第三題

前幾天中國(guó)隊(duì)參加羅馬尼亞數(shù)學(xué)競(jìng)賽慘敗的消息小火了一把，尤其是第三題，只有一人得了1分，可謂團(tuán)滅。網(wǎng)上的報(bào)道有些夸張成分，容易造成誤導(dǎo)，好像題目很難，刷題遺漏了，又有大把關(guān)于是否該加強(qiáng)奧數(shù)的討論。是否該加強(qiáng)奧數(shù)，關(guān)系國(guó)家發(fā)展大局，我不敢妄言，只能就事論事，就這倒題本身談?wù)勛约旱囊恍┎怀墒煜敕ā?/p>

早于國(guó)內(nèi)報(bào)道，2月25日中午（美國(guó)時(shí)間），我就在海外論壇上看到有人貼出了“團(tuán)滅”的消息?？戳艘幌路?jǐn)?shù)表，我還發(fā)現(xiàn)了一個(gè)不太為人注意的細(xì)節(jié)，對(duì)各國(guó)選手而言第三題似乎并沒(méi)有那么難，即便是銅牌最后一名，第三題也是滿(mǎn)分。這就有意思了。沒(méi)多久有人貼出了第三題和自己的解題思路，并說(shuō)這是一道送分題，于是我就懶得思考了，直接偷看答案了。看完后我基本同意送分題的觀點(diǎn)。該題如下：

翻譯成中文：

給定任何一個(gè)正實(shí)數(shù)ε，證明除了有限個(gè)正整數(shù)以外的所有正整數(shù)v，任何有v個(gè)頂點(diǎn)且
有大于等于(1+ε)v條邊的圖包含兩個(gè)不同的等長(zhǎng)簡(jiǎn)單回路。（注意簡(jiǎn)單回路中沒(méi)有重復(fù)頂點(diǎn)）

這位大俠的評(píng)論和解題思路如下：

睡前看到這道題，兩三分鐘就做出思路了，寫(xiě)完整證明也用不了10分鐘。
我一說(shuō)思路，多數(shù)都能做出來(lái)吧：
1）這是一個(gè)送分的大水題；
2）這是一個(gè)計(jì)算機(jī)算法題；
3）中國(guó)隊(duì)教練該刷刷Leetcode了

（本人注：Leetcode是個(gè)國(guó)外網(wǎng)站，很多大軟件公司的應(yīng)聘者到這里交流編程與算法）

另一位大俠給出了相似的思路：

這個(gè)題從直觀上來(lái)看很容易接受。頂點(diǎn)數(shù)v大的時(shí)候，1.x倍的邊數(shù)比頂點(diǎn)數(shù)大很多。
一棵樹(shù)，也就是一個(gè)沒(méi)有回路的圖，是邊數(shù)比頂點(diǎn)數(shù)小1。邊數(shù)再多一點(diǎn)，就必須有回
路了。多余的邊數(shù)可以被多回路吸收。但是吸收的速度，要考慮。如果假設(shè)沒(méi)有相同邊
數(shù)的回路，那么回路長(zhǎng)度只能是，3，4，5，等等。這個(gè)吸收多余邊數(shù)的速度，恐怕是
達(dá)不到1.x倍頂點(diǎn)數(shù)的速度。。。
 

標(biāo)準(zhǔn)答案附在本文末尾，跟第二位大俠的思路基本一致?？床欢脑捚鋵?shí)也沒(méi)啥關(guān)系，這里不想具體講解這道題目，只想探討一下這道題帶來(lái)的一些啟發(fā)。簡(jiǎn)單的說(shuō)，這是一道典型又非典型的圖論題。說(shuō)典型，是因?yàn)槠渖婕暗膱D論概念比如生成樹(shù)、回路等，都是常用概念。說(shuō)不典型，是因?yàn)檫@道題引入了正實(shí)數(shù)ε，有限個(gè)正整數(shù)以外的所有正整數(shù)v（即對(duì)于充分大的v）這樣一些數(shù)學(xué)分析中常用的術(shù)語(yǔ)。相信學(xué)過(guò)微積分初步的朋友對(duì)這些都不陌生。

我的感悟大體有兩點(diǎn)。第一，奧數(shù)學(xué)習(xí)不僅要培養(yǎng)數(shù)學(xué)技巧，更重要的是培養(yǎng)數(shù)學(xué)直覺(jué)。

一道難題看似無(wú)從下手，苦苦思索后未果，看了解答后豁然開(kāi)朗，擊節(jié)叫好。很多人到此為止，就轉(zhuǎn)向下一題了，然而最關(guān)鍵的最能提升能力的下一步，卻錯(cuò)過(guò)了。想想解題者怎么想出這種解答方式的，比看懂答案更重要。最終的解答過(guò)程是按照數(shù)學(xué)邏輯加工后的整理版，而解題者在腦海中和草稿紙上的思考演算過(guò)程，才具有更大的學(xué)習(xí)價(jià)值。一般而言，解題高手在對(duì)數(shù)學(xué)理論的學(xué)習(xí)后形成了自己的心得體會(huì)，并將數(shù)學(xué)元素在腦海中重新建模，形成清晰可見(jiàn)的“數(shù)學(xué)實(shí)體”。有了這個(gè)一般性通用性的“數(shù)學(xué)實(shí)體”后，就可以以不變應(yīng)萬(wàn)變了，解題過(guò)程中依靠對(duì)這種實(shí)體的觀測(cè)與想象進(jìn)行直觀推理，然后把推理過(guò)程用數(shù)學(xué)語(yǔ)言精確描述出來(lái)。比如用微積分解題時(shí)，在腦海中浮現(xiàn)一個(gè)微小單位的幾何結(jié)構(gòu)，長(zhǎng)度角度都能想象出來(lái)，這樣可以組合成一個(gè)無(wú)窮小量，然后加上積分符號(hào)，得出一個(gè)積分表達(dá)式進(jìn)行運(yùn)算。這種解題過(guò)程可以依靠直覺(jué)，大大降低了思考的復(fù)雜度，提高了驗(yàn)算的準(zhǔn)確度，其實(shí)質(zhì)是利用人類(lèi)在生活中無(wú)處不在的空間概念，利用大自然這臺(tái)精確的計(jì)算機(jī)輔助我們解題。很多數(shù)學(xué)家留下的手稿大有研究?jī)r(jià)值，也是出于這個(gè)道理。

回到這道題，腦海中浮現(xiàn)出出生成樹(shù)的樣子，生成樹(shù)的邊加粗顯示，其他的多余的邊與生成樹(shù)構(gòu)成回路，這樣就能很自然的像那位大俠一樣意識(shí)到，在頂點(diǎn)數(shù)線性增長(zhǎng)時(shí)，題目限制了邊數(shù)線性增長(zhǎng)，而只要能證明回路數(shù)的增長(zhǎng)速度大于線性，那自然在頂點(diǎn)數(shù)足夠大時(shí)結(jié)論成立。有了這樣的想法，細(xì)節(jié)即便不能完全搞清楚，但7分中得個(gè)3到4分還是很容易的。只得1分，甚至0分，表明完全沒(méi)有思路，這說(shuō)明在學(xué)習(xí)圖論生成樹(shù)理論時(shí)沒(méi)有深入思考為什么要研究生成樹(shù)，生成樹(shù)作為樹(shù)的骨干有何特殊意義，而只是為了應(yīng)付題目記住了一些知識(shí)點(diǎn)和技巧，比如Kruskal最小生成樹(shù)算法。這也是“學(xué)而不思”的一種體現(xiàn)。

這道題的增長(zhǎng)速率分析，實(shí)際上跟數(shù)學(xué)應(yīng)用中的估算、量綱分析也很類(lèi)似。ε的具體值無(wú)關(guān)緊要，只要能做定性判斷即可，具體的上下界分析可以在以后研究。這也是大俠說(shuō)這道題其實(shí)是個(gè)送分題的理由之一。這種估算的能力在開(kāi)放性問(wèn)題研究時(shí)非常實(shí)用，可以幫助我們迅速剔除調(diào)明顯不對(duì)的結(jié)論，縮小研究范圍，更快找到正確結(jié)論。這種直覺(jué)能力，類(lèi)似于你聽(tīng)到一艘航母排水量只有一千噸，會(huì)立即憑本能就覺(jué)得不對(duì)。

再比如一道老題，在2N×2N的棋盤(pán)上放上3N個(gè)棋子，證明必然可以選出N行與N列，使得這些棋子全都在這N行與N列中。一種直觀的思考方式是，注意到3N的這個(gè)系數(shù)3必然有其意義，意識(shí)到2N個(gè)棋子可能太少，結(jié)論太容易證明，4N個(gè)棋子可能太多，結(jié)論不成立，那么3有何特殊意義呢？再注意到2N×2N可以分成4塊N×N的子棋盤(pán)，其中3塊形成L形，正好是N行與N列，直覺(jué)上這個(gè)3與那個(gè)3形成聯(lián)系，每個(gè)N×N子棋盤(pán)上平均放置N個(gè)棋子。于是很快就會(huì)發(fā)現(xiàn)對(duì)2N行按棋子數(shù)排序，選出包含棋子最多的那N行，然后分析剩下的棋子數(shù)，很容易證明都可以放進(jìn)N列。

數(shù)學(xué)家不僅把數(shù)學(xué)直覺(jué)停留在草稿紙上，而且直接應(yīng)用到了數(shù)學(xué)理論的表述中。最典型的例子是數(shù)學(xué)分析中“空間”概念的引入。本來(lái)這個(gè)概念是數(shù)學(xué)家用生活中的空間常識(shí)來(lái)輔助思考，后來(lái)他們發(fā)現(xiàn)直接用這個(gè)概念來(lái)進(jìn)行描述和推演非常方便，而為了追求抽象性一般性而刻意回避這個(gè)概念反而不自然，于是干脆定義了函數(shù)空間，將幾何概念引入代數(shù)。

一個(gè)好的老師比書(shū)本更有價(jià)值，其中一點(diǎn)就在于他可以面對(duì)面的把自己的數(shù)學(xué)直覺(jué)傳授給學(xué)生，而書(shū)本篇幅終究有限，寫(xiě)書(shū)的人很難把自己的想法完整記錄成文字。

良好的數(shù)學(xué)直覺(jué)一旦形成即不會(huì)再遺忘，腦海中對(duì)數(shù)學(xué)形體的直觀化思維，是一個(gè)人數(shù)學(xué)知識(shí)的最核心部分，終生不會(huì)丟失，就像學(xué)會(huì)騎車(chē)一樣。如果若干年后你再?gòu)?fù)習(xí)，發(fā)現(xiàn)一點(diǎn)印象都沒(méi)有，那說(shuō)明你當(dāng)年學(xué)習(xí)沒(méi)有建立起這種牢固內(nèi)核。

能否培養(yǎng)并形成清晰的數(shù)學(xué)直覺(jué)，也可以作為是否有奧數(shù)潛力的自我鑒定方式。

第二點(diǎn)感悟，更高效的奧數(shù)學(xué)習(xí)者，還要想到更深一步：出題者是怎么想出這道題的？出題者為什么要出這道題？

僅僅就這道題而言，我分析大致是這幾點(diǎn)。第一，出題者盡量避免題目需要依賴(lài)圖論中的某些定理與結(jié)論，因?yàn)檫@樣不是考察能力而是考察刷題。第二，數(shù)學(xué)競(jìng)賽的題目越來(lái)越偏向于應(yīng)用化實(shí)用化，尤其是在當(dāng)前計(jì)算機(jī)科學(xué)熱門(mén)的背景下。第三，出題者盡量避免出“要么零分要么滿(mǎn)分”的題目，一道題即便做不出來(lái)也有機(jī)會(huì)得部分分?jǐn)?shù)，從而給選手更多展示自己的機(jī)會(huì)，也有利于在分?jǐn)?shù)上造成區(qū)分度。第三，出題者為了增大難度，沒(méi)有用ε=1或某個(gè)特定值出題，而是用了個(gè)一般形式，這就加深了對(duì)增長(zhǎng)速率這個(gè)數(shù)學(xué)概念的考察程度。

“要么零分要么滿(mǎn)分”的題目，比如這道：在19×19路圍棋盤(pán)交叉點(diǎn)上放滿(mǎn)黑白棋子，其中左上右下2個(gè)角頂點(diǎn)是黑子，右上左下2個(gè)角頂點(diǎn)是白子；現(xiàn)考察這18×18（324）個(gè)棋盤(pán)小方塊，每個(gè)方塊4個(gè)頂點(diǎn)，求證4個(gè)頂點(diǎn)中黑子為奇數(shù)個(gè)（1個(gè)或3個(gè)）的小方塊數(shù)是偶數(shù)。這道題見(jiàn)過(guò)或?qū)W習(xí)過(guò)染色理論的可以秒解，給黑子賦值1，白子賦值-1，求所有方塊4個(gè)頂點(diǎn)的乘積，注意到邊上的每個(gè)點(diǎn)算了兩次，中間的每個(gè)點(diǎn)算了四次，馬上得出證明，三分鐘寫(xiě)完解答。不會(huì)的話想破頭皮也想不出來(lái)。這就是“要么零分要么滿(mǎn)分”。應(yīng)該說(shuō)這種類(lèi)型的題目在高層的數(shù)學(xué)競(jìng)賽中越來(lái)越不受青睞，而在底層奧數(shù)培訓(xùn)中往往還很多見(jiàn)，有一定的誤導(dǎo)性 。

出題者本身都是精通高等數(shù)學(xué)的專(zhuān)家，在出高中競(jìng)賽題時(shí)，他們反而面臨許多約束。認(rèn)識(shí)到這一點(diǎn)，可以使得解題者充滿(mǎn)必勝信心。一個(gè)出題思路是從初等數(shù)學(xué)超出課本的范疇去出題。比如歐式幾何在近代仍有發(fā)展，有很多復(fù)雜的結(jié)論，遠(yuǎn)超課本教學(xué)范疇，比如《近代歐式幾何學(xué)》（https://book.douban.com/subject/1551510/）。另一個(gè)方向是從高等數(shù)學(xué)內(nèi)容中抽取可以用初等數(shù)學(xué)知識(shí)解答的特例，比如遞推方程式的求解，有一整套完整的理論，比如齊次非其次，其中某些特殊形式可以用初高中知識(shí)解答。第三個(gè)方向是不同數(shù)學(xué)領(lǐng)域交叉，這類(lèi)的在應(yīng)用數(shù)學(xué)類(lèi)的雜志上有很多有趣問(wèn)題研究，羅馬尼亞這第三題就是一例。還有些別的出題方式，超出我的想象能力了，因?yàn)槲耶吘共皇浅鲱}者，只能從看到的題目去揣測(cè)。

對(duì)每道奧賽題目，在完全弄清楚解答過(guò)程，思考了如何得出這個(gè)解答過(guò)程后，有機(jī)會(huì)的話，想想這道題涉及哪些基本知識(shí)點(diǎn)？出題人是怎么從基本題目組合變形得出這道題目的？題目中的重要參數(shù)能不能改變？改變后題目是否還成立？如果不成立，結(jié)論能否修改后成立？（比如上面圍棋子的題目，4個(gè)角頂點(diǎn)只要黑子正好偶數(shù)個(gè)包括0個(gè)，結(jié)論都成立，而 4個(gè)角頂點(diǎn)的黑子如果正好奇數(shù)個(gè)，則待證結(jié)論只需改成奇數(shù)個(gè)即可。）題目中的具體參數(shù)，能否一般化（比如羅馬尼亞這道題就對(duì)ε進(jìn)行了一般化）？這樣的學(xué)習(xí)，就是舉一反三的過(guò)程，充分利用了每一道題目，不僅獲得了技能，也提升了能力。只看刷題的數(shù)量，是不行的。

以上是自己的一點(diǎn)不成熟想法，僅供參考。畢竟不是專(zhuān)業(yè)的奧數(shù)培訓(xùn)人員，只能管中窺豹。

為了內(nèi)容的完整性，最后附上第三題的標(biāo)準(zhǔn)解答。

歸巢鳥(niǎo)文