奥林匹克数学的技巧(上)

奥林匹克数学的技巧（上篇）

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

奥林匹克技巧是竞赛数学中一个生动而又活跃的组成部分。

2-7-1 构造

它的基本形式是：以已知条件为原料、以所求结论为方向，构造出一种新的数学形式，使得问题在这种形式下简捷解决。常见的有构造图形，构造方程，构造恒等式，构造函数，构造反例，构造抽屉，构造算法等。

例2-127 一位棋手参加11周（77天）的集训，每天至少下一盘棋，每周至多下12盘棋，证明这棋手必在连续几天内恰好下了21盘棋。

证明：用an表示这位棋手在第1天至第n天（包括第n天在内）所下的总盘数（n 1,2,…77），依题意 1 a1 a2… a77 12 11 132

考虑154个数：

a1,a2,…,a77,a1 21,a2 21, a77 21

又由a77 21 132 21 153 154，即154个数中，每一个取值是从1到153的自然数，因而必有两个数取值相等，由于i j时，ai ai ai 21 aj 21

故只能是ai,aj 21(77 i j 1)满足 ai aj 21

这表明，从i 1天到j天共下了21盘棋。

这个题目构造了一个抽屉原理的解题程序，并具体构造了154个“苹果”与153个“抽屉”，其困难、同时也是精妙之处就在于想到用抽屉原理。

例 2-128 已知x,y,z为正数且xyz(x y z) 1求表达式(x y)(y z)的最最小值。

a x y 解：构造一个△ABC，其中三边长分别为 b y z，则其面积为

c z x

1 另方面(x y)(y z) ab 2 2 sinC

222故知，当且仅当∠C=90°时，取值得最小值2，亦即(x y) (y z) (x z)

如x y(x y z) xz时，(x y)(y z)取最小值2，

z ,1y 时， (x y)(y z) 2。

2-7-2 映射

它的基本形式是RMI原理。

令R表示一组原像的关系结构（或原像系统），其中包含着待确定的原像x，令M表示一种映射，通过它的作用把原像结构R被映成映象关系结构R*，其中自然包含着未知原像x的映象x*。如果有办法把x*确定下来，则通过反演即逆映射I M 1也就相应地把x确定下来。取对数计算、换元、引进坐标系、设计数学模型，构造发生函数等都体现了这种原理。

建立对应来解题，也属于这一技巧。

例2-129 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛， 直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 。

解 设甲、乙两队的队员按出场顺序分别为A1，A2， ，A7和B1，B2， B7。

如果甲方获胜，设Ai获胜的场数是xi，则0 xi 7,1 i7 而且 x1 x2 … x7 7 （*）容易证明以下两点：在甲方获生时，

（i）不同的比赛过程对应着方程（*）的不同非负整数解；

（ii）方程（*）的不同非负整数解对应着不同的比赛过程，例如，解（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故甲方获胜的不同的比赛过程总数是方程（*）的非负整数解的个数C13。

解二 建立下面的对应；

集合 A且这种对应也是一个一一对应。1,A2,…,A7 的任一个7-可重组合对应着一个比赛过程，

例如前述的比赛过程对应的7-可重组合是 A1,A2,A3,A4,A5,A6 所以甲方获胜的不同的比赛过程的

77总数就是集合 A1,A2,…,A7 的7-可重组合的个数C7 7 1 C13。

n

例2-130 设pn(k)表示n个元素中有k个不动点的所有排列的种数。求证 kp(k) n! n

k 0

证明 设S a1,a2,…,an 。对S的每个排列，将它对应向量(e1,e2,…,en)，其中每个ei 0,1 ，当排列中第i个元素不动时，ei 1，否则为0。于是pn(k)中所计数的任一排列所对应的向量都恰有k个分量为1，所以n!个排列所对应的那些向量中取值为1的分量的总数为 kp(k)。 n

k 1n

另一方面，对于每个i，1 i n，使得第i个元素不动的排列共有(n 1)!个，从而相应的n维

向量中，有(n 1)!个向量的第i个分量为1。所以，所有向量的取值为1的分量总数n(n 1)! n!，从而得到 kp(k) n! n

k 1n

例2-131 在圆周上给定2n 1(n 3)个点，从中任选n个点染成黑色。试证一定存在两个黑点，使得以它们为端点的两条弧之一的内部，恰好含有n个给定的点。

证明 若不然，从圆周上任何一个黑点出发，沿任何方向的第n 1个点都是白点，因而，对于每一个黑点，都可得到两个相应的白点。这就定义了一个由所有黑点到白点的对应，因为每个黑点对应于两个白点，故共有2n个白点（包括重复计数）。又因每个白点至多是两个黑点的对应点，故至少有n个不同的白点，这与共有2n 1个点矛盾，故知命题成立。

2-7-3 递推

如果前一件事与后一件事存在确定的关系，那么，就可以从某一（几）个初始条件出发逐步递推，得到任一时刻的结果，用递推的方法解题，与数学归纳法（但不用预知结论），无穷递降法相联系，关键是找出前号命题与后号命题之间的递推关系。

用递推的方法计数时要抓好三个环节：

（1）设某一过程为数列f(n)，求出初始值f(1),f(2)等，取值的个数由第二步递推的需要决定。

（2）找出f(n)与f(n 1)，f(n 2)等之间的递推关系，即建立函数方程。

（3）解函数方程

例2-132 整数1，2， ，n的排列满足：每个数大于它之前的所有的数或者小于它之前的所有的数。试问有多少个这样的排列？

解 通过建立递推关系来计算。设所求的个数为an，则a1 1（1）

对n 1，如果n排在第i位，则它之后的n i个数完全确定，只能是n i,n i 1, ,2，1。而它之前的i 1个数，n i 1,n i 2, ,n 1，有ai 1种排法，令i 1,2, ,n得递推关系。

an 1 a1 … an 2 an 1 (1 a1 … an 2) an 1 an 1 an 1 2an 1 （2）

由（1），（2）得 an 2n 1

例2-133 设n是正整数，An表示用2×1矩形覆盖2 n的方法数；Bn表示由1和2组成的

024m2 n m 2, Cm Cm 1 Cm 2 … Cm2, 各项和为n的数列的个数；且 Cn 1，证明35m 21 3… Cm 2 1n 2m 1 Cm 1 Cm 2 Cm

An Bn Cn

证明 由An,Bn的定义，容易得到 An 1 An An 1,A ,A2 2 Bn 1 Bn B ,B 1,B 21 1n112

又因为C1 1,C2 2，且当n 2m时，

0242m 22m1352m 113Cn Cn 1 Cm Cm 1 Cm 2 … C2m 1 C2m Cm Cm 1 Cm 2 … C2m 1 Cm 1 Cm 2

52m 12m 1 Cm C2 3 … C2mm 1 Cn 1

类似地可证在n 2m 1时也有Cn Cn 1 Cn 1，从而 An , Bn 和 Cn 有相同的递推关系和相同的初始条件，所以An Bn Cn。

IMO22 3,IMO29 6用无穷递降法求解也用到了这一技巧。

2-7-4 区分

当“数学黑箱”过于复杂时，可以分割为若干个小黑箱逐一破译，即把具有共同性质的部分分为一类，形成数学上很有特色的方法——区分情况或分类，不会正确地分类就谈不上掌握数学。

有时候，也可以把一个问题分阶段排成一些小目标系列，使得一旦证明了前面的情况，便可用来证明后面的情况，称为爬坡式程序。比如，解柯西函数方程就是将整数的情况归结为自然数的情况来解决，再将有理数的情况归结为整数的情况来解决，最后是实数的情况归结为有理数的情况来解决。IMO14 2的处理也体现了爬坡式的推理（例2-47）。

区分情况不仅分化了问题的难度，而且分类标准本身又附加了一个已知条件，所以，每一类子问题的解决都大大降低了难度。

例2-134 设凸四边形ABCD的面积为1，求证在它的边上（包括顶点）或内部可以找出4个点，使得以其中任意三点为顶点所构成的4个三角形的面积均大于1/4。

证明 作二级分类

1．当四边形ABCD为平行四边形时，

S ABC S ABD S ACD S BCD 11 24

A，B，C，D即为所求，命题成立。

2．当四边形ABCD不是平行四边形时，则至少有一组对边不平行，设AD与BC不平行，且直线AD与直线BC相交于E，又设D到AB的距离不超过C到AB的距离，过D作AB的平行线交BC于F，然后分两种情况讨论。

1AB，此时可作△EAB的中位线PQ、QG，则 2

111SAGQP SEAB SABCD 即A、G、Q、P为所求。 222

11（2）如图2-53，DF AB，此时可在CD与CF上分别取P、Q，使PQ AB。过Q922

1或P）作QG∥AP交AB于G。为证SAPQG ，连AP交BE于M，过A作AH∥BC交CD延长2（1）如图2-52，DF

线于H。有S PCM S PAH S PAD

S MAB S PCM SABCP S PAD SABCO AABCD

得 S APQG1S 2 MA1S21 ABD2

故A、P、Q、G为所求，

这实际上已证明了一个更强的命题：面积为1的凸四边形一定能嵌入一个面积大于1/2的平行四边形。

例2-135 对内角分别为为30°、60°、90°的三角形的顶点和各边四等分点共12个点，染以红色或蓝色，则必存在同色的三点，以它们为顶点的三角形与原三角形相似。

证明 设△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（蓝）时，由△ABC~△B1BA~△C3B1C~△C3AA3~△A2A3B1~△AA2C2~△C2B2C~△A2AB2知，若结论不成立，则有

B1（蓝）→C3（红）→A3（蓝）→A2（红）→C2（蓝）→B2（红）→A（蓝）。

这与A（红）矛盾。

（2）A（红），B（蓝），C（红）时，由△ABC~△B1AC~△A3BB1~△AC3A3~△C2C3B1~△C2B2C~△A2BB2~△AA2C2知，若结论不成立，则有B1（蓝）→A3（红）→C3（蓝）→C2（红）→B2（蓝）→A2（红）→A（蓝）这与A（红）矛盾。

（3）A（红），B（蓝），C（蓝）时，又分两种情况：

（3）1当B1（红）时，由△ABC~△B2B1A~△B2C2C~△AA2C2~△A2BB2知，若结论不成立，则有B2（蓝）→C2（红）→A2（蓝）→B（红）。这与B（蓝）矛盾。图（2-56）

（3）2当B1（蓝）时，由△ABC~△C3B1C~△C3AA3~△A3BB1知，若结论不成立，则有

C3（红）→A3（蓝）→B（红）与B（蓝）矛盾。（图2-57）

2-7-5 染色

染色是分类的直观表现，在数学竞赛中有大批以染色面目出现的问题，其特点是知识点少，逻辑性强，技巧性强；同时，染色作为一种解题手段也在数学竞赛中广泛使用。下面是一些熟知的结果。

1．在（点）二染色的直线上存在相距1或2的同色两点。

2．在（点）二染色的直线上存在成等差数列的同色三点。

3．在（点）二染色的平面上存在边长为1

。

4．设T1，T2是两个三角形，T1有一边长1，T2

找到一个全等于T1或T2的单色三角形。

5．在（点）三染色的平面上，必有相距为1的两点同色。

6．在（点）三染色的平面上，必存在一个斜边为1的直角三角形，它的三个顶点是全同色的或是全不同色的。

7．在（边）染色的六阶完全图中必有单三角形（三边同色）。

8．在（边）染色的六阶完全图中至少有两个单色三角形。

例2-136 有一个3×7棋盘。用黑、白两种颜色去染棋盘上的方格，每个方格只染一种颜色。证明不论怎样染色，棋盘上的方格组成的矩形中总有这样的矩形，其边与棋盘相应的边平行，而4个角上的方格颜色相同。

证明 称满足条件的矩形为单色矩形。由于棋盘上的3×7=21个方格只染两种颜色，必有11个同色，不妨设同为黑色。现设第i列上有di(0 di 3)个黑色方格，一方面，总黑格数为