第二十讲-容斥原理

《第二十讲-容斥原理》由会员分享，可在线阅读，更多相关《第二十讲-容斥原理（13页珍藏版）》请在金锄头文库上搜索。

1、如果您需要使用本文档，请点击下载按钮下载!第二十讲 容斥原理（2）知识提要前面讲述过简单的容斥原理，“容”就是相容，相加，而“斥”就是相斥，相减，容斥原理作为一种计数方法，说简单点，就是从多的往下减，减过头了在加回来，加多了再减，减多了再加最终得到正确结果。对于计数中容易出现重复的题目，我们常常采用容斥原理，去掉重复的情况。应用于计数集合划分有重叠，无法简单应用加法原理的情况下。在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重

2、复，这种计数的方法称为容斥原理。如果被计数的事物有A、B两类，那么，具体公式为:A类或B类元素个数= A类元素个数+ B类元素个数既是A类又是B类的元素个数。如果被计数的事物有A、B、C三类，那么，具体公式为:A类或B类或C类元素个数= A类元素个数+ B类元素个数+C类元素个数既是A类又是B类的元素个数既是A类又是C类的元素个数既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。有了以上的容斥原理,一些看起来头绪很多的问题就可以比较方便地得到解决。 经典例题 例1五（1）班有学生42人，参加体育代表队的有30人，参加文艺代表队的25人，并且每个人都至少参加了一个队，这个班两队都

3、参加的有几个人？分析我们可以画一个图帮助思考，画两个相交的圆圈:其中一个表示体育代表队，另一个表示文艺代表队，那么两圆的内部共有42人，而体育代表队的圆中有30人，文艺代表队的图中有25人，但：30+25=5542，这是因为两队都参加的人被计算了两次，因此55-42=13，即是两队都参加的人数。解答 解：（30+25）-42=13（人）答：两队都参加的有13人。评注可能有很多同学还是刚刚接触容斥原理，所以我们用图形来形象地描绘整个问题。当容斥原理的题目做多了之后，很多基本的题目就不再需要一个一个的画图了。但是，当遇到复杂的问题时，图形还是帮助我们理解和解决问题的一个帮手。举一反三1、某班学生每

4、人家里至少有空调和电脑两种电器中的一种，已知家中有空调的有411 / 12如果您需要使用本文档，请点击下载按钮下载!人，有电脑的有34人，二者都有的有27人，这个班有学生多少人？2、六年级共有96人，两种刊物每人至少订其中一种，有的人订少年报，有的人订数学报，两种刊物都订的有多少人？3、森林中住着很多动物，据说狮子大王派仙鹤去统计鸟的种数，蝙蝠跑去说：“我有翅膀，我算鸟类。”仙鹤把蝙蝠统计进去了，结果得出森林中共有80种鸟类，狮子大王又派大象去统计兽类的种数，蝙蝠又跑去说：“我没有羽毛，我应该算兽类。”大家又把蝙蝠算为兽类，统计出森林中共有70种兽类。最后狮子大王问：森林中共有鸟类和兽类多少种

5、？狐狸军师听了仙鹤和大象的统计结果，向狮子大王报告：“森林中鸟类与兽类共计150种。”听了上面的故事，请你说说狐狸军师这样统计对吗？为什么，正确的答案应该是多少种呢？ 思路拓展 例2在一个炎热的夏日，几个小朋友去冷饮店，每人至少要了一样冷饮，其中有6人要了冰棍，6人要了汽水，4人要了雪碧，只要冰棍和汽水的有3人，只要冰棍和雪碧的没有，只要汽水和雪碧的有1人；三样都要的有1人。问：共有几个小朋友去了冷饮店？ 分析：根据题意画图。 解答方法一：（人） 方法二：（人） 答：共有10个小朋友去了冷饮店。评注这道题目变成了三种事件，我们仍然可以用图形来简单的描述。只要同学们能够明白每一种人的数量应该填在

6、哪个空位里，题目就变得非常容易了。同学们还要注意的一点是，最外圈的6，6，4三个数，并不是指的数字所在范围里的人数，而是指的整个圆里（即买了某种冷饮而并非只买这种冷饮）的人数。另外，方法二里，为什么要减去12，同学们能明白吗？举一反三1， 三年级一班的同学们报名参加趣味体育运动会，比赛内容共三项，分别是跳绳、拍球跑和踢毽子，每个人至少报了一项。报跳绳的有15人，报拍球跑的有18人，报踢毽子的有20人，同时包跳绳和拍球跑的有8人，同时报跳绳和踢毽子的有5人，没有报了拍球跑和踢毽子，但是没报跳绳的同学。三样都报的有2人。那么三年级一班有多少名同学呢？2， 班里组织了一次语数外三科的小测验，每名同学

7、都至少有一门得满分，但是没有人拿到三个满分。语文得满分的有10人，数学得满分的有20人，外语得满分的有25人，语文数学都得满分的有6人，数学外语都得满分的有12人，语文外语都得满分的有2人。那么全班一共有多少人？3 / 12如果您需要使用本文档，请点击下载按钮下载!3， 一次中、美、俄三方的学术交流会上，有28人会说中文，有25人会说英文，有20人会说俄文，有13人会说中文和英文，有10人会说中文和俄文，有6人会说英文和俄文，仅有大会组织者一人三种语言全会。那么这次交流会一共有多少人参与？例3 某班同学参加升学考试，得满分的人数如下：数学20人，语文20人，英语20人，数学、英语两科满分者8人

8、，数学、语文两科满分者7人，语文、英语两科满分者9人，三科都没得满分者3人。问这个班最多多少人？最少多少人？ 分析 分析与解：根据题意画图。解答 设三科都得满分者为x 全班人数 整理后：全班人数39x 39+x表示全班人数，当x取最大值时，全班人数就最多，当x取最小值时，全班人数就最少。x是数学、语文、英语三科都得满分的同学，因而x中的人数一定不超过两科得满分的人数，即且，由此我们得到。另一方面x最小可能是0，即没有三科都得满分的。 当x取最大值7时，全班有人，当x取最小值0时，全班有39人。答：这个班最多有46人，最少有39人。评注这道题目里，我们不知道三科都得满分者的人数，也就无法直接用容

9、斥原理来计算班里的总人数。但是我们可以假设出三科都得满分的人数，再利用包含原则，即三科都得满分的人数不能小于0，也不能超过某两科得满分的人数，从而确定了三科都满分的人数的一个范围，再代入全班人数的计算式子，便可得出最多的人数与最少的人数。遇到这种需要假设的题目，同学们一定要注意设，并且要知道设哪个。如果这道题目假设了语文、数学得满分但英语没得满分的人数，虽然也能计算，但是会麻烦很多。举一反三1， 在四年级二班里，有25名男生，有30名少先队员，有13名三好学生。男少先队员有12人，男三好学生有6人，少先队员里的三好学生有5人，有3名女生既不是少先队员又不是三好学生。那么四年级二班最少有多少人，

10、最多有多少人？2， 某公司的员工为地震灾区捐款、献血和游行鼓励，每位员工至少参加了一项。捐款的有40人，献血的有35人，游行的有25人，捐款、献血但是没有游行的有8人，捐款、游行但是没有献血的有12人，同时献血和游行的有10人。那么这个公司最少有多少名员工，最多又有多少名呢？3， 小玉在黑板上写下了一些数，其中每个数都至少能被2、3、5之一整除。被2整除的数有10个，被3整除的数有9个，被5整除的数有6个。被2、3整除但是不被5整除的有4个，被2、5整除但是不被3整除的有3个、被3、5整除但是不被2整除的有2个。那么小玉最少写下了几个数？最多又写下了几个呢？3 / 12如果您需要使用本文档，请

11、点击下载按钮下载!例4有28人参加田径运动会，每人至少参加跑、跳、投中的两种比赛。已知有8人没参加跑的项目，参加投掷项目的人数与参加跑和跳两项的人数都是17人。问：只参加跑和投掷两项的有多少人？ 分析“每人至少参加两项比赛”说明没有不参加的，也没有参加一项比赛的，我们可以在下图中参加一项的区域用0表示。 解答 （人） 答：只参加跑和投掷两项的有3人。评注在画出象形图并且标注了各个区域的人数和需要求的区域的人数之后，题目就变得很清楚了。当然，这道题目也可以这么想：只参加跑和投掷的，就是没有参加跳的项目的人数。而参加了跳类项目的人数，又可以分为参加了跑的和没参加跑的，后者就是只参加了跳和投掷的人数

12、，前者就是参加了跑和跳的人数。这样也能计算出结果，但是毕竟不如我们画图来得清晰与直接。举一反三1， 有28人参加田径运动会，没有人同时参加跑、跳、投三种比赛。已知有20人参加了跑的项目，参加投掷项目的人数与参加跑和跳两项的人数都是10人，只参加跳项目的有5人。问：只参加跑和投掷两项的有多少人？2， 56名小朋友，每名小朋友胸前都戴着红、白、蓝三种颜色的花，每人每种花至多戴一朵。有30名小朋友戴了红花，有15名小朋友戴了白花和蓝花，只戴一种花的有21人，他们中戴每个颜色的花的人数都相同。那么有多少名小朋友三种花都戴了呢？3， 一次聚会，对参与聚会的人规定，如果穿了西服，打了领带，则必须穿黑皮鞋。

13、来的50人里穿西服、打领带、穿黑皮鞋的各有20人，穿西服和黑皮鞋的有12人，穿黑皮鞋打领带但是没有穿西服的有6人。那么有多少人没穿西服，没打领带，并且没穿黑皮鞋？例5某校六年级二班有49人参加了数学、英语、语文学习小组，其中数学有30人参加，英语有20人参加，语文小组有10人。老师告诉同学既参加数学小组又参加语文小组的有3人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有1人，求既参加英语又参加数学小组的人数。 分析根据已知条件画出图。4 / 12如果您需要使用本文档，请点击下载按钮下载! 解答三圆盖住的总体为49人，假设既参加数学又参加英语的有x人，既参加语文又

14、参加英语的有y人，可以列出这样的方程： 整理后得： 由于x、y均为质数，因而这两个质数中必有一个偶质数2，另一个质数为7。 答：既参加英语又参加数学小组的为2人或7人。评注所以，我们应该按容斥原理的方法来解决此问题。用容斥原理的那一个呢？想一想，被计数的事物有那几类？每一类的元素个数是多少？另外，这道题目也帮助我们复习了质数与合数的概念和性质。举一反三1， 某校五年级三班有51人参加了数学、英语、语文学习小组，其中数学有30人参加，英语有20人参加，语文小组有20人。老师告诉同学既参加数学小组又参加语文小组的有8人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有1

15、人，求既参加英语又参加数学小组的人数。2， 27块立方体，每个都用红、黄、蓝三种颜料中的一种或几种涂上了色。已知涂了红色的有21块，涂了黄色和蓝色的立方体个数都各自是一个整数的平方。同时涂了红、黄两色的有10块，同时涂了黄、蓝两色的有3块，同时涂了红、蓝两色的有2块。仅有一块立方体三种颜色都涂了。那么有多少块涂了黄色呢？3， 有20名同学，爱唱歌的有8人，爱跳舞的有9人，爱演奏乐器的有10人，爱唱歌跳舞的有5人，爱唱歌和演奏乐器的有4人，爱跳舞和演奏乐器的有5人。三种都爱的和三种都不爱的同学的个数都是一个质数，那么有多少名同学至少有一个爱好？例6 有25人参加跳远达标赛，每人跳三次，每人至少有一次达到优秀。第一次达到优秀的有10人，第二次达到优秀的有13人，第三次达到优秀的有15人，三次都达到优秀的只有1人。只有两次达到优秀的有多少人？ 分析“每人至少有一次达到优秀”说明没有三次都没达到优秀的。要求只有两次达到优秀的人数，就是求重叠两层的部分（图中阴影部分）。 5 / 12如果您需要使用本文档，请点击下载按钮下载! 解答（人） 答：只有两次达到