组合数学的一般方法

2023年12月9日发(作者：在线数学试卷批改)

组合数学的一般方法

1、枚举法

所谓枚举法，就是把要计数的集合M中的元素逐一列举出来，不重复不遗漏，从而计算出M中的元素的个数。在枚举的过程中，常常要适当地分类和分步枚举，这就要用到加法原理与乘法原理以及记数的基本公式。

例1-1 方程2x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=3的非负整数解共有

组

（1985年全国高中联赛题）

解

0≤2x1≤3且x1为非负整数，x1=0或1，下面分两种情形。

（1）若x1=1，则必有某xi=1（2≤i≤10），其余xj=0（j≠1，i），这样的1解有C9=9组。

（2）若x1=0，则又分为三种情形。

1（i）有某一个xi=3（2≤i≤10），其余xj=0（j≠1，i），这样的解有C9=9组。

（ii）有某一个xi=2（2≤i≤10），则必还有一个xj=1（j≠1，，其余xk=0i）11C8（k≠1，i，j），这样的解有C9=72组。

（iii）所有xi≠2或3（2≤i≤10），则x2，x3，x4，x5，x6，x7，x8，x9，x10中必有3个等于1，其余6个等于0，这样的解有C93=84组。

于是，原方程共有9+9+72+84=174组。

例1-2 将一个四棱锥的每一个顶点染上一种颜色，并使同一棱的两端点异色，如果只有5种颜色可供使用，那么不同的染色方法总数是 。

（1995年全国高中联赛题）

解 依题意，四棱锥SABCD的顶点S，A，B互不同色，题目有P53=60种染色方法。

当S，A，B的颜色染好后，不妨设其颜色分别为1色，2色，3色，则C只可染2，4，5色中的一色。

1（1）若C染2色，则D可染3，4，5色中的一色，有C3=3种方法。

1（2）若C染4色，则D可染3，5色中的一色，有C2=2种方法。

1 1（3）若C染5色，则D可染2，4色中的一色，有C2=2种方法。

故总的染色方法为60（3+2+2）=420种。

2、映射方法

定义 设f是从集合M到集合N的映射。若对任意x1，x2M，当x1≠x2时有f（x1）≠f（x2），则称f为M到N的单射；若对任意的yN，存在xM，使得f（x）=y，则称f为M到N的满射；若f既是单射又是满射，则称f为M到N的双射，又称f为M与N之间的一一映射。

定理1 对于两个有限集合M与，若存在从M到N的单射，则|M|≤|N|；若存在从M到N的满射，则|M|≥|N|；若存在从M到N的双射，则|M|=|N|。

当计算有限集合M中的元素个数比较困难时，我们设法建立M到另一个有限集合N上的双射，如果N中的元素个数|N|容易算出，于是由|M|=|N|，得出M中的元素个数，这种计数方法称为映射方法，或者称为配对法。

例2-1 设凸n边形的任意3条对角线不相交于形内一点，求它的对角线在形内的交点总数。

解 依题意，一个交点P由两条对角线l与m相交而得，反之，两条相交的对角线l与m，确定一个交点P，而P与（l，m）可建立一一对应。

又因两条相交的对角线l与m分别由凸n边形中两对顶点A，B和C，D连接而成，故（l，m）又可与4顶点组（A，B，C，D）建立一一对应，即有

P

（l，m）（A，B，C，D）

因此，形内对角线的交点总数=凸n边形的4顶点组的组数=Cn4。

例2-2 8个女孩，25个男孩围成一个圆周，每两个女孩之间至少站有2个男孩，共有 种不同的排列方法。（只把圆旋转一下就重合的排法认为是相同的）

（1990年全国高中联赛题）

解 以8个女孩为组长，将25个男孩分入该8个组，各组内男孩数记为x1，x2，x3，x4，x5，x6，x7，x8，则x1+x2+…+x8=25（xi2,i1,2,,8）①

令yi=xi-2，则y1+y2+…+y8=9（Yi0,i1,2,,8）②

781C于是，①的正整数解组的组数等于②的非负整数解组的个数C9=16，即81725个男孩分入该8个组，每组至少两人的分组方法有C16种。8个组排成每组以

2 女孩为头的圆排列有(81)!=7!种排列方法，再25个男孩站入的方法数为25!，7所以总的排列方法为C16•7!•25!

例2-3 将三角形每边n等分，过分点作其余两边的平行线，在已知三角形内所形成的平行四边形的个数记为S，求S的表达式。

11解 延长BA到M使AMBA，延长BC到N使CNBC。设将nnMNn1等分的分点（包括M，N共n2个）依次记为0，1，2，…，n1，于是平行四边形每边所在直线恰与MN交与4点i，j，k，l（0≤i＜j＜k＜l≤n1）反之，从MN上的n2个等分点中任意取4个等分点i，j，k，l（0≤i＜j＜k＜l≤n1），过i，j作AB的平行线，过k，l作BC的平行线，便可得到一个平行四边形，这种对应是一一对应，所以图中边不平行与AC的平行四边形有Cn42个，从而平行四边形的总个数S=3Cn42个。

例2-4 已知一个保险柜由11个成员的委员会负责管理，保险柜上加了若干把锁，这些锁的钥匙分配给各个委员保管使用。为了使任何6个委员同时到场就能打开保险柜，而任何5个委员同时到场都不能打开保险柜，最少应给保险柜加多少把锁？ （1971年波兰数学奥林匹克）

解 设满足要求的锁的最少把数为n，并记这n把锁的集合为A。设Ai为是第i个委员可以打开的锁的集合。依题意，对于{1,2,,11}的任何5元子集{i1,i2,,i5}，都有

Ai1Ai2Ai3Ai4Ai5A ①

对于{1,2,,11}的任何6元子集{j1,j2,,j6}，都有

Aj1Aj2Aj3Aj4Aj5Aj6A ②

由①知集合AAk15ik非空，设xi1i5是它的一个元素。这表明，xi1i5所代表的锁是编号为i1,,i5的那5个委员打不开的一把锁。②式则表明，对任何j{i1,,i5}，都必有xi1i5Aj。从而将{1,2,,11}的任何3

5元子集与锁之间建立一个对应关系。

这个关系是个单射。否则，设对于两个不同的5元子集{i1,i2,,i5}和{k1,k2,,k5}有xi1i5xk1k5。因为两个5元子集不同，故这两个5元子集的并集至少有6个元素，而这就导致有6个人都打不开同一把锁，矛盾。

5462个，所以锁的把数462。 因为{1,2,,11}的不同5元子集共有C11另一方面，如果给保险柜加了462把锁，并将这些锁与{1,2,,11}的462个5元子集建立一一对应关系。将每把锁的6枚钥匙分发给这把锁对应的5人组之外的6个委员掌管使用，则任何6个委员同时到场就能打开保险柜，而任何5个委员同时到场都不能打开保险柜。

所以，最少应给保险柜加462把锁。

3、配对法

求解某些数学间题时，针对问题中一个式子(或集合)F的结构特征，配一个与F具有内在联系的式子(或集合)F/，即F的配对式(或配对集合)，然后借助FF/ (表示某种数学运算，如加、减、乘、除等)，促进问题的转化和解决。我们把这种解决数学何题的思想称为配对思想。

例3-1 一次乒乓球比赛中，p1,p2,,pn是n个运动员，每两人正好比赛一次，没有平局。若记pi胜的次数为ai，负的次数为bi，证明:

ai=bi

22i1i1nn证明 首先，对于任意pi(1in)，他与其余n1个人都赛过，共赛过n1次。

因无平局，所以pi的胜、负次数之和为n1 (定数)，即

ai+bi=n1

其次，因无平局，所以每场比赛后，有人胜必有对应一人负。全部比赛结束后，的总次数等于负的总次数，即

ai=bi

i1i1nn于是

ai-bi=(aibi)

2222i1i1i1nnn

4 =(aibi)(aibi)=(n1)(aibi)0

i1i1nn例3-2 对于{1,2,,n}及其每一个非空子集，定义“交替和”如下：按照递减的顺重新排列元素，然后从最大的数开始交替的减、加后续的数。例如(1，2，4，6，9}，排列成(9，6，4，2，1)，交替和是9-6+4-2+l=6。{5}的交替和就是5。对n7，求所有交替和的总和。

解 不妨规定空集中元素交替和为0，将{1,2,,n}的2n个子集分成两类：一类含n的有2n1个子集，另一类不含n的，也是2n1个子集。将含n的子集F{n,a1,a2,,ai}与不含n的子集F/{a1,a2,,ai}配对，显然这个配对是一一对应的，且其中一对中的两个子集的交替和之和为n，于是{1,2,,n}的所有元素的交替和Sn2n1。因此当n7时，交替和的总和为448。

4、递推法

例4-1 将圆分成n（n≥2）个扇形S1，S2，…，Sn。现用m种颜色给这些扇形染色，每个扇形恰染一种颜色且要求相邻的扇形的颜色互不相同。问有多少种不同的染色方法？

解 设染色方法数为an。

（1）求初始值。n=2时，给S1染色有m种方法，继而给S2染色有（m-1）种方法，所以，a2=m（m-1）。

（2）求递推关系。因S1有m种染色方法，S2有（m-1）种染色方法，S3有（m-1）种染色方法，…，Sn1有（m-1）种染色方法，Sn仍有（m-1）种染色方法（不保证Sn与S1不同色）。这样共有m(m1)n1种染色方法，但这m(m1)n1种染色方法可分为两类：

一类是Sn与S1不同色，此时的染色方法有an种；另一类是Sn与S1同色，则将Sn与S1合并为一个扇形，并注意到此时Sn1与S1不同色，故这时的的染色方法有an1种，由加法原理得

5 an+an1=m(m1)n1（n≥2）

（3）求an。令bn=an1m1bbb，由+=，有－1=－（bn1nn1n(m1)nm1m1m1－１），即bn－1为首项为b2－1＝

bn－1＝（11，公比为－的等比数列的第n1项。

m1m1111）（－）n2＝(1)n，

n1(m1)m1m1即an1n(1)＝１＋，

(m1)n(m1)n1an＝(m1)n(1)n(m1)

例4-2 将周长为24的圆周等分为24段，从24个分点中选取8个点，使得其中任何两点所夹的弧长都不等于3和8。问满足要求的8点组的不同取法有多少种？

（2001年CMO题）

解 设24个分点依次为1，2，…，24，将24个数列成下表：

1 4 7 10 13 16 19 22

9 12 15 18 21 24 3 6

17 20 23 2 5 8 11 14

表中每行相邻两数所代表的点所夹弧长为3，每列相邻两数所代表的点所夹弧长为8，故每列至多取一个数，8列至多取8个数，但一共要取8个数，故每列恰取一个数且相邻两列所取的数不同行。

若将每列看作一个扇形，每列中第一、而、三行看作三种颜色，则由上面例题知，

a8＝(31)8(1)8(31)=258种。

例4-3 如图在1个正六边形的6个区域栽种观赏植物，要求同1区域中种同一种植物，相邻的2区域中种不同的植物。现有4种不同的植物可供选择，则有 种栽种方案。 （2001年全国高中联赛题）

解 在上述命题中，取n=6，m=4，即得

a6＝(41)6(1)6(41)=732种。

例4-4 集合Sn{1,2,,n}的子集中，若不含两个相邻的自然数，则称为“好子集”。问Sn中有多少个“好子集”？ （《中等数学》2008，6）

解 设Sn中有an个“好子集”。

当n1时，Sn中有子集和{1}是“好子集”，

a12。类似a23。

6 当n3时，设M为Sn的“好子集”。

若nM，则M也为Sn1的“好子集”； 若nM，则M{n}也为Sn2的“好子集”。

anan1an2,所以，

a2,a3.2115151515an1()an()an1

2222变形并递推得

an1151515an(anan1)

222

15n115()(a2a1)

2215n2()

2同理，an1消去an1得

1515n2an()

22an115n215n2[()()]

225

5、算两次

例5-1 有n粒弹子，任意将它们分成两堆，求出两堆弹子数的乘积，再将其中一堆，任意分成两堆，求出这两堆弹子数的乘积，如此下去，每次将其中一堆分成两堆，求出这两堆弹子数的乘积，直到不能分为止，记所有乘积之和为S，求S的可能值。

解 一方面，所有由两粒弹子组成的弹子对的数目为Cn2。另一方面，每分一次堆，就将原有的一些弹子对拆开，分到两堆中，每一步拆开的弹子对的数目恰好等于被拆成的两堆的弹子数的乘积，并且到最后，所有的Cn2个弹子对全部被拆开，故所有乘积的和S恰好就是有开始所有弹子对的数目Cn2，即S只可能

7 1取一个值S=Cn2=n(n1)

2

例5-2 地面上有10只小鸟在啄食，其中任意5只鸟中至少有4只在同一个圆上，问有鸟最多的一个圆上至少有几只鸟？

（1991年CMO第5题）

解 （略）

例5-3 有n个人，已知他们任意2人至多通电话一次，他们任意n-2个人之间通电话的总次数相等，都等于3k（k为正整数）。求n的所有可能值。

（2000年全国高中联赛题）

解 设n个人之间通电话的总次数为m。因n个人可形成Cnn2个n-2人组，且每n-2个人之间通电话的总次数都等于3k，故所有n-2人组中通电话次数的总和为Cnn2·3k。

4另一方面，上述计数中，每一对通话的人属于Cnn故每2人间2个n-2人组，4的一次通话重复计算了Cnn2次，所以

n2kCn3n(n1)3km ==

n4(n2)(n3)Cn2（1）若3不整除n，即（3，n）=1时，（n-3，n）=1，（n-3，3k）=1。

n-1）又（n-2，=1，所以n-3|n-1，即n-3≤2，n≤5。

n12n-3|2，为正整数。所以，1n3n3又Cn22≥3k≥3，n≥5，故n=5。

（2）若3整除n，则3|n-3，而（3，n-2）=1，又（n-1，n-2）=1，

n2

n-2|n，即为正整数。

1n2n2n-2|2，n-2≤2，n≤4。这与n≥5矛盾。

由（1）和（2）知n只可能为5，另一方面当n=5时满足题意。

例5-4 8位歌手参加艺术节，准备为他们安排m次演出，每次由其中4位登台表演，要求8位歌手中任意两位同时演出的次数都一样多。请设计一种方案，使得演出的次数m最少。

（1996年CMO第4题）

解 设任意两位歌手都同时演出r次，有

6m=mC42=rC82=28r

8

 3m=14r

由此可知，3|r，因而r≥3，m≥14。下面设计一种方案说明m=14可实现。

{1，2，3，4}，{5，6，7，8}，{1，2，5，6}，{3，4，7，8}，{1，2，7，8}，

{3，4，5，6}，{1，3，5，7}，{2，4，6，8}，{1，3，6，8}，{2，4，5，7}，

{1，4，5，8}，{2，3，6，7}，{1，4，6，7}，{2，3，5，8}。

例5-5 设S{A(a1,an)|ai0或1,i1,,8}。对于S中两个元素A(a1,an)和B(b1,bn)，记

d(A,B)|aibi|

i18并称其为A和B之间的距离。问：S中最多能取出多少个元素，它们之中任何两个的距离5？

解 设S中最多能取出m个元素，它们之中任何两个的距离5。可以知道，

m2m0(mod2)时，5Cm8()2

2m1m12m1(mod2)时，5Cm8()()

22解之得，m4。下面构造4个元素满足条件：

(0,0,0,0,0,0,0,0)；(1,1,1,0,0,1,1,1)；(1,1,1,1,1,0,0,0)；(0,0,0,1,1,1,1,1)

所以，m4。

6、容斥原理

例6-1 将与105互素的正整数从小到大排成数列，求出这个数列的第1000项。

（1994年全国高中联赛题）

解 首先，求出S={1，2，…，105}内与105=345互素的正整数的个数，令Ai={m|m∈S且m被i整除}（i=3，5，7）。于是S中与105互素的正整数的个数为

|A3A5A7|

=|S|-|A3|-|A5|-|A7|+|A3A5|+|A3A7|+|A5A7|-|A3A5A7|

105105105105105105105=105－－－+++－

357353757357=105-35-21-15+7+5+3-1=48

其次，设所有正整数中与105互素的正整数从小到大排成数列为{an}，于是有，a1=1，a2=2，a3=4，…，a46=101，a47=103，a48=104，并记P={a1，a2，…，

9 a48}。

一方面，数列{an}中每一项an可表示成为an=105kr（k，r为非负整数，0≤r≤104），于是由（an，105）=（105kr，105）=（r，105）=1，知r∈P，即数列{an}中每一项an可表示成为an=105kr（k为非负整数，r∈P）的形式。

另一方面，对任意非负整数k及任意r∈P，由（105kr，105）=（r，105）=1，知数列{an}中必有某一项an=105kr。

可见，数列{an}有且仅有形如105kr（k为非负整数，r∈P）的数组成，因对每一个固定的k，r取遍P中的数时，形如105kr的数有48个，得到数列中的48个项，因为1000=4820+40，所以，a1000=10520+a40。

而a48=104，a47=103，a46=101，a45=97，a44=94，a43=92，a42=89，a41=88，a40=86，所以a1000=10520+86=2186。

例6-2（错位排列）若{1，2，…，n}的一个排列{i1，i2，…，in}满足i1≠1，i2≠2，…，in≠n，则称{i1，i2，…，in}为{1，2，…，n}的一个错位排列。试求{1，2，…，n}的所有错位排列的个数Dn。

解 将{1，2，…，n}的所有排列集合记为S，则显然S=n!。设Aj={（i1，i2，…，in）|（i1，i2，

in）S且ijj}（j=1，2，…，n），于是

Dn=|A1A2…An|

___|Aj|=(n1)!（1≤j≤n），|AiAj|=(n2)!（1≤i＜j≤n)，…，

|Ai1Ai2…Air|=(nr)!（1≤i1＜i2＜…＜ir≤n)，…，

|A1A2…An|=0!=1。

故由容斥原理得，

Dn=S－Ai＋i1n_1ijnAAijn－…+（1）A1A2An

10 13nn（1）Cn0! =n!-Cn(n1)!+Cn2(n2)!-Cn(n3)!+…+111(1)n=n!（1）。

1!2!3!n!

7、不等式估计

例7-1 1650个学生排成22行、75列。已知其中任意两列处于同一行的两个人中，性别相同的学生不超过11对。证明：男生的个数不超过928。

（2003年第3届西部竞赛题）

解 设第i行的男生数为ai，则女生数为75-ai。依题意，可得

22211CC)

(Ca≤

7575aii22i1这是因为任意给定的两列处于同一行的两个人中，性别相同的学生不超过211对，故所有性别相同的两人对的个数不超过11C75。



(ai75ai)≤-30525

2i122

(2ai75)≤1650

i1222利用柯西不等式，可得

(2ai75)2≤22(2ai75)i122222≤36300

i1(2ai75)＜191

i12222ai＜i11911650＜921

2

例7-2 正整数a1，a2，…，a2006（可以有相同的）使得aa1a2，，…，2005a2a3a2006两两不相等。问：a1，a2，…，a2006中最少有多少个不同的数？

（2006年CMO第2题）

解 由于n个互不相同的正整数两两比值至多有Pn2+1个，由Pn2+1≥2005，

11 a1，a2，…，a2006中互不相同的数≥46。

下面构造一个例子，说明46是可以取到的。

设p1，p2，…，p46为46个互不相同的质数，构造a1，a2，…，a2006如下：

p1 ，p1，

p2 ，p1，

p3，p2，p3，p1，

p4，p3，p4，p2，p4，p1，

…

p45，p44，p45，p43，…，p45，p2，p45，p1，

p46，p45，p46，p44，…，p46，p34。

例7-3 在某次竞赛中，共有a个参赛选手与b个裁判，其中b≥3且为奇数。每个裁判对每个选手的评分只有“通过”或“不及格”两个等级。设k是满足以下条件的整数：任何两个裁判至多可对k个选手有完全相同的评分。证明：

kb1≥。

a2b （1998年IMO第2题）

证明 首先，如果两个裁判对某个选手有相同的评判，我们就称其为一个“同意”。由已知，任何两个裁判至多可对k个选手有完全相同的评判，即任何两个裁判最多产生k个“同意”。

 “同意”的总数≤kCb2。

另一方面，对任意一个选手，设有A个裁判判他通过，而B个裁判判他不及格，其中AB=b，则对这个选手，有关他的“同意”的个数为

A2B2(AB)

C+C=

22A2B(AB)2(AB)22(AB) =

4b2(AB)22b =

4由于b≥3且为奇数，故AB也应为奇数。从而

b212bb12)

C+C≥=(422A2B

12 b12)

2b12kb1

a(。

)≤kCb2≥2a2b

所有“同意”的个数≥a(

例7-4 已知平面上一个含有n个点的集合S，具有如下性质：

（1）S中任意三点不共线；

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

1证明：k＜2n。

2 （1989第30届IMO第3题）

解法一 对于S中任意两点Ai、Aj，在AiAj的垂直平分线上至多有S中的两个点（因为S中任意三点不共线），于是在这种线段的垂直平分线上至多有S中的2Cn2个点（每点按照出现的次数重复计数）。于是有

2Cn2≥nCk2

解之得，k＜12n。

2解法二 作一个以P为圆心的圆，考虑以S中任意两点为端点的线段。一方面，这种线段有Cn2条。另一方面，对每一个点AiS（i=1，2，…，n），有一个以Ai为圆心的圆，这个圆上至少有Ck2条弦。n个圆共有nCk2条弦，由于每两个圆至多有一条公共弦，所以端点属于S的线段至少有nCk2-Cn2条。

2Cn≥nCk2-Cn2

解之得，k＜

12n。

2例7-5 由1600名议员组成16000个委员会，每个委员会都由80名议员组成，求证一定存在两个委员会，它们至少有4名公共的成员。

（1996年全俄数学奥林匹克）

解 设第i名议员共参加Ki个委员会，于是

K1K2K16001600080

由于第i名议员共参加Ki个委员会，所以他参加了CKi个“委员会对”。 1600名议员共参加的“委员会对”的个数为CK+CK+…+CK122222，由柯西不等式有

1600

13 1600i1C2KiKiKi

2i12i1111600(Ki)24016000

21600i111(8016000)24016000

216001600031960

另一方面，共有16000个委员会，共可组成C16000800015999个不同的“委员会对”。因为

80001599931600031960，于是由抽屉原理知，必有4各由一名委员导致的“委员会对”是同一个“委员会对”，这意味着对中的两个委员会至少有4名公共的成员。

8、归纳法

例8-1 设A是集合S={1，2，…，1000000}的一个恰有101个元素的子集。证明：在S中存在数t1，t2，…，t100使得集合

Aj={xtjxA}，j=1，2，…，100

中，每两个的交集为空集。

（2003第44届IMO第1题）

证明 考虑集合D={xyx,yA}，则D中至多有1011001=10101个不同元素（注意0D）。两个集合Ai和Aj有公共元素的充要条件是ti-tjD。

因此我们只需在S中取出100个元素，使得其中任意两个的差不属于D。

任取S中的一个元素作为归纳基础。假设已经取出k个满足要求的元素，k≤99。我们需要在S中取数x，使得已经选出的k个数都不属于x+D，这里x+D={xyyD}。由于k个数取定后，至多有10101k≤999999个S中的数2不能取，故存在上面要求的x，命题得证。

例8-2 设f(n)表示平面上任何三点不共线的

n(

n4)个点所组成的三角形中,非锐角三角形个数的极小值。设1230，4f(4)C34，5f(5)C35，…，nf(n)C3n，…，则数列{n}是递增数列。

（自编题）

14 证 用数学归纳法证明。显见413

4假设当nk时 ,kk1,当nk1时 ,选取非锐角三角形个数取得极小值的

k1个点 ,这k1个点组成k1个 “k点组” ,显然每个“k点组”中至少有f(k)个非锐角三角形 ,总共至少有(k1)f(k)个非锐角三角形，因为每个非锐角三角形存在于(k2)个“k点组”(因为k1点中除了该三角形三点外还有k2个点 ,去掉k2个点中的任意一点就与该三角形组成一个“k点组”) ,即每个非锐角三角形重复计算了(k2)次 ,故有

(k1)f(k)

f(k1)k2不等式两边同时除以

从而命题得证。

征解题：是否limnnC3k1，即得k1k。

1？

2

9、调整法

调整法是先证明所求的极值存在，然后由问题的直观性，猜想出极值点。最后从反面证明函数在其他点不能达到极值：假设函数在另外的点(x1,x2,,xn)处达到极值，经过适当调整（常常是将小的分量变大，大的分量变小），发现函数在点(x1,x2,,xn)处的值更大或更小，从而断定它不是极值点。

例9-1 空间中有1989个点，其中任意三点不共线。把它们分成点数各不相同的30组，在任何3个不同的组中各取一点为顶点作三角形。试问为使这种三角形的个数最大，各组的点数应分别为多少？

（1989年第4届CMO题）

解 当把这1989个给定点分成30组，点数分别为n1，n2，…，n30时，满足题中要求的三角形总数为

Sij1ijk30///nnnk ①

由于把1989个点分成30组的不同分法只有有限种，故必有一种分法使S达到最大值。

设n1＜n2＜…＜n30为使S达到最大值的分法的各组点数，于是n1+n2+…+n30=1989，且它们有如下特点：

（1）ni1ni≤2，i=1，2，…，29。若不然，必有某个i，使得ni1ni≥3。

15 不妨设i=1，我们将①改写成

Sn1n2nk(n1n2)k3//303jk30nnjkij3ijk30/nnnk ②

////令n1=n1+1，n2=n2-1，于是n1+n2=n1+n2，n1＜n2，n1n2＞n1n2．由②可以看出，当用n1，n2代替n1，n2时，S的值将变大，矛盾。

（2）使ni1ni=2的i值不能多于1个。若有i和j，1≤i＜j≤29，使得/ni1ni=2，nj1nj=2，则当用ni=ni+1，nj1=nj1-1代替ni，nj1时，S的值////将变大，矛盾。

（3）若30组的点数从小到大每相邻两组都差1，则可设它们分别为k-14，k-13，…，k，k+1，…，k+15。于是有

（k-14）+（k-13）+…+k+（k+1）+…+（k+15）=30k+15

而1989不是15的倍数，所以，相邻两组点数之差恰有一个为2，其余为1。

（4）设j=1，2，…，i时，nj=mj1；j=i+1，2，…，30时，nj=mj。于是有

(mj1)(mj)=1989

j1ji1i30 30m-i=1524 ③

其中1≤i≤29，解得m=51，i=6，即S达到最大值的分法的各组点数分别为51，52，…，56，58，59，…，81。

例9-2 155只鸟停在一个圆C上。如果PiPj≤100，称鸟Pi与Pj是相互可见的。求相互可见的鸟对的最小个数（可以假定一个位置同时有几只鸟）。

（1989年第30届IMO预选题）

解 设A为圆C上一点，鸟Pi停在A，从A可以看到在B处（B≠A）的鸟Pj。设k为从B处可以看到而从A看不到的鸟的个数，l为从A处可以看到而从B_看不到的鸟的个数。不妨设k≥l。

如果所有在B处的鸟都飞往A处，那么对其中的每一只鸟来说，减少了k个可见对，同时增加了l个可见对。因此互相可见的对数不会增加。

经过上述的运算，停鸟的位置减少1。重复若干次可能的运算可以使得每两只鸟只有在同一位置时才是互相可见的。这时有鸟的位置至多有35个。

于是问题化为求

min{Cx2j|x1x2x35155,xjN{0}}

j135

16 2（当xj＜2时，Cx0)

j设x1=minxj，x2=maxxj，若x2-x1≥2，则令x1=x1+1，x2=x2-1，这时//鸟的总数仍为155，而

2222x2-1）≥1

CxCxCx/C/=-x1+（x12122即Cn较原来为小。

j因此，可以令x2-x1≤1，从而xj中有20个为4，15个为5，所求最小值为

215C52=270

20C4

10、反证法

例10-1 有n（n≥6）个人聚会，已知：

n（1） 每人至少同其中[]个人互相认识；

2n（2） 对于其中任意[]个人，或者其中有2人相识，或者余下的人中有22人相识。

（1996年全国高中联赛题）

证明：这n个人中必有3人两两相识。

证明 采用反证法：假设这n个人中无3人两两相识。

n（i）若n=2k（k≥3），则[]=k。

2任意考察其中一个人A，设A认识的人组成集合SA，A不认识的人组成集合SA，|SA|=m，根据（1）知，

m≥k，A不认识的人有2k-m-1个。

若|SA|＜k-1，由假设，SA中任意两个人都不相识，从而SA中任意一人B认识的人的个数＜k，与（1）矛盾。

若|SA|=k-1，由假设，SA中任意两个人都不相识，对于SA中任意一人B，根据（1），他认识A和SA中所有人，根据（2）知，既然SA中任意两个人都不相识，则SAA中必有两人（不妨设为C和D）相互认识，于是B、C和D两两相识，矛盾。

n（ii）若n=2k+1（k≥3），则[]=k。

2 （略）

17 例10-2 如果一个集合不包含满足xyz的三个数x、y、z，则称之为单纯的。设M{1,2,,2n1}，A是M的单纯子集，求|A|的最大值。

（1982年西德数学奥林匹克）

解 令A{1,3,,5,2n1}，则A是单纯的，此时|A|n1。下面，证明：对任何单纯子集A，有|A|n1。用反证法。假设|A|n2，即A中至少有n2个元素，设为：a1a2an2。设A中有p个奇数a1a2ap和n2p个偶数b1b2bn2p，注意到M中共有n1个奇数，n个偶数，故p2。

考察a2a1a3a1apa1，它们都是正偶数，连同前面假设的b1b2bn2p，共有(p1)(n2p)n1n个正偶数。由抽屉原理，必有两个元素相等，且只能是某个bi与某个aja1相等，于是aja1bi，与A是单纯的矛盾。

11、奇偶分析

例 11-1 在国际象棋盘上放着8个棋子：每一条水平线和垂直线上各有1个棋子。证明：在国际象棋盘的所有黑格中共有偶数个棋子。

（1989年全俄数学奥林匹克）

证明 把棋盘从角上的白格开始用数1,2,,8把直行和横行编号，那么棋盘上的每个格子就有两个坐标，对于白格来说，这两个坐标的和等于偶数，对于黑格来说，这两个坐标的和等于奇数。8个棋子所在的8个格子的坐标之和为2(128)，因此在这8个格子中只可能有偶数个黑格。

12、不变量法

例 12-1 学校数学小组的同学做成一种计算器，按下按钮可将四数组(a,b,c,d)变成四数组(ab,bc,cd,da)。证明：如果开始的四数组的数不全相等，那么按几次按钮后得到的四数组的数至少有一个大于1985。

（1985年全俄数学奥林匹克）

提示： 假设按n次按钮得到的数组为(an,bn,cn,dn)，那么容易得到anbncndn0，且anbncndn2(an1bn1cn1dn1)，

22222222

18

13、抽屉原理

例 13-1 试证在任何由12个人组成的人群中，都可以找出两个人来，使得在其余10个人中都至少有5个人，他们中的每个人都或者同时认识开头的两个人，或者同时不认识这两个人。

（1985年莫斯科数学奥林匹克）

证明 我们用12个点代表12个人，且当两人认识时，在相应两点间连一条红线，当两人不认识时，在相应两点间连一条蓝线。由一点引出的两条线段构成一个角，当两边同色时称为同色角，当两边异色时称为异色角。问题等价于：在12点中必可找出2点，使得其它10点对这2点张成的10个角中至少有5个同色角。

设第i点引出ni条红线，11ni条蓝线，i1,2,,12。则以第i点为角顶的同色角的个数为Cn2iC211ni25。所以图中至少共有2512300个同色角。图中212个点共可组成不同的两点组C1266个。30066436，由抽屉原理，必存在一个两点组及另外至少5个点，使得每点对前两点的张角是同色的。

19 思考题

1、集合A是一个整数集合，它的最小元素是1，最大元素是100。除1外，它的每个元素都等于A中两个元素（可能是相等的两个数）之和。在满足这些条件的一切集合中，求具有最少元素的集合。 （1980年全俄数学奥林匹克）

2、定义一个“希望集合”（Hope Set）简称HS如下：HS为一个非空集合，它满足条件“若xHS，则2xHS”。试问：在集合{1,2,,30}中，一共有多少个“希望子集合”？ （《中等数学》2007，6）

3、在一张矩形纸上画有一个圆．米老鼠在圆内选中了n个点（但不在纸上标注出来），称为“米氏点”．唐老鸭试图猜出这n个“米氏点”．在每一次尝试中，唐老鸭（在圆内或圆外）指出一个点，米老鼠则告诉他，该点离最近的尚未被猜出的“米氏点”的距离是多少．如果该距离为0，则算他猜中一个“米氏点”．唐老鸭会在纸上标注点，会累加距离，还会运用圆规和直尺（有刻度）作图．试问，唐老鸭是否一定可在少于(n1)2次尝试后，猜出所有“米氏点”?

（2006年江苏夏令营）

4、在考试中，有4个选择题，每题有3个可能的答案。一群学生参加考试，结果是对于其中任意3个人，都有一个问题，他们的答案各不相同。问至多有多少个学生？ （第29届IMO预选题）

5、有一根由60个环组成的锁链，每环重1克。最少砍断几个环，就可以利用断成的一段段锁链，凑出1克，2克，…，59克，60克的重量来（被砍断的环仍然为1克）？ (1951年莫斯科数学奥林匹克)

6、设M{1,2,,1995}，A是M的子集且满足条件:当xA时，15xA。则A中元素的个数最多是多少？ (1995年全国高中数学联赛)

7、设M{1,2,,20}，A是M的子集且满足条件:当xA时，2xA且3xA。则A中元素的个数最多是多少？ (自编题)

8、20个足球队参加全国冠军赛，问至少进行多少场比赛，才能使得任何3个队中总有两个队彼此赛过？ (1969年苏联数学奥林匹克)

9、设{B1,B2,,Bk}是A的一族非空子集，当ij时，BiBj至多有两个元素，求k的最大值。 (1985年IMO预选题)

10、设M{x1,x2,,xn}是自然数1,2,,n的一个排列。f(M)是M中每两个相邻元素的差的绝对值的最小值。求f(M)的最大值。

(1989年IMO预选题)

11、试证可以用4种不同颜色为数集M{1,2,,1987}中的每个数都涂上一种颜色，使得M中任何一个成等差数列的10元子集中的10个数的涂色都不全

20 相同。 (1987年IMO预选题)

12、将平面上每个点都以红、蓝两色之一着色，证明:存在这样的两个相似三角形，它们的相似比为1995，并且每一个三角形的三个顶点同色。 (1995年全国高中数学联赛)

13、在坐标平面上给定集合M{(x,y)|x,yN,x12,y12}，并将M中的每点都涂上红、白、蓝三色之一，试证存在一个矩形，它的边平行于坐标轴，4个顶点都在M中且颜色相同。 （1982年瑞典数学奥林匹克）

14、已知n（n2）条直线把平面分成若干个区域，其中的一些区域被涂上颜色，使得任何两个涂色区域都没有公共边，求证涂色区域的数目不超过12(nn)。 （1985年全苏数学奥林匹克）

315、从n个元素a1,a2,,an中取两个组成一对，共组成n对p1,p2,,pn。如果{ai,aj}是其中一对，则两对pi和pj中恰好有1个公共元素，求证每个元素恰好属于其中两对。 (1985年IMO预选题)

16、将(n1)(n1)的方格表的n2个结点中的每个涂上红、蓝两色之一，求使表中每个方格都恰有两个红色顶点的不同涂色方案的种数。 (1996年IMO预选题)

xy17、设A是正整数集合N的子集，对任何x,yA，xy，有|xy|。25求|A|的最大值。 (1985年IMO预选题)

征解题：将平面上每个点都以红、蓝两色之一着色，问:是否存在这样的两个相似三角形，它们的相似比为1995，并且这两个三角形的六个顶点同色？

21

思考题解答：

1、集合A是一个整数集合，它的最小元素是1，最大元素是100。除1外，它的每个元素都等于A中两个元素（可能是相等的两个数）之和。在满足这些条件的一切集合中，求具有最少元素的集合。

（1980年全俄数学奥林匹克）

解：答案：{1,2,3,5,10,20,25,50,100}。

设k11k2k3kn100，因为2kiki1，那么对于任意i有ki2i1，特别，1002n1，故n8。假设n8得出，k750，而2k525，矛盾。

2、 定义一个“希望集合”（Hope Set）简称HS如下：HS为一个非空集合，它满足条件“若xHS，则2xHS”。试问：在集合{1,2,,30}中，一共有多少个“希望子集合”？ （《中等数学》2007，6-26）

解 下面用“a2a”表示a与2a的两倍关系。注意到

①

1530,

②

1326,

③

1122,

④

918,

⑤

714,1428

⑥

510,1020

⑦

36,612,1224,

⑧

12,24,48,816。

显然,17,19,21,23,25,27,29是否在HS中不影响HS成为希望子集(因为这些数不能被2整除,且每个数的两倍均大于30),所以,这7个数的归属方案有27种。

在①中,15与30不能同时取,故有2213种方案。

同理,在②、③、④中,也各有3种方案。

下面采用递推算法。

在⑤中,若取7,则不能取14,此时,28可取亦可不取,有两种方案；若不取7,则由①知,关于14和28,共有3种方案(14和28的情况与①相同)。因此,在⑤中共有2+3=5种方案。

同理,在⑥中共有5种方案。

在⑦中,若取3,则不能取6,由①知关于12和24,有3种方案；若不取3,则由⑤知,关于6,12,24,有5种方案。因此,在⑦中共有3+5=8种方案。

在⑧中,若取1,则不能取2,由⑤知关于4,8,16,有5种方案；若不取1,则由⑦知关于2,4,8,16,有8种方案。因此,在⑧中共有5+8=13种方案。

再考虑到除去空集 (即1,2,…,30都不取),因此,所求的{1,2,,…,30}的希望子集的个数为273452813126956799。

22 3、 在一张矩形纸上画有一个圆．米老鼠在圆内选中了n个点（但不在纸上标注出来），称为“米氏点”．唐老鸭试图猜出这n个“米氏点”．在每一次尝试中，唐老鸭（在圆内或圆外）指出一个点，米老鼠则告诉他，该点离最近的尚未被猜出的“米氏点”的距离是多少．如果该距离为0，则算他猜中一个“米氏点”．唐老鸭会在纸上标注点，会累加距离，还会运用圆规和直尺（有刻度）作图．试问，唐老鸭是否一定可在少于(n1)2次尝试后，猜出所有“米氏点”?

（2006年江苏夏令营）

解：假设还存在k ≥ 1个“米氏点”C1，C2，…，Ck未被猜出．我们来证明，只需要经过2k1次尝试，就能猜出其中一个点．

在矩形纸上画一条直线l，使之与已知的圆不相交，在l上依次取k1个点A1，A2，…，Ak1．对每一个j2，…，k，Aj在Aj1和Aj1之间．米老鼠会指出每一个Ai到集合C1,C2,,Ck中最近的点距离di，i1，2，…，k1．

下面，唐老鸭可以利用直尺和圆规，在直线l的含圆的一侧，利用距离dj和dj1作点Bj，j1,2,,k．如果这个点不在矩形纸上就放弃作这个点．

我们来证明在所有k个Bj（j1,2,少有一个点在集合C1,C2,，即至,k）中，至少有一个“米氏点”事实上，根据抽屉原理，至少存在两个点Aj,Ck中．和Am（1 ≤ jm ≤ k1），使集合C1,C2,,Ck中离它们最近的点为同一点，设为Ci，1 ≤ i ≤ k．不难看出，在直线l上介于Aj和Am之间的每一点（包括这两点），点Ci都是集合C1,C2,特别地，点Aj1也是．这,Ck中离它们最近的点．就是说，米氏点Ci与直线l上的点Aj和Aj1的距离分别为dj和dj1．由于所有的米氏点均在圆内，也就是在直线同侧，由此就得到点Ci和Bj为同一点．

这样唐老鸭就找到了一个米氏点，他一共最多只需花k1k2k1次尝试．

现在一共有n个米氏点，总共所需要的尝试不超过

4、 在考试中，有4个选择题，每题有3个可能的答案。一群学生参加考试，结果是对于其中任意3个人，都有一个问题，他们的答案各不相同。问至多有多少个学生？ （第29届IMO预选题）

23

(2k1)k1nn(32n1)n(n2)(n1)2．

2 解 至多有9个学生。

我们设每题有3个答案为0、1、2三种。如果人数10，则第4个问题的答案中最多的两种至少出现7次。考虑这7个人，他们对第4个问题的答案为0、1（设答案2最少）。

这7个人对第3个问题的答案中，最多的两种（设为0和1）至少出现5次。

5个人（他们对第3个问题的答案为0或1）对第2个问题的答案中，最多的两种（不妨仍设为0和1）至少出现4次。

因此，有4个人，他们对第2、第3、第4个问题的答案均为0或1，这4个人中有两个人对第1个问题的答案相同。这两个人及（4个人中的）另一个人，对第1个问题的答案至少有两个是相同的。因此，如果人数9。

另一方面，构造如下：

1 2 3 4

1 0 1 0 1

2 1 2 1 1

3 2 0 2 1

4 0 0 1 0

5 1 1 2 0

6 2 2 0 0

7 0 2 2 2

8 1 0 0 2

9 2 1 1 2

5、有一根由60个环组成的锁链，每环重1克。最少砍断几个环，就可以利用断成的一段段锁链，凑出1克，2克，…，59克，60克的重量来（被砍断的环仍然为1克）？

(1951年莫斯科数学奥林匹克)

解 将锁链的第5，14，31环砍断，则整个锁链断成7部分，其重量分别为1，1，1，4，8，16，29。容易验证，由它们可以组成从1克到60克的任何一个整数重量。

当仅砍断两环时，整个锁链断成5部分。5个元素的集合只有31个非空子集，故由5部分锁链所能组成的不同重量不超过31个，不满足题设。

所以，最少砍断3个环。

6、 设M{1,2,,1995}，A是M的子集且满足条件:当xA时，15xA。则A中元素的个数最多是多少？ (1995年全国高中数学联赛)

解 用n(A)表示集合A所含元素的个数。6、

由题设，k与15k(k=9，10，…，133)这两个数中至少有一个不属于A，所以至少有125(=133-9+1)个数不属于A。

即n(A)19951251870

24 另一方面，可取A{1,2,,8}{134,135,,1995}，A满足题设条件，此时n(A)1870。

所以，n(A)的最大值就是1870。

7、 设M{1,2,,20}，A是M的子集且满足条件:当xA时，2xA且3xA。则A中元素的个数最多是多少？ (自编题)

解 用n(A)表示集合A所含元素的个数。

由题设容易用枚举法验证，M1{2,4,8,16}中至少有两个元素不属于A，M2{5,10,15,20}中至少有两个元素不属于A，M3{7,14}中至少有一个元素不属于A。现考虑M4{3,6,9,12,18}，容易用枚举法验证M4中至少有两个元素不属于A，分情况讨论：

（1）M4中至少有三个元素不属于A，则n(A)20221312。

（2）M4中有两个元素不属于A，由题设，{6,9,12}A，{6,9,18}A，{6,12,18}A，{9,12,18}A，则必有3A，且{3,12,18}A，从而1A，则n(A)202212112。

综合（1）和（2），所以至少有8个数不属于A。

即n(A)12。

另一方面，可取A{1,4,5,6,7,9,11,13,16,17,19,20}，A满足题设条件，此时n(A)12。

所以，n(A)的最大值就是12。

8、 20个足球队参加全国冠军赛，问至少进行多少场比赛，才能使得任何3个队中总有两个队彼此赛过？ (1969年苏联数学奥林匹克)

解 设进行了m场比赛后使得任何3个队中总有两个队彼此赛过。设A队是所有球队参赛场次最少的一个球队，它共参赛k场。于是已经与A队赛过的队至少进行了k场比赛。没与A队赛过的19k个队中的任何两队之间都得赛一场，否则存在3个队，其中任何两个队都未彼此赛过。于是有

2m(k1)k2C19k2(k9)2180180

25

2 这意味着至少进行90场比赛。

另一方面，将20个足球队分成两组，每组内的任何两队之间比赛一场，不同组的任何两队之间不比赛，则共进行了90场比赛。由于任何3个队中总有两个队同组，它们之间已经进行了一场比赛，这种安排满足题设要求。

所以，至少要进行90场比赛。

9、 设{B1,B2,,Bk}是A的一族非空子集，当ij时，BiBj至多有两个元素，求k的最大值。 (1985年IMO预选题)

解 首先，易见A的至多含3个元素的所有子集所构成的子集族满足题设要求，其中子集的个数为

C10C10C10175

所以，k的最大值不小于175。

另一方面，设有一个子集族满足题设要求且有A的子集B，B中至少有4个元素。设xB，令B/B{x}。因为BB/至少有3个元素，故B/。于是当用B/代替中的B时，中的子集数不减且仍然满足题设要求。重复这个过程，总可使得中的每个子集的元素不多于3而且中的子集数不减。由此可见，中的子集数不多于175。

因此，k的最大值为175。

10、 设M{x1,x2,,xn}是自然数1,2,,n的一个排列。f(M)是M中每两个相邻元素的差的绝对值的最小值。求f(M)的最大值。

(1989年IMO预选题)

n解

f(M)的最大值为。下面分情况讨论：

2n（1）n2k时，k与其相邻数之差的绝对值不大于k，故f(M)k。2123另一方面，令M(k1,1,k2,2,,2k,k)，则有f(M)k。

（2）n2k1时，k1与其相邻数之差的绝对值不大于k，故nf(M)k。另一方面，令M(k1,1,k2,2,,2k,k,2k1)，则有2f(M)k。

综上，命题成立。

26 11、 试证可以用4种不同颜色为数集M{1,2,,1987}中的每个数都涂上一种颜色，使得M中任何一个成等差数列的10元子集中的10个数的涂色都不全相同。

(1987年IMO预选题)

证明 首先，我们计算M中包含的10项等差数列的个数。公差为1的10项等差数列共1978个；公差为2的10项等差数列共1969个；公差为3的10项等差数列共1960个；…；公差为220的10项等差数列共7个。故M中包含的10项等差数列的总数为

1978+1969+1960+…+7=218350

因此，有同色的10项等差数列的染色法的种数不多于

n21835044197741987

而所有不同的染色法的总数为41987，故必有一种染色法满足题设要求。

12、将平面上每个点都以红、蓝两色之一着色，证明:存在这样的两个相似三角形，它们的相似比为1995，并且每一个三角形的三个顶点同色。

(1995年全国高中数学联赛)

证明 在平面上作两个同心圆，其半径比为1995。然后作出9条不同的半径，与两个同心圆各交于9个点。由抽屉原理知，大圆上的9个点中必有5个点同色。再考察过这同色5点的5条半径与小圆的5个交点，由抽屉原理知，其中必有3个点同色，于是分别以这同色3点和大圆上相应的同色3点为顶点的两个三角形便满足题设要求。

13、 在坐标平面上给定集合M{(x,y)|x,yN,x12,y12}，并将M中的每点都涂上红、白、蓝三色之一，试证存在一个矩形，它的边平行于坐标轴，4个顶点都在M中且颜色相同。

（1982年瑞典数学奥林匹克）

证明 显然，集合M中共有144个点且构成12行和12列的正方形点阵。由抽屉原理知，必有一种颜色的点至少有48个，不妨设红点有48个。设第i列中共有ai个红点，i1,2,,12，于是a1a2a1248。

将同一列中的两个红点称为一个点对并考察点对的数目。第i列上的点对有1ai(ai1)，从而点对总数为

212122m(a1a2a12)(a1a2a12)

221222(a1a2a12)24 ①

2由柯西不等式有

1m(a1a2a12)224

24

27 =96-24=72 ②

显然。每个红点对都对应一个由两点的纵坐标组成的“行对”。于是由②知，至少有72个“行对”。另一方面，由于点阵共12行，共可组成C1266个不同的“行对”，由抽屉原理，必有两个不同列的红点对对应于同一个“行对”。易见，以这两队中的4个红点为顶点的矩形即为所求。

14、 已知n（n2）条直线把平面分成若干个区域，其中的一些区域被涂上颜色，使得任何两个涂色区域都没有公共边，求证涂色区域的数目不超过12(nn)

3（1985年全苏数学奥林匹克）

证明 如果给定的n条直线两两平行，结论显然成立。设有k条边的涂色区域的个数为mk，k2,3,,n。因为每条直线被其他直线分割成至多n部分（线段或射线），因此，n条直线互相相交至多分成n2个部分。由已知，每个部分至多是一个涂色区域的边，所以

2m23m3nmnn2 ①

又因每条直线上只有两端的射线部分才可能是有两条边的涂色区域的边，故有m2n，从而由①知

2

m2m3mnm21(2m23m3nmn)

331

(n2n)

3

15、 从n个元素a1,a2,,an中取两个组成一对，共组成n对p1,p2,,pn。如果{ai,aj}是其中一对，则两对pi和pj中恰好有1个公共元素，求证每个元素恰好属于其中两对。

(1985年IMO预选题)

证明 设包含ak的数对的个数为dk，k

d11,2,,n，于是有

d2dn2n ①

对于每个dk，在dk个数对中，任何两个数对pi，pj都以ak为公共元素。由已知，{ai,aj}是数对之一时，两对pi和pj中恰好有1个公共元素，从而

28

由此及①得

C22d1CdCdn

2n22

d1d2dn4n ②

由均值表达式和①、②有

224n2(d1d2dn)2n(d12d22dn2)4n2

这意味着上述不等式中等号成立，从而必有d1即每个元素恰好属于两对之中。

16、 将(n1)(n1)的方格表的n2个结点中的每个涂上红、蓝两色之一，求使表中每个方格都恰有两个红色顶点的不同涂色方案的种数。

(1996年IMO预选题)

解 将第1行的n个结点中的每个涂上红、蓝两色之一，共有2n种不同涂色方案，分情况计数。

（1）第1行中任何两个相邻结点都异色，即红蓝相间地涂色，有两种不同的涂色方案。这时不难发现，第2行结点也必须红蓝相间地涂色，又是有两种不同的涂色方案。以此类推，每行结点也必都须红蓝相间地涂色。由乘法原理知，整个方格表共有2n种不同涂色方案。

（2）第1行结点中有两个相邻结点同色，共有2n2种不同的涂色方案。这时不难发现，第1行结点中同色的两个相邻结点下方第2行的两个相邻结点也必须同色，且与第1行的两个结点异色。以此推出，第2行的每个结点都与第1行的同列结点异色，即第2行结点只有唯一的涂色方案。同理可知，后面每行结点也只有唯一的涂色方案。所以这种情形共有2n2种不同的涂色方案。

由加法原理知，整个方格表共有2n12种不同涂色方案。

17、 设A是正整数集合N的子集，对任何x,yA，xy，有|xy|求|A|的最大值。 (1985年IMO预选题)

解 令X1{1}，X2{2}，X3{3}，X4{4}，X5{5,6}，X6{7,8,9}，X7{10,11,,16}，X8{17,18,,53}，X9{54,55,}N{1,2,,53}。

d2dn2，xy。25

29 对于X9，当x,yX9时，x25，所以yxyyXi(i1,2,,8)，当x,yXi时，显然有yxxxy，而对于2525xy，于是A最多只能含有上述每25个集合中的一个数，所以|A|9。

令A{1,2,3,4,5,7,,10,17,54}满足题设条件，所以|A|的最大值为9。

30