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

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

2-7-18 优化假设

对已知条件中的多个量作有序化或最优化（最大、最小、最长、最短）的假定，叫做优化假设，常取“极端”、“限定”、“不妨设”的形式。由于假设本身给题目增加了一个已知条件，求解也就常能变得容易。求解IMO10?4,IMO24?6,IMO29?6都用到这一技巧。

例2-166 空间2n(n?2)个点，任4点不共面，连n?1条线段，证明其中至少有3条边组成一个三角形。

证明 设其中任意三条线段都不能组成三角形，并设从A1点引出的线段最多（优化假设），且这些线段为A1B1，A1B2，?A1Bk，除A1，B1，B2，?，Bk之外，其他点设为A2，A3，?，A2n-k。显然?B1,B2,…,Bk?中任两点间无线段相连。于是，每一个Bi发出的线段至多（2n?k）条，而每个Aj发出的线段至多k条（i?1,2,…,kj?1,2,…,2n?k），故线段总数最多为（图2-65）： 2

1k?(2n?k)2[l(2n?k)?(2n?k)k]?k(2n?k)?[]?n2 22

这与已知条件连n?1条线段矛盾，故存在三条线段组成一个三角形。

例2-167 平面上的有限个圆盘盖住了面积为1的区域S，求证可以从中选出一些互不相交的原盘来，使它们的面积之和不小于21。 9

证明 将圆心为O，半径为r的原盘记为C(o,r)。首先取全体圆盘中面积最大的一个记为

然后在与C(o1,r记为C(o2,r2)，接着在与C(o1,rC(o1,r1)；1)不相交的圆盘中取面积最大的一个，1)，

C(o2,r2)都不相交的圆盘中取面积最大的一个，记为C(o3,r3)，继续这一过程，直到无圆可取为止，设取得的圆盘依次为C(o1,r1)，C(o2,r2)，?，C(on,rn) （1）

则（1）中的圆盘互不相交，且剩下的圆盘均与（1）中的某一圆盘相交。下面证明，（1）中各圆面积之和S1?S2?…?Sn不小于1。 9

o,r)。这个C(o,r)或在（1）中，或与（1）任取x?S，必存在一个已知圆盘C(o,r)，使c?C(

中的圆盘相交，反正必与（1）有重迭部分，现设（1）中与C(o,r)有公共部分的最大圆盘为C(ok,rk)(1?k?n)，因为C(o,r)，C(ok,rk)与C(o1,r1)，C(o2,r2)，?，C(ok?1,rk?1)均不相交，故由C(ok,rk)的取法知r?rk，且由C(o,r)

。这表明S?UC(oi,3ri) x?C(ok,3rk)i?1nC(ok,rk)??知，C(o,r)?Co(k,r3)更有k，

222从而 1??(3r )??(3r)?…??(3r)12n

222 ?9(?r1??r2?…??rn)?9(S1?S2?…?Sn)

得 (S1?S2?…?Sn)?1 9

2-7-19 计算两次

对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理。计算两次可以建立左右两边关系不太明显的恒等式。在反证法中，计算两次又可用来构成矛盾。

例2-168 能否从1，2，?，15中选出10个数填入图2-66的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所的的14个差恰好为1，2，?，14？

解 考虑14个差的和S，一方面S=1+2+?+14=105为奇数。

另一方面，每两个数a,b的差与其和有相同的奇偶性 a?b?a?b(mod2)

因此，14个差的和S的奇偶性与14个相应数之和的和S’的奇偶性相同，由于图中的每一个数a与2个或4个圈中的数相加，对S’的贡献为2a或4a，从而S’为偶数，这与S为奇数矛盾，所以不能按要求给图中的圆圈填数。

例2-169 设a1,a2,…,an为1，2，?，n的一个排列，fk是集合aiai?ak,i?k元素的个数，而gk是集合aiai?ak,i?k元素的个数（k?1,2,…,n），证明?????f??gk

k?1k?1nnk

证明 考虑集合S?(ai,ak)ai?ak,i?k的元素个数S。一方面，固定k先对i求和，然后再对k求和，得S?

nn???fk?1nk；另一方面，固定i先对k求和，然后再对i求和，又得到

S??gi??gk，所以得?fk??gk。

i?1k?1k?1k?1nn

2-7-20 辅助图表

解题中作一些辅助性的图形或表格，常克使问题的逻辑结构直观地显现出来，并提供程序性操作的机会，例3-2的处理曾获冬令营特别奖，同样的方法可用来求和

Sn?12?22?…?n2?n(n?1)(2n?1) 6

例2-170 设N??1,2,…,n?,n?2。N的子集Ai(i?1,2,…,t)组成集合F??A,At?。1,A2,…

如果对于每一对元素x,y?N，有一个集合Ai?F使得Ai则称F是可分的。?x,y?恰含一个元素，

如果N的每一个元素至少属于一个集Ai?F，则称F是覆盖的。问使得有一个F??A,At?1,A2,…既是可分的又是覆盖的t的最小值f(n)是多少？

解 设F??A,At?对于N是既是可分的又是覆盖的，考虑集合与元素的关系表： 1,A2,…

元素 1

集合

A1 A2 ?? At

其中aij??

2

3

?? ?? ?? ?

??

n a1n a2n

?

a11 a21

?

a12 a22

?

a13 a23

?

at1 at2 at3 atn

??1,j?A

1?i?t,1?j?n

??0,i?A

①由于F是覆盖的，所以每个j属于至少一个Ai，即表中每一列中至少有一个1。 ②由于F是可分的，所以表中每两列均不完全相同。

由于表中的t行中，每个元素只取0或1，并且每列的元素不全为0，所以最多可以组成2?1个两两不同的列，由F是可分的（或由②），有

t

n?2t?1?2t t?log2n?[log2n]

得 f(n)?[lo1 （1） 2gn?] 另一方面，取t满足2

t?1

?n?2t?1，即t?[log2n]?1

t

可作出n个不同的由0，1组成的并且不全为0的长为t的数字列，因为n?2?1，这总是可能的，将它们作为一个有t行n列的数字表的n列，再把这个表看作是一些集合A1，A2，?，At与元素1，2，?，n的关系表。即集合Ai由第i行中使得aij?1的哪些j组成，即

Ai?j?j?n且aij?1,1?i?t。

这时，集合F??A,At?对于N既是可分的，又是覆盖的，所以，又有 1,A2,…

??

f(n)?t?[log2n]?1 （2）

由（1）（2）知 f(n)?[log2n]?1

例2-171 六名乒乓球选手进行单打寻坏赛，比赛在3个台上同时进行，每人每周只能而且必须

参加一场比赛，因而比赛需要进行五周，已知，在第一周C与E对垒；第二周B与D对垒；第三周A与C对垒；第四周D与E对垒；各周在上述这些对垒同时另外还有两台比赛，问F在第五周同谁进行了比赛。

解 用表上作业法，列下表，并把已知条件填入第一列，根据题意，填表时应满足

（1）每行填3对字母，恰好出现已知6个字母A，B，C，D，E，F各一次。

（2）每个字母各行出现一次，恰好在全表中出现5次；每次都与不同的字母配对，恰好与其他5个字母各配对一次。

周次 比赛对垒

一 （CE） （AD）4

二 （BD） （CF）2 （AE）3

三 （AC）

四 （DE） （CB）2 （AF）3

五 （F？） （CD）1 （AB）4

①由于比赛对垒的第一列中，前四周或有C或有D，但C、D间未对垒，故C、D必在第五周对垒，记为（CD）1。

②由于已经有（CE），（AC），（CD），故剩下的（CB），（CF）必出现在第二、四周，但第二周B已与D对垒，故第二周应是（CF），记作（CF）2，从而第四周有（CB）2。

③这时第二周必还有（AB）3，第四周必还有（AF）3。

④由于已经有（AC），（AE），（AF），故剩下的（AB）（AD）4，必出现在第一、五行，但（CD）4，

已经有D出现在第五行，故只能（AB）4在第五行，这就表明F与E对垒。