例1 设

1、设n?1?mod4?且n＞1，P??ap1,a2,?,an?是?1,2,3,?,n?的任意

排列，k表示使下列不等式成立的最大下标k，

a1?a2???ak＜ak?1?ak?2???an．

p试对一切可能的不同排列P，求对应的k的总和． 解：设n?4m?1（m为正整数），对于?1,2,3,?,n?的任意排列

P??a1,a2,?,an?，由kp的定义得

kp?1a1?a2???akp＜a?akp?2???an，

① ②

a1?a2???akp?akp?1≥akp?2???an．

首先，②中等号不成立．事实上，若

a1?a2???akp?akp?1?akp?2???an，

则2?a1?a2???akp?1?a1?a2???an?1?2???n??12n?n?1?

??4m?1??2m?1?．

上式左端为偶数，右端为奇数，矛盾．故②应为

a1?a2???akp?1＞akp?2???an

③

n于是，对于P的反序排列P'??akp'?n??kp?1?,an?1,?,a2,a1?，由①，③得

，即kp?kp'?n?1，将?1,2,3,?,n?的n！个排列两两配

p对，每对中的两个排列P与P’互为反序，它的对应的k之和为1?n?1??n!?．

22、给定2003个集合，每个集合都恰含44个元素，并且每两个集合恰有一个公共元．试求这2003个集合的并集中元素的个数．

解：设给定的2003个集合为A,A12,?,A2003．依题意有Ai?44（1≤i≤2003）．

A1?A2???A2003i2＜…＜ikAi?Aj?1（1≤i＜j≤2003）．为了求

i1，由容斥原理，只需求Ai?Ai2???Aik（1≤i＜

1≤2003，k≥3）．由A?Aj?1知这个数至多等于

1，

若都等于1，则必有一个元是所有A的公共元．

i考虑A．它与其他2002个集合A（2≤i≤2003）都有惟

1i一公共元．又A1?442003，且????45??44?，若A中每个元至多属于

1其他45个集合，则A至多与其他44×45＝1980个集合有公

1共元，矛盾．可见A中必有一个元a至少属于其他46个集合，

1不妨设a属于A，A，…，A，并设B是A234748,A49,?,A2003中任意

一个集合，如果a?B，又因为B与A,A12,?A47中每一个都有公

ij共元，且这些公共元两两不同（这时，若B与A及A?1?i?有相同的公共元b，则b?a，于是A与A?1?i?ijj?47?j?47?有两个公

共元a和b，矛盾），可见B至少有47个元，这与B必有a?B，即a是2003个集合A,A12?44矛盾．故

,?A2003的公共元，但

A1,A2,?A2003中任何两个只有惟一公共元a，所以

?．

Ai1?Ai2???Aik?1?1?i1???ik?2003由容斥原理得

A1?A2???A20032003

?1?i?j?k?2003??i?1Ai??1?i?j?2003Ai?Aj?Ai?Aj?Ak???A1?A2???A2003

?2003?44?C2003?C2003???C2003232003

?2003?44?C2003?C2003?C2003?C2003?C2003??C2003?86130??1?1?200301?0122003?

?86130．

3、证明：在任何n个人中，总存在2人，使得其余n?2人

n?中与这两人都互相认识或都不互相认识的人数不少于????1?2?个．

证明：如果结论不成立，那么对n个人中任意两人A和B，其余n?2个人中同时认识A和B以及同时不认识A和B

n?的总人数至多为?个．设除A，B外其余n?2个人中恰认???2?2??n?n?2?k????2?2?识A或B中一人的有

nn?n?k?n????n??22?2?k个，则

，所以

．若C恰认识A、B中一个人，则将（C，

A，B）组成一个三人组，并设这种三人组的个数为S，因为

n个人可形成Cnn2个（A，B）对，并且对每一对人A和B，至

?n2C2n少有个人恰认识A或B中一个，所以S2?n2?n?1?4①．另

一方面，设对n人中任意一人C，其余n?1人中恰有h人认识C而

n?1?h人不认识C，于是含C的三人组有

22?n?1??h?n?1?h?h?n?1?h?????24??S?n?n?1?42个，而C有n种取法，所以

②．①与②矛盾，故命题成立．

从上述例题可以看出，用组合分析方法证明组合问题中的不等式时，就是对题中所涉及的组合结构进行数量上的分

析和比较，从而导出要证的不等式．而有的则先转化成一个图论模型，再按题目要求构造出符合条件的组合结构，然后进行数量上的分析与比较后得出要证的不等式．有的则从结论的反面出发，对组合结构进行数量上的分析和比较后导致矛盾，从而证明了结论成立．有的考虑的“三元组”是一种很有用的组合结构，今后的例题会看到，对恰当的“三元组”进行数量上的分析和比较是解决组合问题的一种有效方法．

4、设n和k是正整数，S是平面内n个点的集合，满足： （1）S中任何三点不共线；

（2）对S中有一个点P，S中至少有k个点与P的距离相等．

求证：k?12?2n．

12证法一 设S??P,Pii,?,Pn?，依题意，对任意Pi?S，存在

以P为中心的圆C，使得C上至少有S中k个点?i?1,2,?,n?．设

iCi上恰有

Si中

ri个点且设

Pi恰在

C1,C2,?,Cn中e个圆上

i?i?1,2,?,n?，于是

e1?e2???en?r1?r2???rn?knik．

j若S中点P同时在两个圆C与C?k组成一个三元组?p为M．

i?j?C上，则将P与C，

ikj;Ck,Cj?，这种三元组的全体构成的集合记

一方面，每两个圆至多有2个交点，至多形成2个三元组，n个圆至多形成2C个三元组，故M2n?2Cn2．

另一方面，因P在e个圆上，可形成C个含P的三元组

ii2eii?i?1,2,?,n?，故

M??C．

2eii?1n综合上述两个方面，并利用哥西不等式得

n2C2n??i?1C2ei1?n2???ei?2?i?1nn?i?1?ei? ?21?1?n?????ei??2?n?i?1???i?1?1?n??n?ei????ei???ei?n?2n?i?1??i?1???nk?k?1?

?12n?kn?kn?n??12，

即k2?k?2?n?1??0，

?1?28n?12?2n∴k?1?1?82?n?1?．

证法二 依题意，以S中的每一点为中心可作n个圆，使每个圆上至少有k个点属于S．

我们称两个端点均属于S的线段为好线段． 一方面，好线段显然共有C条．

2n另一方面，每个圆上至少有C条弦是好线段，n个圆共

2k有nC条弦是好线段，但其中有一些公共弦被重复计算了．由

2kn个圆至多有C条公共弦于每两个圆至多有一条公共弦，（这

2n些公共弦还不一定是好线段），故好线段的条数不少于

nCk?Cn22．

2n综上所述，得到C即k2?nC2k?Cn2．

?k?2?n?1??0，

∴k?1?8n?72?12?2n．

注（1）本题的两种解法都说明了题目中的每一条件是多余的．

（2）在用算二次方法证明题目时，由于选择计算的题不同，常常得到的证明方法不全相同．在本题中显然证法二较证法一简便．但从今后的例题会看到，计算“三元组“是一个有效的方法．

（3）算二次时，如果两方面都是精确结果，综合起来就得到一个等式．如果至少有一个方面采取了估计（即算了量的下界或上界），那么综合起来就得到了一个不等式．

5、在某一次竞赛中，共有a个参赛选手及b个裁判，其中?3且为奇数．设每一位裁判对每一位参赛选手的判决方式只有“通过”或“不通过”．已知任意两个裁判至多对k个参赛选手有相同的判决，证明：k试题）

证明：设a个参赛选手为A,A12a?b?12b．（1998年第38届IMO

,?,Aa,b个裁判为B1,B2,?,Bb，

i若两个裁判Bi,Bj?i?j?对选手A的判决相同，则将?Bk,Bj,Ak?组

成三元组，这种三元组的个数记为S．一方面，由已知条件知对任意一对裁判B元组?B,Biji,Bj?i?j?，至多存在k个选手A组成k个三

j2b,Ak?2，而B，B有C种取法，所以

ijS?k?Cb

①

另一方面，设对选手A有r个裁判对A的判决是“通过”，

kkjtk个裁判对Ak的判决是“不通过”，于是r2k?tk?b，且含Ak的三

元组恰有C2rka?Ctk2rk个．

2∴S???Ck?1?Ctk12?．

?rk?tktk?2而C?122rk?Ctk?22?r2k?12??rk?tk?2??rk?tk??2rktk?

?bk?b?2rktk?．

因r?tk?b且b为奇数，所以

?14rktk??b?1??b?1?4?b2?1?．

故C∴

2rk?Ctk?21?212?12??b?b?2?b?1?b?1?42?4????．

．

S?a?14?b?1?2 ②

由①②，得k?C2b?a?14?b?1?2，

∴ka?b?12b．

6、若任意133个正整数中，至少有799对数互素，证明：其中必存在4个正整数a、b、c、d使得a与b，b与c，

c与d，d与a都互素．

证明：用平面内133个点A，A，…，a表示133个正

12133整数，若两个正整数互素，则对应两点连一线段，并设从A出发的线段有

133idi条?i?1,2,?,133?，于是，由已知条件得

?di?1i?2?799．

若两点A、B都与点C连有线段，则称（A，B）为属于C的点对．于是，分别属于A，A，…，A的点对数的总和

12133为

133M??Ci?12di1?1332???di?2?i?1133?i?12?1??133?di?????di??2????i?1??1332/????1???i?1133?i?1??di??????

?

1?133??133???2?799??2?799?133??di???di?133??2?133?i?12?133??i?1?1?12?133?2?6?133??2?6?133?133??2133133?1322?C1332．

但133个点一共只能组成C个点对，可见上式左端计数有重复，即存在一个点对（A，C）属于不同的两点B和D，即A、C既与B连有线段，又与D连有线段，所以A、B、C、D对应的4个正整数满足a与b，b与c，c与d，d与a都互素．

7、设Z为空间含有n??4?个点的点集，其中任意四点不

?n2?共面，这些点之间连有???1条线段．证明：这些线段必可

?4?构成两个有公共边的三角形（特别n为偶数时，此题为1987年国家集训队选拔考试试题）．

证明：n?4时，Z中共有4个点A、B、C、D，它们之间连有

?42????1?5?4?条线段，故仅有C24?5?1对点之间没有连

线．不妨设C与D没有连线，于是存在两个有公共边的三角形：△ABC与△ABD．

设n?k??4?时，结论成立．考虑n?k?1的情形，这时Z中

??k?1?2?有k?1个点，它们之间连有???1条线段，于是从各点出4????k?1?2?发的线段数之总和为2???2条，其中必有一点4??A，从A

出发的线段数l为最少，于是

AlA???k?1?2???． ?2???2???k?1??4??1?2t当k当k为偶数时，lA?12t12t?1?2t?t?1??2??t?t?12t?1A，所以l?tA?t；

?2t?1为奇数时，lA??2t2?2?t??12t，所以l．去掉A

点以及从A出发的线段后还剩k个点，它们之间所连线段数为

?2?t?t?1??1?t?t?1??m???2t?1?t?t?t?1??1????k2????1?k?2t?4???k????1?k?2t?1??4?2

故由归纳假设知连线段中必存在两个有公共边的三角形，即n?k?1时结论成立，于是命题得证．

8、设?B?n3求证：存在B?YN?是一个n元集合，

，满足：（1）

；（2）若u，v?B，则u?v?B．

分析：先考虑一种特珠情形：若X??1,2,?,3k?1?是连续3k?1个正整数组成的集合，而A??k,k?1,k?2,?,2k?2,2k?1?，则易知

A?k?13X，并且若u，v?A，则u?v?A，且u?v模3k?1的最小

正剩余也不属于A．

对一般的Y??y1,y2,?,yn??N?，若用m表示正整数m模3k?11的最小正剩余，其中3k?1?n且3k?1与yk?y1y2?yn,?yn都互素（例如取

即可），利用上述集合A来构造Y的子集

Bi?i?1,2,3,?3k?1?如下：

Bi?yy?Y且iy?A??．

i利用A的性质易证每个B都满足条件（2），再用算二次方法证明必有某个B满足Bi0i0?n3，从而完成证明．

与

证明：设Y??y1取正整数p?3k?1?n且使p,y2,?yn??N?，

（例如取k?y1y2?yn即可），my1,y2,?,yn都互素表示正整数m模

P的最小正剩余（1?m?p）．令A??k,k?1,k?2,?2k?1?，则易知若x，y?A，则x?故或者

x?y?Ay?A事实上，若x，y?A，则2k?x?y?4k?2，或者1?x?y?4k?2??3k?1??k?1，总有

2k?x?y?3k?1）．

i构造Y的子集B?1?i?3k?1?如下：

Bi?yy?Y且iy?A?1?i?3k?1?．

??则每一个B满足：当u，v?B时，u?v?B．

iii事实上，当u，v?B时，有iui?au?A及iv?av?A，于是

i?u?v??au?av?A，从而u?v?Bi．

下面证明必有某个B满足Bioio?n3．为此作?3k?1??n表格，

其中第i行第j列处的数为

xij??1?若yj?Bi??1?i?3k?1,1?j?n?． ????0?若yj?Bi?ij于是x?1当且仅当iyjj?A．因为p?3k?1与y互素，因此pj的完全剩余系乘y后仍是p的完全剩余系，即y，2y，…，

jj?3k?1?yj是1，2，…，3k?1的一个排列，其中恰有k个数属于

如果n?6，则因为a，a，…a都是②中的数且②中8

126个数之积为28?7?11?13444，它是一个完全平方数，而②中任

意两数之积不是完全平方数，故②中任意6个数之积不为完全平方数，这与已知条件（3）矛盾，所以n?7．

设n?7，则a，a，…，a不能都是2的倍数（否则21277k2，

而28k2，矛盾），但2126k2，故a，a，…，a中恰有6个是2

1277的倍数，即a，a，…，a中恰有一个数不是②中的数．不妨设a不是②中的数，由已知条件（1）知a，a，…，a中

1127必有一个数为7的倍数，也有一个数为11的倍数，还有一个数为13的倍数，结合条件（2）知a，a，…，a中任何

127两个数的最大公约数大于1．又a不为2的倍数，所以a能

11被7×11×13整除．于是由①得a积为2于是

81?7?11?13，又②中所有数之

6444?7?11?136444，故惟一的可能为aa13332?a7?2?7?11?13，

a2a3?a7?2?7?11?13，即②中只有两个数：2和

72×7×11×13不属于a，a，…，a，即{a，a，…，a}＝{2×7，

232372×11，2×13，2×7×11，2×7×13，2×11×13}．

综上可知，所求n的最小值为7，这时{a，a，…，a}

127＝{7×11×13，2×7，2×11，2×13，2×7×11，2×7×13，2×11×13}．

12、设S??1,2,3,4,5,6,7,8,9,10?，A，A，…，A是S的子集，

12k满足

（1）A（2）Ai?5?1?i?k?；

?Aj?2?1?i?j?k?．

i求这样一批子集个数k的最大值．（1994年国家集训队第6次测验试题）

解：作10?k的表格，其中第i行、第j列处的元素为

aij??1?若i?Aj??i?1,2,?,10,j?1,2,?,k?． ????0若i?A?j?于是表中第i行元素之各li?…，A?a表示i属于A，A，

ijk12kj?1中l个集合，而第j列元素之和?aii?110ij?Aj表示集合A中元素个

j数，由已知条件（1）有?ai?110ij?Aj?5，所以

1010ikijk10ijk?li?1???ai?1j?1???aj?1i?1??j?1Aj?5k．

①

若r?Ai?Aj，则将?A,A,r?组成三元组，这种三元组的个

ij数记为S．一方面因r属于A，A，…，A中l个集合，可形

12kr成C个含r的三元组，所以S??C．另一方面，对任意A，

2lr102lrir?1Aj?1?i?j?k?有

Ai?Aj个元属属于A?Ai?Aji?Aj，可形成

Ai?Aj个含

Ai，Aj的三元组，所以S?，于是

1?i?j?k10?Ai?Aj??r?1C2lr1?i?j?k1?102???lr?2?r?1?l?r?r?1?10．

利用①及已知条件（2）和哥西不等式得

k?k?1??2C2k??Ai?Aj1?i?j?k21?1?10?????li??2?10?i?1??10?i?1?li???

?120??5k?2?10?5k???54k?k?2?，

所以k?6．

其次，下列6个集合满足题设条件：

A1??1,2,3,4,5?，A2??1,2,6,7,8?，A3??1,3,6,9,10?， A4??2,4,7,9,10?，A5??3,5,7,8,10?，A6??4,5,6,8,9?．

综上可知，所求k的最大值为6．

13、设凸四边形ABCD的面积为1，求证在它的边上（包括顶点）或内部存在4个点，使得以其中任意3点为顶点的四个三角形的面积都大于1．（1991年全国高中联赛试题）

4证明：如图，考虑四个三角形：△ABC，△BCD，△CDA，△DAB的面积，不妨设S?DAB最小，分下列四种情形讨论：

?DAB（1）S?14，则A，B，C，D四点即为满足题设条件

的四个点．

S（2）

?DAB?14，设G为△BCD的重心，则S13S?BCD?14?BCD?1?S?DAB?34，

故S?BCG?S?CDG?S?DBG?．

故B、C、D、G四点即为满足题设要求的四个点． （3）S于S?ABC?DAB?1434，而其余三个三角形的面积均大于1．由

4?S?BCD?1?S?DAC?，故过A作BC的平行线l必与线段

?ABCCD相交于CD内部一点E（如图）．由于SS?EAB?S?DAB?14?S?DAB?14，故

．又S?EAC?S?DAB?14，S?EBC?S?ABC?14，所以A、B、

C、E四点即为满足题设要求的四个点．

（4）S?DAB?14，其余三个三角

形中还有一个三角形的面积也等于

14．不妨设

S?CDA?14．因为

S?DAB?S?CDA，所以AD∥BC．又

34S?ABC?S?DBC?，故BC?3AD．在AB

AE?14AB上取点E，CD上取点F，使

EF?AD?14，DF?14DC，则

?BC?EBF?AD??32AD?3412BC34，

?12S?ABC?932?14于是S?S?ECF?S?ABF?14，

S?EBC?S?FBC?S?EBF?，故E、B、C、F四点即为满足题设

要求的四点．

注：本题证明中用到了下列一个常用的几何结论：若△ABC，△ABD，△ABE共有底边AB，且C、D、E在一直线上．D介于C与E之间，并且SS?ABC?S?ABD?S?ABE?ABC?S?ABE，则

．

14、平面内有4条直线，其中任意3条不共点，每两条相交于一点，从而每条直线上有3个交点，在此直线上截出2条线段．问所得8条线段的长能否为

（1）1，2，3，4，5，6，7，8？ （2）互不相等的整数？

解（1）如图，所得8条线段的长为1，2，3，4，5，6，7，8，因为三角形中任意

一个边之长大于其余两边之差的绝对值，故在一个非等腰且边长为整数的三解形中，任何一边的长大于1，所以长为1的线段只可能为AB或AF．不妨设AF＝1，由于

1?AF?AC?CF，且AC，CF均为正整数，所以AC＝CF．在

△ACF中，由余弦定理得

cos?C?AC2?FC2?AF22AC?FC?1?AF22AC?FC?1?12AC?FC．

在△BCD中，由余弦定理得

BD2?BC2?CD2?2BC?CDcos?C

?BC2?CD21???2BC?CD?1??

2AC?FC???2BC?CD??DCFCBCAC?DCFC?BC2?CD2．

上式中BCAC为小于1的真分数，而其

余各项均为整数，矛盾．

故不存在满足条件的4条直线，使得截出8条线段的长为1，2，3，4，5，6，7，8．

（2）如图知所截出的8条线段可以为互

不相等的线段，图中这8条线段的长依次为3，4，5，12，16，20，28，32．

15、证明：在边长为1的正方形内，不可能无重叠地放入两个边长大于

23的正三角形．

分析：我们只需证明：在边长为1的正方形内放入一个

边长大于

23的正三角形后，必有正方形内一定点（由对称性

自然会想到应是正方形的中心）落到这个正三角形内．

证明：设边长大于

23的正△ABC

任意放入一个边长为1的正方形DEFG内．设DF与EG的交点为O，则A必在△DOE，△EOF，△FOG及△GOD中某一个三角形的内部或边界上（如图），

不妨设A在△DOE的内部或边界上．作△ABC的高AH，则

AH?32BC?32?23?22?OE?AO．

可见，O，A在BC的同一侧．同理可证O、B在AC的同一侧，O、C在AB的同一侧，这就证明了O必在△ABC内．

因此，如果边长为1的正方形内可以无重叠地放置两个边长大于

23的正三角形，则正方形中心必是这两个正三角形

的公共内点，矛盾．可见，边长为1的正方形内不可能无重叠地放置两上边长大于

23的正三角形．

注：在证明是一定条件的覆盖（或嵌入）不存在时，常用反证法．先假设它存在，然后证明至少有一点没有被盖住（或至少有一点是嵌入的诸图形的公共内点），从而导致矛盾．这种“攻其一点”的方法是解决不能覆盖（或不能无重叠

嵌入）问题的一个有效方法．

16、平面有h?s条直线，其中h条是水平线，另s条直线满足：

（1）它们都不是水平线； （2）它们中任意两条不平行；

（3）h?s条直线中任何3条不共点，且这h?s条直线恰好把平面分成1992个区域．求所用的正整数对（h，．（1992s）年亚太地区数学奥林匹克试题）

解：因为每条直线把平面分成两个区域，设n条直线（其中每两条相交，但任意3条不共点）把平面分成a个区域，

n则

n?1条这样的直线把平面分成的

an?1个区域满足

an?1?an??n?1?，a1?2．

由此推得an?a1???akk?2n?ak?1??2?n?k?2k?1?n?n?1?2．

于是s条直线把平面分成1?1s?s?1?个区域．又h条平行线

2与这s条直线相交时又增加了h?s?1?个区域（即每加一条水平线，增加s?1个区域），所以有

h?s?1??1?12s?s?1??1992，

．

?s?1??2h?s??2?1991?2?11?181对上述不定方程的可能正整数解可列出下表：

s?1 s 2h?s h 2 11 1 10 1991 362 995 176 22 181 21 180 181 22 80 <0 故所求的正整数对?h,s?为（995，1），（176，10），（80，21）．

本文来源：https://www.bwwdw.com/article/g30v.html