数学奥林匹克命题人讲座（升级版）：组合问题

本套丛书不同于一般的堆砌大量难题的数学奥林匹克教材，而是力求做到既深入浅出，又具备很大的实用性，完整地体现各专题的思想方法，探索解题的一般规律，并注重对学生兴趣和能力的培养。

本书是“数学奥林匹克命题人讲座”（升级版）中的一本，主要讲述组合问题的内容。各章节从高考难题、全国联赛一试试题的难度入手，充分考虑了参加数学竞赛的高中学生的实际需要。
升级版书稿保留了版中具有典型性的问题，在此基础上删减了部分老题目，并将近年来的高校自招、全国联赛、冬令营、IMO、中国女子数学奥林匹克、中国西部数学邀请赛及国外的数学竞赛中的新题好题充实进来，既有一定的新鲜度，又充分考虑到合理性。

刘培杰  哈尔滨工业大学出版社编审 。从1985年开始从事数学奥林匹克培训、命题及研究工作。在几十年的教学中共培训学生近万人次，多人次获奖，其中获IMO金牌两块。多次为竞赛活动命题，包括全国初中数学联赛及希望杯竞赛，多年来一直是黑龙江省初高中及哈尔滨市竞赛命题组成员。共发表数学竞赛方面论文60余篇，出版有关竞赛方面的研究专著近10部。

讲 常规计数方法 /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

杨振宁曾这样描述过他一生中漫长的计算： 
“我在中国昆明的时候，从硕士论文导师王竹溪先生口中次听到翁萨格 （Ｏｎｓａｇｅｒ）这个名字。２０ 世纪 ３０ 年代，王先生在英国剑桥跟福勒 （Ｒ．Ｈ． Ｆｏｗｌｅｒ）学习有序无序跃迁。１９４４—１９４５年的一天，他告诉我，翁萨格已经找到了二维空间伊辛（Ｉｓｉｎｇ）模型的严格解。王先生是一位安静、保守的人，那天他却显得非常兴奋。半个世纪后的今天，我仍然能够记得他告诉我翁萨格的论文时那种仰慕与兴奋的口气。后来我找了那篇论文来细读，可是始终不明白翁萨格的方法。他似乎总是喜欢计算对易式（Ｃｏｍｍｕｔａｔｏｒ），而从不解释为什么要这样做。
“几年后，当我在芝加哥大学做研究生时，再次阅读了翁萨格的论文，并花了大量时间仔细研究，可是又一次毫无进展。 
“１９４９年秋天，我成为普林斯顿高等研究院的一员（用今天的名词即博士 后）。奥本海默（Ｏｐｐｅｎｈｅｉｍｅｒ）为了帮助我应付美国移民局，把我名义上调为佩斯（Ｐａｉｓ）的助理，可是我没有真正帮佩斯做过什么事情。那一年高等研究院的所有人员，包括我在内，都在研究场论和基本粒子，统计力学当时并不是一个热门题目。可是偶然地，在１９４９年１１月里的一天，通过与鲁丁格（Ｌｕｔｔｉｎｇｅｒ）的谈 话，我得知一个新的翁萨格考夫曼（Ｋａｕｆｍａｎ）方法极大地简化了翁萨格的论 文。更重要的是，这新方法建立在许多‘反对换’矩阵的表示论上，而我在学习迪 拉克（Ｄｉｒａｃ）方程时就曾充分了解此表示论。就这样，我终于明白了翁萨格的方法。我曾描述这件事如何使得我后来在１９５１年计算出磁化（ｍａｇｎｅｔｉｚａｔｉｏｎ），并称此计算为‘我一生中漫长的计算’。” 
当然，在当代，相当一部分复杂的计算可由电子计算机处理，但这并不意味着计算本身没什么研究价值了。人们面临两件事情：一是计算的代价，由此产生了计算复杂性和Ｐ-ＮＰ难题；二是计算的艺术，这就是组合学的任务了。前者不会进入奥数领域，而后者恰恰是奥数为看重的。
人们还是采取这样的方式，把一个组合问题还原成一个代数或分析问题（对应和估计），就像面对几何一样。于是，许多复杂的组合细节就可忽略。复杂性是人类而不是个人面临的困难（比如癌症、天气预报等，都是复杂性在困扰人类），但是奥林匹克数学命题考察的是个人能力，所以命题者尽可以避开组合复杂性。也就是说，组合问题必可用整体对应、代数还原或局部处理这几类方法解决。如果你在做题时遇到非常棘手的困难，毫无思路，那必定是陷入了组合细节的复杂性中，而没有想到或找到前几种方法。对于命题者来说，如果所出的组合问题只有组合细节的话，那么只能用小的数字一一列举，否则就不应该是学生做的题。尤其是组合数学和初等数论中的问题，题目本身往往具有伪装性，什么是不能做的，什么是研究性质的，什么是学生的思考题，一下子看不出来。只要稍做改动，就可能由一道常规题变成世界难题了。所以，命题比解题更重要，尤其是对组合与数论的一些杂题而言。

命题人写书，富于原创性，且因为充分了解问题的背景，写来能够深入浅出，“百炼钢化为绕指柔”。