高中数学竞赛专题讲座2 集合与容斥原理.doc

《高中数学竞赛专题讲座2 集合与容斥原理.doc》由会员分享，可在线阅读，更多相关《高中数学竞赛专题讲座2 集合与容斥原理.doc（8页珍藏版）》请在三一办公上搜索。

1、容斥原理与抽屉原理一、基础知识 （一）有限集合所含元素个数的几个简单性质（容斥原理） 设表示集合所含元素的个数,（1）, 当时， 推广到个集合的情况，（2）变形：逐步淘汰原理（筛法公式）设S是有限集，()，在S中的补集为()，则+（三）集合的划分：若，且，则这些子集的全集叫I的一个-划分。相对补集：称属于A而不属于B的全体元素，组成的集合为B对A的相对补集或差集，记作A-B。 （四）计数原理定理1 分类计数原理（加法原理）：做一件事有类办法，第一类办法中有种不同的方法，第二类办法中有种不同的方法，第类办法中有种不同的方法，那么完成这件事一共有种不同的方法。定理2 分步计数原理（乘法原理）：做一

2、件事分个步骤，第一步有种不同的方法，第二步有种不同的方法，第步有种不同的方法，那么完成这件事一共有种不同的方法。应用举例例1、某班对数学、物理、化学三科总评成绩统计如下：优秀的人数：数学21个，物理19个，化学20个，数学物理都优秀9人，物理化学都优秀7人。化学数学都优秀8人。这个班有5人任何一科都不优秀。那么确定这个班人数以及仅有一科优秀的三科分别有多少个人。分析：自然地设A=数学总评优秀的人 B=物理总评优秀的人 C=化学总评优秀的人则已知|A|=21 |B|=19 |C|=20这表明全班人数在41至48人之间。仅数学优秀的人数是可见仅数学优秀的人数在4至11人之间。同理仅物理优秀的人数在

3、3至10人之间。同理仅化学优秀的人数在5至12人之间。例2、集合A，B是I=1，2，3，4，5，6，7，8，9，0的子集，若，求有序集合对（A，B）的个数；分析：集合I可划分为三个不相交的子集；AB，BA，中的每个元素恰属于其中一个子集，10个元素共有310种可能，每一种可能确定一个满足条件的集合对，所以集合对有310个。例3、 求1，2，3，100中不能被2，3，5整除的数的个数。分析：记，由容斥原理，所以不能被2，3，5整除的数有个。例4、设A1,2，3，n，对XA，设X中各元素之和为Nx，求Nx的总和.分析已知的所有的子集共有个.而对于,显然中包含的子集与集合的子集个数相等.这就说明在集

4、合的所有子集中一共出现次,即对所有的求和,可得【解】集合的所有子集的元素之和为=说明本题的关键在于得出中包含的子集与集合的子集个数相等.这种一一对应的方法在集合问题以及以后的组合总是中应用非常广泛.例5、给定集合的个子集：，满足任何两个子集的交集非空，并且再添加I的任何一个其他子集后将不再具有该性质，求的值。分析：将I的子集作如下配对：每个子集和它的补集为一对，共得对，每一对不能同在这个子集中，因此，；其次，每一对中必有一个在这个子集中出现，否则，若有一对子集未出现，设为C1A与A，并设，则，从而可以在个子集中再添加，与已知矛盾，所以。综上，。例6、1992位科学家，每人至少与1329人合作过

5、，那么，其中一定有四位数学家两两合作过。分析：在与一个人A合作的人中我们找到B。再说明一定有人与A和B都合作过为C。最后再说明有人与A、B、C都合作过为D，那么A、B、C、D就是找的人了。 证明：一个人A。不妨设B与之合作。那么。即C与A和B均合作过，分别表示与A、B合作过的人的集合。同样地，。所以存在。则A、B、C、D就是所求，证毕。说明：把一个普通的叙述性问题转化为集合的语言描述的问题通常为解题的关键之处，也是同学们需加强的。（五）抽屉原理 在数学问题中有一类与“存在性”有关的问题，例如：“13个人中至少有两个人出生在相同月份”；“某校400名学生中，一定存在两名学生，他们在同一天过生日”

6、；“2003个人任意分成200个小组，一定存在一组，其成员数不少于11”。这类存在性问题中，“存在”的含义是“至少有一个”。在解决这类问题时，只要求指明存在，一般并不需要指出哪一个，也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉及到的运算较少，依据的理论也不复杂，这些理论称为“抽屉原理”。 抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。（一）抽屉原理的基本形式 定理1、如果把n+1个元素分成n个集合，那么不管怎么分，都存在一个集合，

7、其中至少有两个元素。 证明：（用反证法）若不存在至少有两个元素的集合，则每个集合至多1个元素，从而n个集合至多有n个元素，此与共有n+1个元素矛盾，故命题成立。 例1、 已知在边长为1的等边三角形内（包括边界）有任意五个点（图1）。证明：至少有两个点之间的距离不大于. 如果把条件（包括边界）去掉，则结论可以修改为：至少有两个点之间的距离小于 .分析：5个点的分布是任意的。如果要证明“在边长为1的等边三角形内（包括边界）有5个点，那么这5个点中一定有距离不大于的两点”，则顺次连接三角形三边中点，即三角形的三条中位线，可以分原等边三角形为4个全等的边长为的小等边三角形，则5个点中必有2点位于同一个

8、小等边三角形中（包括边界），其距离便不大于。 以上结论要由定理“三角形内（包括边界）任意两点间的距离不大于其最大边长”来保证，下面我们就来证明这个定理。如图2，设BC是ABC的最大边，P，M是ABC内（包括边界）任意两点，连接PM，过P分别作AB、BC边的平行线，过M作AC边的平行线，设各平行线交点为P、Q、N，那么PQN=C，QNP=A因为BCAB，所以AC，则QNPPQN，而QMPQNPPQN（三角形的外角大于不相邻的内角），所以 PQPM。显然BCPQ，故BCPM。由此我们可以推知，边长为的等边三角形内（包括边界）两点间的距离不大于。 说明：（1）这里是用等分三角形的方法来构造“抽屉”。

9、类似地，还可以利用等分线段、等分正方形的方法来构造“抽屉”。例如“任取n+1个正数ai，满足0ai1（i=1,2,n+1），试证明：这n+1个数中必存在两个数，其差的绝对值小于”。又如：“在边长为1的正方形内任意放置五个点，求证：其中必有两点，这两点之间的距离不大于。 例2、 从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。 分析：本题似乎茫无头绪，从何入手？其关键何在？其实就在“两个数”，其中一个是另一个的整数倍。我们要构造“抽屉”，使得每个抽屉里任取两个数，都有一个是另一个的整数倍，这只有把公比是正整数的整个等比数列都放进去同一个抽屉才行，这里

10、用得到一个自然数分类的基本知识：任何一个正整数都可以表示成一个奇数与2的方幂的积，即若mN+,KN+，nN,则m=(2k-1)2n，并且这种表示方式是唯一的，如1=12，2=121，3=32， 证明：因为任何一个正整数都能表示成一个奇数乘2的方幂，并且这种表示方法是唯一的，所以我们可把1-100的正整数分成如下50个抽屉（因为1-100中共有50个奇数）： （1）1，12，122，123，124，125，126；2）3，32，322，323，324，325；3）5，52，522，523，524； （4）7，72，722，723；（5）9，92，922，923；（6）11，112，1122，11

11、23；（25）49，492；（26）51；（50）99。 这样，1-100的正整数就无重复，无遗漏地放进这50个抽屉内了。从这100个数中任取51个数，也即从这50个抽屉内任取51个数，根据抽屉原则，其中必定至少有两个数属于同一个抽屉，即属于（1）-（25）号中的某一个抽屉，显然，在这25个抽屉中的任何同一个抽屉内的两个数中，一个是另一个的整数倍。 说明： （1）从上面的证明中可以看出，本题能够推广到一般情形：从1-2n的自然数中，任意取出n+1个数，则其中必有两个数，它们中的一个是另一个的整数倍。想一想，为什么？因为1-2n中共含1，3，2n-1这n个奇数，因此可以制造n个抽屉，而n+1n，

12、由抽屉原则，结论就是必然的了。给n以具体值，就可以构造出不同的题目。例2中的n取值是50，还可以编制相反的题目，如：“从前30个自然数中最少要（不看这些数而以任意方式地）取出几个数，才能保证取出的数中能找到两个数，其中较大的数是较小的数的倍数？” (2）如下两个问题的结论都是否定的（n均为正整数）想一想，为什么？ 从2，3，4，2n+1中任取n+1个数，是否必有两个数，它们中的一个是另一个的整数倍？从1，2，3，2n+1中任取n+1个数，是否必有两个数，它们中的一个是另一个的整数倍？（3）如果将（2）中两个问题中任取的n+1个数增加1个，都改成任取n+2个数，则它们的结论是肯定的还是否定的？你

13、能判断证明吗？ 例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个数，求证其中存在两个数，它们相互的比值在内。显然，必须找出一种能把前25个自然数分成6（7-1=6）个集合的方法

14、，不过分类时有一个限制条件：同一集合中任两个数的比值在内，故同一集合中元素的数值差不得过大。这样，我们可以用如上一种特殊的分类法：递推分类法： 从1开始，显然1只能单独作为1个集合1；否则不满足限制条件.能与2同属于一个集合的数只有3，于是2，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，

15、91； 例4在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明：其中一定存在两个整点，它们的连线中点仍是整点。 分析与解答：由中点坐标公式知，坐标平面两点（x1,y1）、（x2,y2）的中点坐标是。欲使都是整数，必须而且只须x1与x2，y1与y2的奇偶性相同。坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数，偶数），（奇数，偶数），（偶数，奇数）以此构造四个“抽屉”，则在坐标平面上任取五个整点，那么至少有两个整点，属于同一个“抽屉”因此它们连线的中点就必是整点。 说明：我们可以把整点的概念推广：如果（x1,x2,xn）是n维（元）有序数组，且x1,

16、x2,xn中的每一个数都是整数，则称（x1,x2,xn）是一个n维整点（整点又称格点）。如果对所有的n维整点按每一个xi的奇偶性来分类，由于每一个位置上有奇、偶两种可能性，因此共可分为222=2n个类。这是对n维整点的一种分类方法。当n=3时，23=8，此时可以构造命题：“任意给定空间中九个整点，求证它们之中必有两点存在，使连接这两点的直线段的内部含有整点”。 例5在任意给出的100个整数中，都可以找出若干个数来（可以是一个数），它们的和可被100整除。 分析：本题也似乎是茫无头绪，无从下手，其关键何在？仔细审题，它们的“和”能“被100整除”应是做文章的地方。如果把这100个数排成一个数列，

17、用Sm记其前m项的和，则其可构造S1，S2，S100共100个和数。讨论这些“和数”被100除所得的余数。注意到S1，S2，S100共有100个数，一个数被100除所得的余数有0，1，2，99共100种可能性。“苹果”数与“抽屉”数一样多，如何排除“故障”？证明：设已知的整数为a1,a2,a100考察数列a1,a2,a100的前n项和构成的数列S1，S2，S100。 如果S1，S2，S100中有某个数可被100整除，则命题得证。否则S1，S2，S100。 均不能被100整除，这样，它们被100除后余数必是1，2，99中的元素。由抽屉原理I知，S1，S2，S100中必有两个数，它们被100除后具

18、有相同的余数。不妨设这两个数为Si，Sj（ij），则100（Sj-Si），即100。命题得证。 说明：有时候直接对所给对象作某种划分，是很难构造出恰当的抽屉的。这时候，我们需要对所给对象先作一些变换，然后对变换得到的对象进行分类，就可以构造出恰当的抽屉。本题直接对an进行分类是很难奏效的。但由an构造出Sn后，再对Sn进行分类就容易得多. 另外，对Sn按模100的剩余类划分时，只能分成100个集合，而Sn只有100项，似乎不能应用抽屉原则。但注意到余数为0的类恰使结论成立，于是通过分别情况讨论后，就可去掉余数为0的类，从而转化为100个数分配在剩下的99个类中。 例6、一个集合含有10个互不相

19、同的两位数。试证，这个集合必有2个无公共元素的子集合，此两子集的各数之和相等。分析：两位数共有10,11，,99，计99990个，最大的10个两位数依次是90,91，,99，其和为945，因此，由10个两位数组成的任意一个集合中，其任一个子集中各元素之和都不会超过945，而它的非空子集却有21011023个，这是解决问题的突破口。解：已知集合含有10个不同的两位数，因它含有10个元素，故必有2101024个子集，其中非空子集有1023个，每一个子集内各数之和都不超过90919899945133，就有15n1995.故取出所有大于133而不超过1995的整数. 由于这时己取出了159=135,

20、15133=1995. 故9至133的整数都不能再取，还可取1至8这8个数，即共取出1995133+8=1870个数, 这说明所求数1870.另一方面，把k与15k配对，（k不是15的倍数，且1k133）共得1338=125对，每对数中至多能取1个数为A的元素，这说明所求数1870，综上可知应填1870.9、集合的容量是指集合中元素的和则满足条件“，且若时，必有”的所有非空集合的容量的总和是 （用具体数字作答）先找出满足条件的单元素和二元素的集合有：，将这四个集合中的元素任意组合起来也满足要求，则所有符合条件的集合A中元素的总和是 ：10、设n是正整数，集合M=1，2，2n求最小的正整数k，使

21、得对于M的任何一个k元子集，其中必有4个互不相同的元素之和等于4 n +1,则k= 解：考虑M的n+2元子集P=nl，n，n+1，2nP中任何4个不同元素之和不小于(n1)+n+( n +1)+( n +2)=4 n +2，所以kn +3将M的元配为n对，Bi=(i，2 n +1i)，1in 对M的任一n+3元子集A，必有三对同属于A(i1、I 2、I 3两两不同)又将M的元配为n1对，C I (i，2ni)，1in1对M的任一n+3元子集A，必有一对同属于A，这一对必与中至少一个无公共元素，这4个元素互不相同，且和为2 n +1+2 n =4 n +1,最小的正整数k= n +31011、（

22、2013福建高一）对给定的正整数（），由不大于的连续5个正整数的和组成集合，由不大于的连续6个正整数的和组成集合，若集合的元素个数为2013，则的最大值为 12088 。【解答】由条件知集合由形如的数构成，其中为正整数，且。集合由形如的数构成，其中为正整数，且。由知，所以。设（为正整数），则，。由，知，。 由形如的数构成，其中为正整数，且。 集合的元素个数为。由的元素个数为2013知，。 ，。的最大值为。12、集合1，2，3n可以划分成个互不相交的三元集合，其中，则满足条件的最小正整数= 【解】 设其中第个三元集为则1+2+所以。当为偶数时，有，所以，当为奇数时，有，所以，当时，集合1，11，

23、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=18211+2，所以S一共至多含有1825+2=912个元素，另一方面，当时，恰有，且S满足题目条件，所以最少含有912个元素。2、（2011甘肃）

24、设是一正整数， 由不大于的连续10个正整数的和组成集合，由不大于的连续11个正整数的和组成集合。若的元素个数是181，求的最大值和最小值。解：显然，为求的元素个数，令 ，则。- 再令，则得因为，可取值，此时的相应取值为。 注意到 符合的取值范围，舍去不合乎要求的值，则知集合的元素个数为。令 ， 则 即，于是的最大值和最小值分别为2011和2001 3、任取 5 个整数，必然能够从中选出三个，使它们的和能够被 3 整除 证明：任意给一个整数，它被 3 除，余数可能为 0，1，2，我们把被 3 除余数为 0，1，2 的整数各归 入类 r，r1，r2至少有一类包含所给个数中的至少两个因此可能出现两种

25、情况： 1某一类至少包含三个数； 2某两类各含两个数，第三类包含一个数 若是第一种情况，就在至少包含三个数的那一类中任取三数，其和一定能被 3 整除； 若是第二种情况，在三类中各取一个数，其和也能被 3 整除 综上所述，原命题正确4、把1到10的自然数摆成一个圆圈，证明一定存在在个相邻的数，它们的和数大于17.证明 如图12-1，设a1，a2，a3，a9，a10分别代表不超过10的十个自然数，它们围成一个圈，三个相邻的数的组成是（a1，a2，a3），（a2，a3，a4），（a3，a4，a5），,（a9，a10，a1）,（a10，a1，a2）共十组.现把它们看作十个抽屉，每个抽屉的物体数是a1+

26、a2+a3，a2+a3+a4，a3+a4+a5，a9+a10+a1，a10+a1+a2,由于（a1+a2+a3）+（a2+a3+a4）+（a9+a10+a1）+（a10+a1+a2）=3(a1+a2+a9+a10)=3(1+2+9+10)=根据原则2,至少有一个括号内的三数和不少于17,即至少有三个相邻的数的和不小于17.5、任意给定7个实数，则必存在两个数，使得 6、设A=1，2，3，4，5，6，B=7，8，9，n，在A中取三个数，B中取两个数组成五个元素的集合，求的最小值。【解】 设B中每个数在所有中最多重复出现次，则必有。若不然，数出现次（），则在出现的所有中，至少有一个A中的数出现3次

27、，不妨设它是1，就有集合1，其中，为满足题意的集合。必各不相同，但只能是2，3，4，5，6这5个数，这不可能，所以20个中，B中的数有40个，因此至少是10个不同的，所以。当时，如下20个集合满足要求：1，2，3，7，8， 1，2，4，12，14， 1，2，5，15，16， 1，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， 2，4，6，7，11， 2，5，6，12，13，3，4，

28、5，12，16， 3，4，6，8，9， 3，5，6，7，10， 4，5，6，14，15。7、把个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合。分析：首先考虑到是一个很特殊的数，其次我们发现若两个集合的元素个数除以2的若干次幂后若为奇数，那么，它们之间挪后就应为偶数这一事实，若还不能想到解答就试一下，时的情况，相信解答就不会难找到了。证明：考虑含奇数个元素的子集（如果有这样的子集），因为所有子集所含元

29、素的个数总和是偶数，所以具有奇数个元素的子集个数也是偶数，任意将所有含有奇数个元素的子集配成对，对每对子集按题目要求的规则移动：从较大的子集挪出一些元素，添加到较小的子集，挪出的元素个数为较小子集的元素个数，于是得到的所有子集的元素个数都是偶数，现在考虑元素个数不被4整除的子集，如果，则总共有两个元素，它们在同一个子集，因此设，因为子集的元素个数的总数被4整除，因此这样的子集的个数为偶数，任意将这样的子集配成对，对每一对子集施行满足题目要求的挪动，于是得到的每个子集数均可被4整除，依此做下去，最后得到的每个子集元素个数均可被整除，也就是只能有一个子集，它的元素个数为，证毕。说明：这道题的证明中

30、隐含了一种单一变量在变化时变化方向相同这一性质，就这道题来说，一直在增加的就是各子集元素个数被2的多少次幂整除的这个幂次数，这是一大类问题，除了这种变化量，还要经常考虑变化中的不变量。8给定1978个集合，每个集合都含有40个元素，已知其中任意两个集合都恰有一个公共元，证明：存在一个元素，它属于全部集合。分析：我们可以先去找一个属于很多个集合的元素，最好它就是我们要找的那一个。证明：考虑给定的1978个集合中任意一个集合，它和其它1977个集合都相交，因此，存在，使得它至少属于其中50个集合，否则，集合中每个元素至多属于49个集合，而集合恰有40个元素，所以除外至多有1960个集合，不可能，因

31、此设属于集合，下面证明它属于给定的1978个集合中任一个。对于除了，的任一个集合，设，则与，每一个都有至少一个元素的交，它们都与不同，那么，就至少要有51个元素，不可能，因此属于每个集合。说明：这种题目最怕把它想难了，想行太难了，就会觉得无从下手，做数学竞赛题就需要一方面在做题之前选好方向，另一方面就是大胆尝试去做。9在个元素组成的集合中取个不同的三元子集。证明：其中必有两个，它们恰有一个公共元。分析：证明恰有一个公共元也许挺难。那么证只有两个或零个公共元不可能是否可行呢？如果具有两个公共元的集合与表示为、那么有传递性。是否有用呢？证明：设结论不真。则所给的3元子集要么不交，要么恰有两个公共元

32、，如果子集与恰有两个公共元，则记。设是三个子集。可以证明如果，则，于是所有给定的3元子集可以分类，使得同一类中任意两个不同子集都恰有两个公共元。而不同类的子集不相交。于是对每个子集类，有三种可能：（1）恰含3个元素的类。（2）恰含4个元素的类。（3）至少含5个元素的类。在（1）下，3元子集类恰由一个3元子集组成。在（2）下，子集类中至多有4个子集。考虑（3） 设，则还有一个，由，有。因此对子集类中任意子集，由，它包含与，于是类中子集个数比类中元素个数少2，于是，每个类中子集个数不超过元素个数，但是题中条件子集数大于元素个数，矛盾！10 、 46个国家派代表参加亚洲数学竞赛，比赛共4题，结果统计如下：第一题对235人；一、二都对59人；一、三都对29人；一、四都对15人。四题全对的3人，有一人只错了第4题。求证：存在一个国家，这个国家派出的选手中至少有4人恰好只做对了第一题。解设集合A=全部选手，。可是由抽屉原理知46个国家中必存在一个国家，至少4人只做对第一题。