數學奧林匹克命題人講座(升級版)：組合問題（簡體書）

楊振寧曾這樣描述過他一生中最漫長的計算：
“我在中國昆明的時候，從碩士論文導師王竹溪先生口中第一次聽到翁薩格 （Ｏｎｓａｇｅｒ）這個名字。２０ 世紀 ３０ 年代，王先生在英國劍橋跟福勒 （Ｒ．Ｈ． Ｆｏｗｌｅｒ）學習有序無序躍遷。１９４４—１９４５年的一天，他告訴我，翁薩格已經找到了二維空間伊辛（Ｉｓｉｎｇ）模型的嚴格解。王先生是一位安靜、保守的人，那天他卻顯得非常興奮。半個世紀後的今天，我仍然能夠記得他告訴我翁薩格的論文時那種仰慕與興奮的口氣。後來我找了那篇論文來細讀，可是始終不明白翁薩格的方法。他似乎總是喜歡計算對易式（Ｃｏｍｍｕｔａｔｏｒ），而從不解釋為什麼要這樣做。
“幾年後，當我在芝加哥大學做研究生時，再次閱讀了翁薩格的論文，並花了大量時間仔細研究，可是又一次毫無進展。
“１９４９年秋天，我成為普林斯頓高等研究院的一員（用今天的名詞即博士 後）。奧本海默（Ｏｐｐｅｎｈｅｉｍｅｒ）為了幫助我應付美國移民局，把我名義上調為佩斯（Ｐａｉｓ）的助理，可是我沒有真正幫佩斯做過什麼事情。那一年高等研究院的所有人員，包括我在內，都在研究場論和基本粒子，統計力學當時並不是一個熱門題目。可是偶然地，在１９４９年１１月裡的一天，通過與魯丁格（Ｌｕｔｔｉｎｇｅｒ）的談 話，我得知一個新的翁薩格考夫曼（Ｋａｕｆｍａｎ）方法極大地簡化了翁薩格的論 文。更重要的是，這新方法建立在許多‘反對換’矩陣的表示論上，而我在學習迪 拉克（Ｄｉｒａｃ）方程時就曾充分了解此表示論。就這樣，我終於明白了翁薩格的方法。我曾描述這件事如何使得我後來在１９５１年計算出磁化（ｍａｇｎｅｔｉｚａｔｉｏｎ），並稱此計算為‘我一生中最漫長的計算’。”
當然，在當代，相當一部分復雜的計算可由電子計算機處理，但這並不意味著計算本身沒什麼研究價值了。人們面臨兩件事情：一是計算的代價，由此產生了計算復雜性和Ｐ-ＮＰ難題；二是計算的藝術，這就是組合學的任務了。前者不會進入奧數領域，而後者恰恰是奧數最為看重的。
人們還是采取這樣的方式，把一個組合問題還原成一個代數或分析問題（對應和估計），就像面對幾何一樣。於是，許多極端復雜的組合細節就可忽略。復雜性是人類而不是個人面臨的困難（比如癌癥、天氣預報等，都是復雜性在困擾人類），但是奧林匹克數學命題考察的是個人能力，所以命題者盡可以避開組合復雜性。也就是說，組合問題必可用整體對應、代數還原或局部處理這幾類方法解決。如果你在做題時遇到非常棘手的困難，毫無思路，那必定是陷入了組合細節的復雜性中，而沒有想到或找到前幾種方法。對於命題者來說，如果所出的組合問題只有組合細節的話，那麼只能用小的數字一一列舉，否則就不應該是學生做的題。尤其是組合數學和初等數論中的問題，題目本身往往具有偽裝性，什麼是不能做的，什麼是研究性質的，什麼是學生的思考題，一下子看不出來。只要稍做改動，就可能由一道常規題變成世界難題了。所以，命題比解題更重要，尤其是對組合與數論的一些雜題而言。

第一講 常規計數方法 /1
1.1 分類法/1
1.2 染色法/20
1.3 運用組合數 / 38
1.4 容斥原理 / 51
1.5 母函數法 / 61
第二講 對應方法/ 70
2.1 集合中的對應 /70
2.2 數列中的對應/ 92
2.3 幾何及雜題中的對應 / 99
第三講 數學歸納法 / 113
第四講 遞推方法/140
4.1 數列遞推 / 140
4.2 幾何及雜題中的遞推 /147
第五講 代數雜題舉隅 /158
第六講 構造方法/ 180
6.1 賦值法/ 180
6.2 構造函數/187
6.3 構造圖 / 200
6.4 模型法/ 215
第七講 幾何雜題舉隅/223
第八講 組合計算/ 250
8.1 求和與算兩次/ 250
8.2 組合恒等式/ 261
第九講 遊戲問題舉隅/272
第十講 操作問題/293
第十一講 比賽問題/303
第十二講 博弈與策略/313
第十三講 極端原理/320
參考答案及提示/ 327