奥林匹克数学的解题方法

《奥林匹克数学的解题方法》由会员分享，可在线阅读，更多相关《奥林匹克数学的解题方法（24页珍藏版）》请在金锄头文库上搜索。

1、奥林匹克数学的解题方法（上篇）有固定求解模式的问题不属于奥林匹克数学，通常的情况是，在一般思维规律的指导下，灵活 运用数学基础知识去进行探索与尝试、选择与组合。这当中，经常使用一些方法和原理（如探索法， 构造法，反证法，数学归纳法，以及抽屉原理，极端原理，容斥原理） ，同时，也积累了一批 生气勃勃、饶有趣味的奥林匹克技巧。在 2-1 曾经说过：“竞赛的技巧不是低层次的一招一式或妙 手偶得的雕虫小技，它既是使用数学技巧的技巧，又是创造数学技巧的技巧，更确切点说，这是一 种数学创造力，一种高思维层次，高智力水平的艺术，一种独立于史诗、音乐、绘画的数学美。 ” 奥林匹克技巧是竞赛数学中一个生动而又活

2、跃的组成部分。 2-7-1 构造 它的基本形式是：以已知条件为原料、以所求结论为方向，构造出一种新的数学形式，使得问 题在这种形式下简捷解决。常见的有构造图形，构造方程，构造恒等式，构造函数，构造反例，构 造抽屉，构造算法等。 例 2-127 一位棋手参加 11 周（77 天）的集训，每天至少下一盘棋，每周至多下 12 盘棋， 证明这棋手必在连续几天内恰好下了 21 盘棋。证明：用表示这位棋手在第 1 天至第天（包括第天在内）所下的总盘数（nann） ，依题意 1,2,77n 1277112 11132aaa考虑 154 个数：12771277,21,21,21a aaaaa , ,又由，即

3、154 个数中，每一个取值是从 1 到 153 的自然数，因7721 13221153154a而必有两个数取值相等，由于时， ijiiaa2121ijaa故只能是满足 ,21(771)ija aij 21ijaa这表明，从天到天共下了 21 盘棋。1ij这个题目构造了一个抽屉原理的解题程序，并具体构造了 154 个“苹果”与 153 个“抽屉” ， 其困难、同时也是精妙之处就在于想到用抽屉原理。例 2-128 已知为正数且求表达式的最最小值。, ,x y z()1xyz xyz()()xyyz解：构造一个ABC，其中三边长分别为，则其面积为axy byz czx ( ()()()()1p pa

4、pbpcxyz xyz 另方面2()()2sinxyyzabC故知，当且仅当C=90时，取值得最小值 2，亦即222()()()xyyzxz时，取最小值 2，如时，()y xyzxz()()xyyz1,21xzy。()()2xyyz2-7-2 映射 它的基本形式是 RMI 原理。令 R 表示一组原像的关系结构（或原像系统） ，其中包含着待确定的原像，令表示一种xM映射，通过它的作用把原像结构 R 被映成映象关系结构 R*，其中自然包含着未知原像的映象。x*x如果有办法把确定下来，则通过反演即逆映射也就相应地把确定下来。取对数计算、*x1IMx换元、引进坐标系、设计数学模型，构造发生函数等都体现

5、了这种原理。 建立对应来解题，也属于这一技巧。 例 2-129 甲乙两队各出 7 名队员按事先排好的顺序出场参加围棋擂台赛，双方先由 1 号队员 比赛，负者被淘汰，胜者再与负方 2 号队员比赛，直到有一方队员全被淘汰为止，另一方获得胜 利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 。 解 设甲、乙两队的队员按出场顺序分别为 A1，A2，A7和 B1，B2，B7。如果甲方获胜，设获胜的场数是，则而且 iAix07,17ixi 1277xxx（*）容易证明以下两点：在甲方获生时， （i）不同的比赛过程对应着方程（*）的不同非负整数解； （ii）方程（*）的不同非负整数解对应着不同的比赛

6、过程，例如，解 （2，0，0，1，3，1，0）对应的比赛过程为：A1胜 B1和 B2，B3胜 A1，A2和 A3，A4胜 B3后负于 B4，A5胜 B4，B5和 B6但负于 B7，最后 A6胜 B7结束比赛。故甲方获胜的不同的比赛过程总数是方程（*）的非负整数解的个数。7 13C解二 建立下面的对应；集合的任一个 7-可重组合对应着一个比赛过程，且这种对应也是一个一一对应。127,A AA ,例如前述的比赛过程对应的 7-可重组合是所以甲方获胜的不同的比赛过程的123456,A A A A A A总数就是集合的 7-可重组合的个数。127,A AA ,77 7 7 113CC 例 2-130

7、设表示个元素中有个不动点的所有排列的种数。求证( )np knk0( )!nn kkp kn证明 设。对 S 的每个排列，将它对应向量，其中每个12,nSa aa12( ,)ne ee ,，当排列中第 个元素不动时，否则为 0。于是中所计数的任一排列所对 0,1ie i1ie ( )np k应的向量都恰有个分量为 1，所以个排列所对应的那些向量中取值为 1 的分量的总数为k!n。1( )nn kkp k另一方面，对于每个 ，使得第 个元素不动的排列共有个，从而相应的i1in i(1)!n维向量中，有个向量的第 个分量为 1。所以，所有向量的取值为 1 的分量总数n(1)!ni，从而得到(1)!

8、n nn1( )!nn kkp kn例 2-131 在圆周上给定个点，从中任选个点染成黑色。试证一定存在两个黑21(3)nnn点，使得以它们为端点的两条弧之一的内部，恰好含有个给定的点。n证明 若不然，从圆周上任何一个黑点出发，沿任何方向的第个点都是白点，因而，1n 对于每一个黑点，都可得到两个相应的白点。这就定义了一个由所有黑点到白点的对应，因为每个黑点对应于两个白点，故共有个白点（包括重复计数） 。又因每个白点至多是两个黑点的对应点，2n 故至少有个不同的白点，这与共有个点矛盾，故知命题成立。n21n 2-7-3 递推 如果前一件事与后一件事存在确定的关系，那么，就可以从某一（几）个初始条

9、件出发逐步递 推，得到任一时刻的结果，用递推的方法解题，与数学归纳法（但不用预知结论） ，无穷递降法相 联系，关键是找出前号命题与后号命题之间的递推关系。 用递推的方法计数时要抓好三个环节：（1）设某一过程为数列，求出初始值等，取值的个数由第二步递推的需要决( )f n(1),(2)ff定。（2）找出与，等之间的递推关系，即建立函数方程。( )f n(1)f n(2)f n（3）解函数方程 例 2-132 整数 1，2，n 的排列满足：每个数大于它之前的所有的数或者小于它之前的所 有的数。试问有多少个这样的排列？解 通过建立递推关系来计算。设所求的个数为，则（1）na11a 对，如果排在第 位

10、，则它之后的个数完全确定，只能是,2，1。1n nini,1,ni ni 而它之前的个数，,，有种排法，令,得递推关系。1i1,2,nini 1n1ia1,2,i n（2）1211211111(1)2nnnnnnnnaaaaaaaaaa 由（1） ， （2）得 12nna例 2-133 设是正整数，表示用 21 矩形覆盖的方法数；表示由 1 和 2 组成的nnA2 nnB各项和为的数列的个数；且 ，证明n0242 12213521 12321, 2 , 21m mmmm nm mmmmCCCCnmCCCCCnm nnnABC证明 由的定义，容易得到 ,nnA B1112,1,2nnnAAAAA

11、1112,1,2nnnBBBBB又因为，且当时，121,2CC2nm0242221352113 112212122112mmm nnmmmmmmmmmmmCCCCCCCCCCCCC 52121 32211mm mmmnCCCC 类似地可证在时也有，从而和有相同的递推关系21nm11nnnCCC ,nnAB nC和相同的初始条件，所以。nnnABC用无穷递降法求解也用到了这一技巧。22 329 6,IMOIMO2-7-4 区分 当“数学黑箱”过于复杂时，可以分割为若干个小黑箱逐一破译，即把具有共同性质的部分分 为一类，形成数学上很有特色的方法区分情况或分类，不会正确地分类就谈不上掌握数学。 有时

12、候，也可以把一个问题分阶段排成一些小目标系列，使得一旦证明了前面的情况，便可用 来证明后面的情况，称为爬坡式程序。比如，解柯西函数方程就是将整数的情况归结为自然数的情 况来解决，再将有理数的情况归结为整数的情况来解决，最后是实数的情况归结为有理数的情况来解决。的处理也体现了爬坡式的推理（例 2-47） 。14 2IMO区分情况不仅分化了问题的难度，而且分类标准本身又附加了一个已知条件，所以，每一类子 问题的解决都大大降低了难度。 例 2-134 设凸四边形 ABCD 的面积为 1，求证在它的边上（包括顶点）或内部可以找出 4 个 点，使得以其中任意三点为顶点所构成的 4 个三角形的面积均大于

13、1/4。 证明 作二级分类 1当四边形 ABCD 为平行四边形时， 11 24ABCABDACDBCDSSSSA，B，C，D 即为所求，命题成立。 2当四边形 ABCD 不是平行四边形时，则至少有一组对边不平行，设 AD 与 BC 不平行，且 直线 AD 与直线 BC 相交于 E，又设 D 到 AB 的距离不超过 C 到 AB 的距离，过 D 作 AB 的平行线 交 BC 于 F，然后分两种情况讨论。（1）如图 2-52，此时可作EAB 的中位线 PQ、QG，则1 2DFAB即 A、G、Q、P 为所求。111 222AGQPEABABCDSSSYV（2）如图 2-53，此时可在 CD 与 CF

14、 上分别取 P、Q，使。过 Q91 2DFAB1 2PQAB或 P）作 QGAP 交 AB 于 G。为证，连 AP 交 BE 于 M，过 A 作 AHBC 交 CD 延1 2APQGSY长线于 H。有PCMPAHPADSSSMABPCMABCPPADABCOABCDSSSSSA得 111 222APQGMABABCDSSSY故 A、P、Q、G 为所求， 这实际上已证明了一个更强的命题：面积为 1 的凸四边形一定能嵌入一个面积大于 1/2 的平行 四边形。 例 2-135 对内角分别为为 30、60、90的三角形的顶点和各边四等分点共 12 个点，染 以红色或蓝色，则必存在同色的三点，以它们为顶

15、点的三角形与原三角形相似。 证明 设ABC 中，C=90，B=60，C=30，点 A1，A2，A3；B1，B2，B3；C1，C2，C3分别是边 AB、BC、CA 的四等分点，下面作三级分类。 1点 A、B、C 同色时，结论显然成立。 2点 A、B、C 异色时，记 A 为红色，写作 A（红） ，其余各点染色记号类同。 （1）A（红） ，B（红） ，C（蓝）时，由ABCB1BAC3B1CC3AA3A2A3B1AA2C2C2B2CA2AB2知，若结论不成立，则有 B1（蓝）C3（红）A3（蓝）A2（红）C2（蓝）B2（红）A（蓝） 。 这与 A（红）矛盾。 （2）A（红） ，B（蓝） ，C（红）时，由ABCB1ACA3BB1AC3A3C2C3B1C2B2CA2BB2