高联一试讲义系列2：容斥原理与抽屉原理

高联一试讲义系列：容斥原理与抽屉原理

【知识点、例题】

一、基础知识

(一)有限集合所含元素个数的几个简单性质(容斥原理)

设”(X)表示集合X所含元素的个数，

(1)n(AU+n[B}-n(AAB),

当n(AClB)=。时，n(AUB)=〃(A)+n(B)

n(AUBUC)=n(A)+〃(B)+n(C)-n(AryB)-n(AcC)一〃(BcC)+〃(AcBcC)

■1-3-1

推广到〃个集合的情况，

=

ZUA2L|A+z|AnA；c\A—+(-i)n-,p|A.

k

Z=1f=I\<i<j<k<ni=l

(2)变形：逐步淘汰原理(筛法公式)

设S是有限集，AuS(i=l,2,...〃)，A,在S中的补集为CsA(i=l,2,…〃)，则

GACG&C…CGARSI-力⑷+ZMM-ZM。4。卜.・+

j=ir*j\<i<j<k<n

..+(-ir'|qA|.

(三)集合而划分：

若AUAzU-UA”=/,且4rl4则这些子集的全集叫/的一个

〃一划分。

相对补集：称属于A而不属于B的全体元素，组成的集合为B对A的相对补集或差集，记作A-B。

(四)计数原理

定理1分类计数原理(加法原理)：做一件事有〃类办法，第一类办法中有町种不同的方法，第

二类办法中有用2种不同的方法，…，第〃类办法中有〃7“种不同的方法，那么完成这件事一共有

N=mi+叫+…+mn种不同的方法。

定理2分步计数原理(乘法原理)：做一件事分〃个步骤，第一步有町种不同的方法，第二步有m2

种不同的方法，…，第〃步有〃2”种不同的方法，那么完成这件事一共有N二叫•根2•”种不

同的方法。

应用举例

例1、某班对数学、物理、化学三科总评成绩统计如下：优秀的人数：数学21个，物理19个，化

学20个，数学物理都优秀9人，物理化学都优秀7人。化学数学都优秀8人。这个班有5人任何

一科都不优秀。那么确定这个班人数以及仅有一科优秀的三科分别有多少个人。

分析：自然地设A=｛数学总评优秀的人｝B=｛物理总评优秀的人｝C=｛化学总评优秀的人｝

则已知|A|=21|B|=19C|=20

MA5I-9i5nci-川・8

因为MU3ucH/i+i3i+ici-inci8i-|3nci-icn/|+|/n3nci

所以|jUBUC|・|/D3nc|-36

而|4nBnC|<mm｛|4n3|,|BnC|,|Cn/|｝・7

所山6q/U3UC|443.所以4iq/|448

这表明全班人数在41至48人之间。

仅数学优秀的人数是

M夙元MU3U6T3UC|

,|4UBUC|-|3|-|C|“BnC|T4U3UC|-32

可见仅数学优秀的人数在4至11人之间。同理仅物理优秀的人数在3至10人之间。

同理仅化学优秀的人数在5至12人之间。

例2、集合A,8是/=｛1,2,3,4,5,6,7,8,9,())的子集，若=求有序集合对(A，

B)的个数；

分析：集合/可划分为三个不相交的子集；A\B,矶4,API氏/中的每个元素恰属于其中一个子集,

10个元素共有3母种可能，每一种可能确定一个满足条件的集合对，所以集合对有31°个。

例3、求1,2,3,…，100中不能被2,3,5整除的数的个数。

分析：记/=｛1,2,3,…,100｝4=｛印。4100,且x能被2整除(记为2|力｝,

B=｛^<x<100,^x｝,C=(A|1<x<100,5|x｝,由容斥原理，

|AUBUc|=|A|+|z?|+|c|-|AnB|-|Bnc|-|cn^|+|?inBnc|=写+竽+

JJ

100100100幽川吗=74,

561015J30」

所以不能被2,3,5整除的数有|/|-|AU3Uq=26个。

lZN.

例4、设八=｛1,2,3,…，n｝,对XQA,设X中各兀素之和为NX,求Nx的总和XqA.

K分析X已知｛1,2,…,川的所有的子集共有2"个.而对于V"｛1,2,…，川，显然｛1,2,…，川中包含i

的子集与集合｛1,2，…,+…，川的子集个数相等.这就说明i在集合｛1,2，…，川的所有子集中

一共出现2'i次，即对所有的i求和，可得S“=2M-'(XZ).

r=1

【解】集合｛1,2，…,川的所有子集的元素之和为2”T(1+2+…+〃)=2'T♦誓山

=〃(〃+1)-2叫

工说明】本题的关键在于得出｛1,2,…，川中包含i的子集与集合｛1,2,…,+L…，川的子集个数

相等.这种一一对应的方法在集合问题以及以后的组合总是中应用非常广泛.

例5、给定集合/={1,2,3,…，川的々个子集：4，42,…,A"满足任何两个子集的交集非空，并

且再添加/的任何一个其他子集后将不再具有该性质，求女的值。

分析•：将/的子集作如下配对：每个子集和它的补集为一对，共得2小对，每一对不能同在这攵个

子集中，因此，k<T-x；其次，每一对中必有一个在这A:个子集中出现，否则，若有一对子集未

出现，设为G4与力，并设API4=0，则4qC/A，从而可以在左个子集中再添加G4,与已

知矛盾，所以2»2"-二综上，k=2,

例6.1992位科学家，每人至少与1329人合作过，那么，其中一定有四位数学家两两合作过.

分析：在与一个人A合作的人中我们找到Bo再说明一定有人与A和B都合作过为Co最后再说明有

人与A、B、C都合作过为D,那么A、B、C、D就是找的人了。

证明：一个人A。不妨设B与之合作。那么

―0方|・|力|*|方卜|7113|2132”1329・199221.所以存在（'前）月阴"与人和8

均合作过，40分别表示与A、B合作过的人的集合。同样地，

|3n^nc|-|3|+|j|+|C|-HU5|-|5UC|-|CU^|*MU5UC|

21392*3-1992x221。

所以存在占n<?。则A、B、c、I）就是所求，证毕。

说明：把•个普通的叙述性问题转化为集合的语言描述的问题通常为解题的关键之处，也是同学们

需加强的。

（五）抽屉原理

在数学问题中有一类与“存在性”有关的问题，例如：”13个人中至少有两个人出生在相同月

份”；“某校400名学生中，一定存在两名学生，他们在同一天过生口”；“2003个人任意分成200

个小组，一定存在一组，其成员数不少于11”。这类存在性问题中，“存在”的含义是“至少有一

个”。在解决这类问题时，只要求指明存在，一般并不需要指出哪一个，也不需要确定通过什么方

式把这个存在的东西找出来。这类问题相对来说涉及到的运算较少，依据的理论也不复杂，这些理

论称为“抽屉原理”。抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出

来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个重要的原理。

把它推广到一般情形有以下几种表现形式。

（一）抽屉原理的基本形式

定理1、如果把n+1个元素分成n个集合，那么不管怎么分，都存在一个集合，其中至少有两个元

素°

证明：（用反证法）若不存在至少有两个元素的集合，贝!每个集合至多1个元素，从而n个集合

至多有n个元素，此与共有n+1个元素矛盾，故命题成立。

例1、已知在边长为1的等边三角形内（包括边界）有任意五个点（图1）。证明：至少有两个点之

£

间的距离不大于5.如果把条件（包括边界）去掉，则结论可以修改为：至少有两个点之间的距离

小于2.

分析：5个点的分布是任意的。如果要证明“在边长为1的等边三角形内（包括边界）有5个

点，那么这5个点中一定有距离不大于5的两点”，则顺次连接三角形三边中点，即三角形的三条

中位线，可以分原等边三角形为4个全等的边长为5的小等边三角形，则5个点中必有2点位于同

£

一个小等边三角形中（包括边界），其距离便不大于5。

以上结论要由定理“三角形内（包括边界）任意两点间的距离不大于其最大边长”来保证，

下面我们就来证明这个定理。

如图2,设BC是△ABC的最大边，P,M是△ABC内（包括边界）任意两点，连接PM,过P分

别作AB、BC边的平行线，过M作AC边的平行线，设各平行线交点为P、Q、N,那么NPQN=NC,Z

QNP=NA因为BCNAB,所以/ANNC,则/QNP2NPQN,而NQMP2NQNPNNPQN（三角形的外角

£

大于不相邻的内角）所以PQ2PM。显然BC2PQ,故BC2PM。由此我们可以推知,边长为5的等边

£

三角形内（包括边界）两点间的距离不大于5。

说明：（1）这里是用等分三角形的方法来构造“抽屉”。类似地，还可以利用等分线段、等

分正方形的方法来构造“抽屉”。

例如“任取n+l个正数满足OV&Wl（i=l,2,-,n-l）,试证明：这n+1个数中必存在两个

数，其差的绝对值小于.又如：”在边长为1的正方形内任意放置五个点，求证：其中必有两

点，这两点之间的距离不大于〒。

例2、从1T00的自然数中•任意取出51个数，证明其中定有两个数，它们中的个是另个

的整数倍。

分析：本题似乎茫无头绪，从何入手？其关键何在？其实就在“两个数”，其中一个是另一个

的整数倍。我们要构造“抽屉”，使得每个抽屉里任取两个数，都有一个是另一个的整数倍，这只

有把公比是正整数的整个等比数列都放进去同一个抽屉才行，这里用得到一个自然数分类的基本知

识：任何一个正整数都可以表示成一个奇数与2的方幕的积，即若m£N+,K£N+,nWN,则

m=（2k-l）•2n,并且这种表示方式是唯一的,如1=1X2°,2=1X21,3=3X2°,……

证明：因为任何•个正整数都能表示成•个奇数乘2的方鼎，并且这种表示方法是唯•的，所以我

们可把1-100的正整数分成如下50个抽屉(因为1-100中共有50个奇数):

(1){1,1X2,1X22,1X23,1X24,1X25,1X26}；

2){3,3X2,3X22,3X23,3X24,3X25}；

3){5,5X2,5X22,5X23,5X24)；(4){7,7X2,7X22,7X23}；

(5){9,9X2,9X22,9X23}；(6){11,11X2,11X22,11X23}；...

(25){49,49X2}；(26){51}；……(50){99}。

这样，1T00的正整数就无重复，无遗漏地放进这50个抽屉内了。从这100个数中任取51

个数，也即从这50个抽屉内任取51个数，根据抽屉原则，其中必定至少有两个数属于同一个抽屉，

即属于(1)-(25)号中的某一个抽屉，显然，在这25个抽屉中的任何同一个抽屉内的两个数中，

一个是另一个的整数倍。

说明：(1)从上面的证明中可以看出，本题能够推广到一般情形：从L2n的自然数中，任

意取出n+1个数，则其中必有两个数，它们中的一个是另一个的整数倍。想一想，为什么？因为l-2n

中共含1,3,…，2nT这n个奇数，因此可以制造n个抽屉，而n+l>n,由抽屉原则，结论就是

必然的了。给n以具体值，就可以构造出不同的题目。例2中的n取值是50,还可以编制相反的题

目，如：“从前3()个自然数中最少要(不看这些数而以任意方式地)取出几个数，才能保证取出的

数中能找到两个数，其中较大的数是较小的数的倍数？”

(2)如下两个问题的结论都是否定的(n均为正整数)想一想，为什么？①从2,3,4,

2n+l中任取n+1个数，是否必有两个数，它们中的一个是另一个的整数倍？②从1,2,3,

2n+l中任取n+1个数，是否必有两个数，它们中的一个是另一个的整数倍？

(3)如果将(2)中两个问题中任取的n+1个数增加1个,都改成任取n+2个数,则它们的

结论是肯定的还是否定的？你能判断证明吗？

例3.从1到25的25个自然数中任意取出7个数，证明：取出的数中一定有两个数，这两个数中

大数不超过小数的1.5倍。

证明：把前25个自然数分成卜.面6组：

1;①

2,3；②

4,5,6；③

7,8,9,10；④

11,12,13,14,15,16；⑤

17,18,19,20,21,22,23,⑥

因为从前25个自然数中任意取出7个数，所以至少有两个数取自上面第②组到第⑥组中的某

同一组，这两个数中大数就不超过小数的1.5倍。

说明：(1)本题可以改变叙述如下：在前25个自然数中任意取出7个数，求证其中存在两个

23

数，它们相互的比值在脑内。显然，必须找出一种能把前25个自然数分成6（7-1=6）个集合

23

的方法，不过分类时有一个限制条件•：同一集合中任两个数的比值在［一,一］内，故同一集合中元素

32

的数值差不得过大。这样，我们可以用如上一种特殊的分类法：

递推分类法：

从1开始，显然1只能单独作为1个集合｛1｝；否则不满足限制条件.能与2同属于一个集

合的数只有3,于是｛2,3｝为一集合。如此依次递推下去，使若干个连续的自然数属于同一集合，

3_

其中最大的数不超过最小的数的亍倍，就可以得到满足条件的六个集合。

（2）如果我们按照（1）中的递推方法依次造“抽屉”，则第7个抽屉为｛26,27,28,29,

30,31,32,33,34,35,36,37,38,39）；第8个抽屉为：｛40,41,42,…，60｝；第9个抽屉

为：｛61,62,63,…，90,91｝；……

例4.在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明：其中一定存在两个整点,

它们的连线中点仍是整点。

分析与解答：由中点坐标公式知，坐标平面两点（XI,y。、（x2,y2）的中点坐标是‘亍人丁"乙

欲使1-'-7一都是整数，必须而且只须xl与x2,yl与y2的奇偶性相同。坐标平面上的任意整

点按照横纵两个坐标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数，偶数〉，（奇数，偶数）,

（偶数，奇数）以此构造四个“抽屉”，则在坐标平面上任4又五个整点，那么至少有两个整点，属

于同一个“抽屉”因此它们连线的中点就必是整点。

说明：我们可以把整点的概念推广：如果（xl,x2,…xn）是n维（元）有序数组，且xl,x2,…xn

中的每一个数都是整数，则称（xl,x2,…xn）是一个n维整点（整点又称格点）。如果对所有的n维

整点按每一个xi的奇偶性来分类，由于每一个位置上有奇、偶两种可能性，因此共可分为

2X2X…X2=2"个类。这是对n维整点的一种分类方法。当n=3时，2邑8,此时可以构造命题：“任

意给定空间中九个整点，求证它们之中必有两点存在，使连接这两点的直线段的内部含有整点”。

例5.在任意给出的100个整数中，都可以找出若干个数来（可以是一个数），它们的和可被100整

除。

分析：本题也似乎是茫无头绪，无从卜，手，其关键何在？仔细审题，它们的“和”能”被100

整除”应是做文章的地方。如果把这100个数排成一个数列，用除记其前m项的和，则其可构造S”

S2,・・Soo共100个"和”数。讨论这些“和数”被100除所得的余数。注意到SI,S2,…S100共有

100个数,一个数被100除所得的余数有0,1,2,…99共100种可能性。“苹果”数与“抽屉”

数一样多，如何排除“故障”？

证明：设已知的整数为由3,…a⑼考察数列出,a?,…am的前n项和构成的数列S”S2,-S.ooo

如果，，52，…5M中有某个数可被100整除，则命题得证。否则2,S2,…，00。

均不能被100整除，这样,它们被100除后余数必是｛1,2,…,99｝中的元素。由抽握原理I

知，S.,S2,…S仙中必有两个数，它们被100除后具有相同的余数。不妨设这两个数为Si,Sj(i

Vj),则100I(Sj-Si),即100I(%+1+%+2+A+勺_1+叼)。命题得证。

说明：有时候直接对所给对象作某种划分，是很难构造出恰当的抽屉的。这时候，我们需要对

所给对象先作一些变换，然后对变换得到的对象进行分类，就可以构造出恰当的抽屉。本题直接对

｛词进行分类是很难奏效的。但由｛an｝构造出｛Sn｝后，再对｛Sn｝进行分类就容易得多.另外，对｛Sn｝

按模100的剩余类划分时，只能分成的0个集合,而模n｝只有100项,似乎不能应用抽屉原则。但

注意到余数为0的类恰使结论成立，于是通过分别情况讨论后，就可去掉余数为0的类，从而转化

为100个数分配在剩下的99个类中。

例6、一个集合含有10个互不相同的两位数。试证，这个集合必有2个无公共元素的子集合，此两

子集的各数之和相等。

分析：两位数共有10,11,……,99,计99-9=90个,最大的10个两位数依次是90,91,……,99,

其和为945,因此，由10个两位数组成的任意一个集合中，其任一个子集中各元素之和都不会超过

945,而它的非空子集却有210—1=1023个，这是解决问题的突破口。

解:己知集合含有10个不同的两位数，因它含有10个元素，故必有2m=1024个子集，其中非

空子集有1023个，每一个子集内各数之和都不超过90+91+…98+99=945<1023,根据抽屉原理,

一定存在2个不同的子集，其元素之和相等。如此2个子集无公共元素，即交集为空集，则已符合

题目要求；如果这2个子集有公共元素，则划去它们的公共元素即共有的数字，可得两个无公共元

素的非空子集，其所含各数之和相等。

说明：此题构造了一个抽展原理模型，分两步完成，计算子集中数字之和最多有945个“抽屉”,

计算非空子集得1023个“苹果”，由此得出必有两个子集数字之和相等。第二步考察它们有无公共

元素，如无公共元素，则已符合要求；如有公共元素，则去掉相同的数字，得出无公共元素并且非

空的两个子集，满足条件。

(二)单色三角形问题

抽屉原理的应用多么奇妙，其关键在于恰当地制造抽屉，分割图形，利用自然数分类的不同

方法如按剩余类制造抽屉或按奇数乘以2的方哥制造抽屉，利用奇偶性等等，都是制造“独屉”的

方法。抽屉原理的道理极其简单，但“于无声处听惊雷”，恰当地精心地应用它，不仅可以解决国

内数学竞赛中的问题，而且可以解决国际中学生数学竞赛。

例6.17名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而

且任意两名科学家通信时只讨论一个题目，证明：其中至少有三名科学家，他们相互通信时讨论的

是同一个题目。

证明：视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题,

若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个

问题则在相应两点连条蓝线。二名科学家研究同一个问题就传化为找到一个二边同颜色的二角形。

考虑科学家A,他要与另外的16位科学家每人通信讨论〜个问题，相应于从A出发引出16条线段,

将它们染成3种颜色，而16=3X5+1,因而必有6=5+1条同色，不妨记为ABI,AB2,AB3,AB4,AB5,

AB6同红色，若Bi（i=l,2,…，6）之间有红线，则出现纥色三角线，命题已成立；否则Bl,B2,

B3,B4,B5,B6之间的连线只染有黄蓝两色。考虑从B1引出的5条线，B1B2,B1B3,B1B4,B1B5,

B1B6,用两种颜色染色,因为5=2X2+L故必有3=2+1条线段同色,假设为黄色，并记它们为B1B2,

B1B3,BlB4o这时若B2,B3,B4之间有黄线，则有黄色三角形，命题也成立,若B2,B3,B4,之

间无黄线，则4BZ,B3,B4,必为蓝色三角形，命题仍然成立。

说明：（1）本题源于一个古典问题一世界上任意6个人中必有3人互相认识，或互相不认;只。

（2）将互相认识用红色表示，将互相不认识用蓝色表示，（1）将化为一个染色问题，成为一个

图论问题：空间六个点，任何三点不共线，四点不共面，每两点之间连线都涂上红色或蓝色。求证:

存在三点，它们所成的三角形三边同色。（3）问题（2）可以往两个方向推广：其一是颜色的种数,

其二是点数。

本例便是方向一的进展，其证明已知上述。如果继续沿此方向前进，可有下题：在66个科学家

中，每个科学家都和其他科学家通信，在他们的通信中仅仅讨论四个题目，而任何两个科学家之间

仅仅讨论一个题目。证明至少有三个科学家，他们互相之间讨论同一个题目。

（4）回顾上面证明过程，对于17点染3色问题可归结为6点染2色问题，又可归结为3点染

一色问题。反过来，我们可以继续推广。从以上（3,1）—（6,2）-（17,3）的过程，易发现6:

（3-1）X2+2,17=（6-1）X3+2,66=（17-1）X4+2,同理可得（66T）X5+2=327,（327T）X6+2=1958…

记为rl=3,r2=6,r3=17,r4=65,r5=327,r6=1958,…..我们可以得到递推关系式：rn=n（rnTT）+2,

n=2,3,4…这样就可以构造出327点染5色问题，1958点染5色问题，都必出现一个同色三角形。

（二）抽屉原埋的具他形式。

定理2：把m个元素分成n个集合（m>n）

（1）当n能整除m时，至少有一个集合含有m/n个元素；

（2）当n不能整除m时，则至少有一个集合含有至少［m/n］+l个元素，（［m/n］表示不超过的最大

整数）

定理2也可叙述成：把mXn+1个元素放进n个集合，则必有一个集合中至少放有m+1个元素。

例7.9条直线的每一条都把一个正方形分成两个梯形，而且它们的面积之比为2：3。证明：

这9条直线中至少有3条通过同一个点。

证明：设正方形为ABCD,E、F分别是AB,CD的中点。设直线L把正方形ABCD分成两个梯形

ABGH和CDHG,并且与EF相交于P.梯形ABGH的面积:梯形CDHG的面积=2：3,EP是梯形ABGH的中

位线，PF是梯形CDHG的中位线，由于梯形的面积;中位线X梯形的高，并且两个梯形的高相等

（AB=CD）,所以梯形ABGH的面积：梯形CDHG的面积=EP：PF,也就是EP：PF=2：3.这说明，直线

L通过EF上一个固定的点P,这个点把EF分成长度为2：3的两部分。这样的点在EF上还有一个，

如图上的Q点（FQ：QE=2：3）。同样地，如果直线L与AB、CD相交，并且把正方形分成两个梯形面

枳之比是2：3,那么这条直线必定通过AD、BC中点连线上的两个类似的点(三等分点)。这样，在

正方形内就有4个固定的点，凡是把正方形面积分成两个面积为2：3的梯形的直线，一定通过这4

点中的某一个。我们把这4个点看作4个抽屉，9条直线看作9个苹果，由定理2可知，9MX2+1,

所以，必有一个抽屉内至少放有3个苹果，也就是，必有三条直线要通过一个点。

说明：本例中的抽屉比较隐蔽，正方形两双对边中点连线上的4个三等分点的发现是关键，而

它的发现源于对梯形面积公式S梯形=中位线X梯形的高的充分感悟。

例8.910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色

次序必定出现下述两种情况之一种：1.至少三行完全相同；2.至少有两组(四行)，每组的两行完

全相同。

证明：910瓶红、蓝墨水.排成130行，每行7瓶。每行中的7个位置中的每个位置都有红、

蓝两种可能，因而总计共有27=128种不同的行式(当且仅当两行墨水瓶颜色及次序完全相同时称为

“行式”相同.任取130行中的129行，依抽屉原理可知，必有两行(记为A,B)“行式”相同。

在除A、B外的其余128行中若有一行P与A(B)“行式”相同，则P,A,B满足“至少有三行完

仝相同”；在其余(除A,B外)的128行中若没有与A(B)行式相同者，则128行至多有127种

不同的行式，依抽屉原则，必有两行(不妨记为C、D)行式相同，这样便找到了(A,B)、(C,D)

两组(四行)，每组两行完全相同。

【练习】

1、设集合从={L2,3,4,5,6},3={456,7,8}则满足S=A且S30°的集合s的个数

为—56—个。

2、(2010湖北)将总和为200的10个数放置在给定的一个圆周上，且任意三个相邻的数之和不小

于5g.所有满足上述要求的10个数中最大数的最大值为26.

提示：设所有放置中的最大数为A,则A+3x58W200,所以AW26.

事实上26,6,26,26,6,26,26,6,26,26满足.

3、某班有36名同学参加数学、物理、化学课外探究小组，每名同学至多参加两个小组，已知参

加数学、物理、化学小组的人数分别为26,15,13,同时参加数学和物理小组的有6人，同时参加

物理和化学小组的有4人,则同时参加数学和化学小组的有8人。

解析：由条件知，每名同学至多参加两个小组,故不可能出现一名同学同时参加数学、物理、化学课

外探究小组，设参加数学、物理、化学小组的人数构成的集合分别为,则

card(AryBr>C)=0.ca「d(AcB)=6,card(BcC)=4,

由公式card(AuBuC)=card(A)+card(B)+card(C)-card(AGB)-card(AcC)-card(BcC)

易知36=26+15+13-6-4-card{AnC)故card(Ar>C)=8

即同时参加数学和化学小组的有8人.

4、已知集合4=卜5%—〃W0},B={A]6X-Z?>0},a.beN,且Ac3cN={2,3,4},则整数

对(〃/)的个数为

【解】5X-6/<0=>x<y；6x—〃=要使4c8cN={2,3,4},则

"2

602

即4所以数对(〃㈤共有C：C；=30。

4*520<6/<25

5、以国表示集合X的元素个数.若有限集合A8,C满足|AU却=20,忸Uq=30,

|cu川=40,则|An3dq的最大可能值为io.,

6、从集合知={1,2.3,,2009}中，去掉所有3的倍数以及5的倍数后，则M中剩下的元素个数

为—1072.

-2009-1「2009-

提示：集合M中，3的倍数有--=669个，5的倍数有=401个，15的倍数有

L3J5」

2009~1

市一二133个，则剩下的元素个数为2009—(669+401-133)=1072个.

7、设加={1,2,100},A是M的子集，且A中至少含有一个立方数，则这种子集A的

个数是2m一296

8、设M二{1,2,3,…，1995},A是M的子集且满足条件：当代A时，15xeA,则A中元素的个数最多

是________1870.

解：由于1995=15x133,所以，只要〃>133,就有15〃>1995.故取出所有大于133而不超过1995

的整数.由于这时己取出了15x9=135,…15x133=1995.故9至133的整数都不能再取，还可取1

至8这8个数，即共取出1995—133+8=1870个数，这说明所求数21870.

另一方面，把k与15k配对，(k不是15的倍数，且lWkW133)共得133—8=125对，每对数中至

多能取1个数为A的元素，这说明所求数W1870,综上可知应填1870.

9、集合的容量是指集合中元素的和.则满足条件“Aq{1,2,3,456,7},且若时，必有

8—auA”的所有非空集合A的存量的总和是.(月具体数字作答)

先找出满足条件的单元素和二元素的集合有：A={4),&={1,7},4={2,6},4={3,5},

将这四个集合中的元素任意组合起来也满足要求，则所有符合条件的集合A中元素的总和是：

(4+8+8+8)x23=224.

10、设〃是正整数，集合M二{1,2,…，2〃}.求最小的正整数在，使得对于M的任何一个“元子集，

其中必有4个互不相同的元素之和等于4n+1,则k=

解:考虑M的/升2元子集P={/?—1,〃，加4,2/?).P中任何4个不同元素之和不小于(〃-1)+加(〃

+1)+(n+2)=4n+2,所以+3.将M的元配为〃对，5=(九2n+1-7)，对M的

任一/升3元子集A,必有三对纥，纥，练同属于A(九、八、九两两不同).又将M的元配为〃一1对，

Cj(7»2/7—7),〃-1.对M的任一/?+3元子集A,必有一对G,同属于A,这一对必与

4,用」纥中至少一个无公共元素，这4个元素互不相同，且和为2〃+1+277=4〃+1,最小的正整

数A=〃+310.

11、(2013福建高一)对给定的正整数〃(n>6),由不大于〃的连续5个正整数的和组成

集合A,由不大于〃的连续6个正整数的和组成集合8,若集合的元素个数为

2013,则〃的最大值为12088o

【解答】由条件知集合A由形如Z+(A+l)+(Z+2)+(A+3)+(Z+4)=5&+10的数构

成，其中左为正整数，且心〃-4。

集合3由形如形(/+1)+(/+2)+(/+3)+(/+4)+(/+5)=6/+15的数构成,其中/为正

整数，且/。-5。

由5&+10=6/+15知，6/=5("1),所以6|伏一1)。

设01=6,(，为正整数)，则々=6f+l,l=5t,5k+10=6/+15=301+15。

由/K〃一5,攵<〃一4知，t<-~~-o

6

・•・Ac3由形如30,+15的数构成，其中，为正整数，且

6

・・・集合Ac3的元素个数为。

0

由Ac8的元素个数为2013知，—=2013o

6

・•・2013<-^<2014,12083<A?<12089o〃的最大值为12088。

6

12、集合{1,2,…,3〃}可以划分成〃个互不相交的三元集合{%,y,z},其中x+y=3z,则满足条

件的最小正整数九=

【解】设其中第i个三元集为{,£.,)，1},i=l,2,…,〃，则l+2+―+3〃=£4Zj,

/=1

所以3吗+1)=42,。当〃为偶数时，有8|3〃，所以〃28,当〃为奇数时，有电〃+1,所以

2i=i

n>5,当〃=5时，集合{I,11,4),{2,13,5},{3,15,6),{9,12,7),{10,14,8}满足条

件，所以〃的最小值为5。

解答题

1、设S是集合(1,2,2004)的子集，S中的任意两个数的差不等于4或7,问S中最多含有多

少个元素？

【解】将任意连续的11个整数排成一圈如右图所示。由题目条件可知每相邻两个数至多有一个

属于S,将这11个数按连续两个为一组，分成6组，其中一组只有一个数，若S含有这11个数中

至少6个,则必有两个数在同一组，与已知矛盾，所以S至多含有其中5个数。乂因为2004=182x11+2,

所以S一共至多含有182x5+2=912个元素，另一方面，当

5={4=1味+/,/=124,7,10/«2004«£阴时，恰有网=912,且S满足题目条件，所以最

少含有912个元素。

2、设〃211是一正整数，由不大于〃的连续10个正整数的和组成集合A,由不大于〃的连续II

个正整数的和组成集合8。若AcB的元素个数是181,求〃的最大值和最小值。

解：显然4={55+10左I0WAW〃-10,&eZ},B={66+U/|0</<z?-ll,7eZ),

为求Ac8的元素个数，令55+102=66+11/,则10Z=(/+1)11。…

再令2=11m，则得/=106一1.因为0KZW〃-10,加可取值0,1,2,，［三平1，此时/的相应

取值为-1,9,19,…,10［个乡一1。

符合/的取值范围，舍去不合乎要求的值-1,则知集合AcB的元素个数为［土f］。令

181=[纥W],则⑻<上U<182

11II

即2001K/IV2012,于是〃的最大值和最小值分别为2011和2001.

3、任取5个整数，必然能够从中选出三个，使它们的和能够被3整除.证明：任意给一个整数，它被3除，

余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类rO,r1,2.至少有一类包含所给5个数

中的至少两个.因此可能出现两种恃况：1.某一类至少包含三个数；2.某两类各含两个数，第三类包含一个数.若

是第一种情况，就在至少包含三个数的那一类中任取三数，其和一定能被3整除：若是第二种情况，在三类中各

取一个数，其和也能被3整除.综上所述，原命题正确.

4、把1到10的自然数摆成一个圆圈，证明一定存在在个相邻的数，它们的和数大于17.

证明如图12T,设a1，a2,①，…，①，aio分别代表不超过10的十个自然

数，它们围成一个圈，三个相邻的数的组成是(a1，a2,a：J,(a2,a3,

aO,(a3,a-oa5)»(as,aio,a】),ai,a2)共十组.现把它们

看作十个抽屉，每个抽屉的物体数是ai+a2+a3,a2+a3+a.,a3+a4+a5,-a9+aio+ai,

ai(l+ai+a2,由于

(ai+az+a^)+(a+a+a)+•,,+(a+aio+ai)+(aio+ai+a2)

23।a阳12-1

(1Q+1)xl

=3(ai+a2+.-+a9+aio)=3X(H2+»»«+9-HQ)=3x°=165=16x10+5

2

根据原则2,至少有一个括号内的三数和不少于17,即至少有三个相邻的数的和不小于17.

5、设4={1,2,3,4,5,6),B={7,8,9............在A中取三个数，5中取两个数组成五个

兀素的集合4,/=1,2,•--,20,1A,nAj\<2,}<i<J<20,求〃的最小值。

【解】〃而…⑹

设8中每个数在所有片中最多重复出现女次，则必有女工4。若不然，数机出现〃次(A>4),

则3%>12.在〃?出现的所有从中，至少有一个A中的数出现3次，不妨设它是1,就有集合{1,

4){l,6r3,674,/w,Z?2),{l,6z5,6r6,n?,/?3),其中4GA1</<6,为满足题意的集合。?必

各不相同，但只能是2,3,4.5,6这5个数，这不可能，所以A<4.

20个4中，3中的数有40个，因此至少是10个不同的，所以〃之16。当〃=16时，如下2()个集

合满足要求：

{1，2,3,7,8}，“，2,4,12,14},“，2,5,15,16},“，2,6,9,10},

{1，3,4,10,11}，{1,3,5,13,14},{1，3,6,12,15},{1,4,5,7,9},

{1，4,6,13,16},{1，5,6,8,11),{2,3,4,13,15},{2,3,5,9,11},

{2,3,6,14,16},{2,4,5,8,10},⑵4,6,7,11}，{2,5,6,12,13},

{3,4,5,12,16},{3,4,6,8,9),5,6,7.10},(4,5,6,14,15}。

6、把2!个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另

一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数(前一子集的元素个数应

不小于后一子集的元素个数)，证明：可以经过有限次挪动，使得到的子集与原集合相重合。

分析：首先考虑到2*是一个很特殊的数，其次我们发现若两个集合的元素个数除以2的若干次品后

若为奇数，那么，它们之间挪后就应为偶数这事实，若还不能想到解答就试下为-2,方-3时

的情况，相信解答就不会难找到了。

证明：考虑含奇数个元素的子集（如果有这样的子集），因为所有子集所含元素的个数总和是偶

数，所以具有奇数个元素的子集个数也是偶数，任意将所有含有奇数个元素的子集配成对，对每对

子集按题目要求的规则移动：从较大的子集挪出一些元素，添加到较小的子集，挪出的元素个数为

较小子集的元素个数，于是得到的所有子