第二十讲 容斥原理

word第二十讲容斥原理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人，并且每个人都至少参加了一个队，这个班两队都参加的有几个人？分析我们可以画一个图帮助思考，画两个相交的圆圈:其中一个表示体育代表队，另一个表示文艺代表队，那么两圆的内部共有42人，而体育代表队的圆中有30人，文艺代表队的图中有25人，但：30+25=5542，这是因为两队都参加的人被计算了两次，因此55-42=13，即是两队都参加的人数。解答 解：30+25-42=13人答：两队都参加的有13人。评注可能有很多同学还是刚刚接触容斥原理，所以我们用图形来形象地描绘整个问题。当容斥原理的题目做多了之后，很多根本的题目就不再需要一个一个的画图了。但是，当遇到复杂的问题时，图形还是帮助我们理解和解决问题的一个帮手。举一反三1、某班学生每人家里至少有空调和电脑两种电器中的一种，家中有空调的有41人，有电脑的有34人，二者都有的有27人，这个班有学生多少人？2、六年级共有96人，两种刊物每人至少订其中一种，有的人订少年报，有的人订数学报，两种刊物都订的有多少人？3、森林中住着很多动物，据说狮子大王派仙鹤去统计鸟的种数，蝙蝠跑去说：“我有翅膀，我算鸟类。仙鹤把蝙蝠统计进去了，结果得出森林中共有80种鸟类，狮子大王又派大象去统计兽类的种数，蝙蝠又跑去说：“我没有羽毛，我应该算兽类。大家又把蝙蝠算为兽类，统计出森林中共有70种兽类。最后狮子大王问：森林中共有鸟类和兽类多少种？狐狸军师听了仙鹤和大象的统计结果，向狮子大王报告：“森林中鸟类与兽类共计150种。听了上面的故事，请你说说狐狸军师这样统计对吗？为什么，正确的答案应该是多少种呢？ 思路拓展 例2在一个炎热的夏日，几个小朋友去冷饮店，每人至少要了一样冷饮，其中有6人要了冰棍，6人要了汽水，4人要了雪碧，只要冰棍和汽水的有3人，只要冰棍和雪碧的没有，只要汽水和雪碧的有1人；三样都要的有1人。问：共有几个小朋友去了冷饮店？分析：根据题意画图。解答方法一：人方法二：人答：共有10个小朋友去了冷饮店。评注这道题目变成了三种事件，我们仍然可以用图形来简单的描述。只要同学们能够明白每一种人的数量应该填在哪个空位里，题目就变得非常容易了。同学们还要注意的一点是，最外圈的6，6，4三个数，并不是指的数字所在X围里的人数，而是指的整个圆里即买了某种冷饮而并非只买这种冷饮的人数。另外，方法二里，为什么要减去12，同学们能明白吗？举一反三1， 三年级一班的同学们报名参加趣味体育运动会，比赛内容共三项，分别是跳绳、拍球跑和踢毽子，每个人至少报了一项。报跳绳的有15人，报拍球跑的有18人，报踢毽子的有20人，同时包跳绳和拍球跑的有8人，同时报跳绳和踢毽子的有5人，没有报了拍球跑和踢毽子，但是没报跳绳的同学。三样都报的有2人。那么三年级一班有多少名同学呢？2， 班里组织了一次语数外三科的小测验，每名同学都至少有一门得总分为，但是没有人拿到三个总分为。语文得总分为的有10人，数学得总分为的有20人，外语得总分为的有25人，语文数学都得总分为的有6人，数学外语都得总分为的有12人，语文外语都得总分为的有2人。那么全班一共有多少人？3， 一次中、美、俄三方的学术交流会上，有28人会说中文，有25人会说英文，有20人会说俄文，有13人会说中文和英文，有10人会说中文和俄文，有6人会说英文和俄文，仅有大会组织者一人三种语言全会。那么这次交流会一共有多少人参与？例3 某班同学参加升学考试，得总分为的人数如下：数学20人，语文20人，英语20人，数学、英语两科总分为者8人，数学、语文两科总分为者7人，语文、英语两科总分为者9人，三科都没得总分为者3人。问这个班最多多少人？最少多少人？ 分析分析与解：根据题意画图。解答 设三科都得总分为者为x全班人数整理后：全班人数39x 39+x表示全班人数，当x取最大值时，全班人数就最多，当x取最小值时，全班人数就最少。x是数学、语文、英语三科都得总分为的同学，因而x中的人数一定不超过两科得总分为的人数，即且，由此我们得到。另一方面x最小可能是0，即没有三科都得总分为的。当x取最大值7时，全班有人，当x取最小值0时，全班有39人。答：这个班最多有46人，最少有39人。评注这道题目里，我们不知道三科都得总分为者的人数，也就无法直接用容斥原理来计算班里的总人数。但是我们可以假设出三科都得总分为的人数，再利用包含原如此，即三科都得总分为的人数不能小于0，也不能超过某两科得总分为的人数，从而确定了三科都总分为的人数的一个X围，再代入全班人数的计算式子，便可得出最多的人数与最少的人数。遇到这种需要假设的题目，同学们一定要注意设，并且要知道设哪个。如果这道题目假设了语文、数学得总分为但英语没得总分为的人数，虽然也能计算，但是会麻烦很多。举一反三1， 在四年级二班里，有25名男生，有30名少先队员，有13名三好学生。男少先队员有12人，男三好学生有6人，少先队员里的三好学生有5人，有3名女生既不是少先队员又不是三好学生。那么四年级二班最少有多少人，最多有多少人？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个。那么小玉最少写下了几个数？最多又写下了几个呢？例4有28人参加田径运动会，每人至少参加跑、跳、投中的两种比赛。有8人没参加跑的项目，参加投掷项目的人数与参加跑和跳两项的人数都是17人。问：只参加跑和投掷两项的有多少人？分析“每人至少参加两项比赛说明没有不参加的，也没有参加一项比赛的，我们可以在如下图中参加一项的区域用0表示。解答人答：只参加跑和投掷两项的有3人。评注在画出象形图并且标注了各个区域的人数和需要求的区域的人数之后，题目就变得很清楚了。当然，这道题目也可以这么想：只参加跑和投掷的，就是没有参加跳的项目的人数。而参加了跳类项目的人数，又可以分为参加了跑的和没参加跑的，后者就是只参加了跳和投掷的人数，前者就是参加了跑和跳的人数。这样也能计算出结果，但是毕竟不如我们画图来得清晰与直接。举一反三1， 有28人参加田径运动会，没有人同时参加跑、跳、投三种比赛。有20人参加了跑的项目，参加投掷项目的人数与参加跑和跳两项的人数都是10人，只参加跳项目的有5人。问：只参加跑和投掷两项的有多少人？2， 56名小朋友，每名小朋友胸前都戴着红、白、蓝三种颜色的花，每人每种花至多戴一朵。有30名小朋友戴了红花，有15名小朋友戴了白花和蓝花，只戴一种花的有21人，他们中戴每个颜色的花的人数都一样。那么有多少名小朋友三种花都戴了呢？3， 一次聚会，对参与聚会的人规定，如果穿了西服，打了领带，如此必须穿黑皮鞋。来的50人里穿西服、打领带、穿黑皮鞋的各有20人，穿西服和黑皮鞋的有12人，穿黑皮鞋打领带但是没有穿西服的有6人。那么有多少人没穿西服，没打领带，并且没穿黑皮鞋？例5某校六年级二班有49人参加了数学、英语、语文学习小组，其中数学有30人参加，英语有20人参加，语文小组有10人。教师告诉同学既参加数学小组又参加语文小组的有3人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有1人，求既参加英语又参加数学小组的人数。分析根据条件画出图。解答三圆盖住的总体为49人，假设既参加数学又参加英语的有x人，既参加语文又参加英语的有y人，可以列出这样的方程：整理后得：由于x、y均为质数，因而这两个质数中必有一个偶质数2，另一个质数为7。答：既参加英语又参加数学小组的为2人或7人。评注所以，我们应该按容斥原理的方法来解决此问题。用容斥原理的那一个呢？想一想，被计数的事物有那几类？每一类的元素个数是多少？另外，这道题目也帮助我们复习了质数与合数的概念和性质。举一反三1， 某校五年级三班有51人参加了数学、英语、语文学习小组，其中数学有30人参加，英语有20人参加，语文小组有20人。教师告诉同学既参加数学小组又参加语文小组的有8人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有1人，求既参加英语又参加数学小组的人数。2， 27块立方体，每个都用红、黄、蓝三种颜料中的一种或几种涂上了色。涂了红色的有21块，涂了黄色和蓝色的立方体个数都各自是一个整数的平方。同时涂了红、黄两色的有10块，同时涂了黄、蓝两色的有3块，同时涂了红、蓝两色的有2块。仅有一块立方体三种颜色都涂了。那么有多少块涂了黄色呢？3， 有20名同学，爱唱歌的有8人，爱跳舞的有9人，爱演奏乐器的有10人，爱唱歌跳舞的有5人，爱唱歌和演奏乐器的有4人，爱跳舞和演奏乐器的有5人。三种都爱的和三种都不爱的同学的个数都是一个质数，那么有多少名同学至少有一个爱好？例6 有25人参加跳远达标赛，每人跳三次，每人至少有一次达到优秀。第一次达到优秀的有10人，第二次达到优秀的有13人，第三次达到优秀的有15人，三次都达到优秀的只有1人。只有两次达到优秀的有多少人？分析“每人至少有一次达到优秀说明没有三次都没达到优秀的。要求只有两次达到优秀的人数，就是求重叠两层的局部图中阴影局部。 解答人答：只有两次达到优秀的有11人。评论这道题目，图形对我们的帮助依然很大。通过画图，我们就可以清晰地看出如何在容斥中进展扣除。准确地画出“只有两次达到优秀的人数在图中的位置，是解决此问题的关键。举一反三1、学校先后举行数学、作文、自然三科竞赛，某班有25人报名参加。其中14人参加数学竞赛，12人参加作文竞赛，10人参加自然竞赛，并且有4人参加数学作文两科竞赛，有2人参加数学、自然两科竞赛；只有1人三科竞赛都参加。问有多少人参加作文、自然两科的竞赛？2、有A、B、C三本书，至少读过其中一本的有20人，读过A书的有10人，读过B书的有12人，读过C书的有15人，读过A、B两书的有12人，读过B、C两书的有9人，读过A、C两书的有7人，三本书全都读过有多少人？3、某班四年级时，五年级时和六年级时分别评出10名三好学生，又知四、五年级连续三好生4人，五、六年级连续三好生3人，四年级、六年级两年评上三好生的有5人，四、五、六三年没评过三好生的有20人，问这个班最多有多少名同学，最少有多少名同学？例7 在1到1000的自然数中，能被3或5整除的数共有多少个？不能被3或5整除的数共有多少个？分析显然，这是一个重复计数问题当然，如果不怕麻烦你可以分别去数3的倍数，5的倍数。我们可以把“能被3或5整除的数分别看成A类元素和B类元素，能“同时被3或5整除的数15的倍数就是被重复计算的数，即“既是A类又是B类的元素。求的是“A类或B类元素个数。现在我们还不能直接计算，必须先求出所需条件。10003=3331，能被3整除的数有333个。同理，可以求出10005=200，能被5整除的数有200个。可以求出100015=6610，能被15整除的数有66个。解答333+200-66=467(个)1000+66-333-200=533(个)答：在1到1000的自然数中，能被3或5整除的数共有467个；不能被3或5整除的数共有533个。评注这样的题目在考试中经常会出现。被什么数整除，其实等于既告诉了各自集合的元素个数，也告诉了公共局部的元素个数。此外，这道题目和数论还要一些联系，同学们要注意知识的关联呦。举一反三1、在1到10000这10000个自然数中，即不能被8整除也不能被125整除的数有多少个？2、分母是1001的最简分数一共有多少个？3、求在1100的自然数中不是5的倍数也不是6的倍数的数有多少个？例850名学生面向教师站成一行，按教师的口令从左往右依次报数：1、2、350。报完后，教师让所报数是4的倍数的同学向后转，接着又让所报数是6的倍数的同学向后转。问：现在仍然面向教师的有多少名同学？分析 面向教师的学生有两种情况：一是两次都没有向后转的学生；二是两次都向后转的学生。所以此题可求出只向后转一次的学生数，用学生总数减去这个数字就可得出结果。解答因为504=12.5，即1至50这50个数中，有12个数是4的倍数。同样，506=82，即这些数中，有8个数是6的倍数。但5012=42，即这些数中，有4个数既是4的倍数又是6的倍数。所以，向后转一次的学生数=12+8-4=16名 最后面向教师的学生数=50-16=34名答：还有34名学生面向教师。评注这道题目将不单单是求两次都转向或者是两次都不转向的同学人数。由于转向的特殊性，需要求这两类同学的人数和。当然，这仍然只需要利用公式将每一局部的人数求出再求和即可。当总人数增多时，必须利用容斥原理才能得出结论。举一反三1， 20名学生面向教师站成一行，按教师的口令从左往右依次报数：1、2、320。报完后，教师让所报数是3的倍数的同学向后转，接着又让所报数是质数的同学向后转。问：现在仍然面向教师的有多少名同学？2， 200名学生，每名学生有一个学号，分别是1、2、3200。现在他们全部面对教学楼站好，接着让学号是4的倍数的同学向后转，接着又让学号是5的倍数的同学向后转，接着再让学号是6的倍数的同学向后转。问：现在仍然面向教学楼的有多少名同学？3， 马路上有40盏灯连成一排，每盏灯的底下都有一个开关，现在所有灯都是亮着的。小成从第一盏灯数起，每隔4盏灯就按一盏灯的开关。等小成按完后，小亮也从第一盏灯数起，每隔3盏灯就按一盏灯的开关。当他们都按完后，还有多少盏灯是亮的？例9在一根长的木棍上有三种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份，第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段？分析很显然，要计算木棍被锯成多少段，只需要计算出木棍上共有多少条不同的刻度线，在此根底上加1就是段数了。假如按将木棍分成10等份的刻度线锯开，木棍有9条刻度线。在此木棍上加上将木棍分成12等份的11条刻度线，显然刻度线有重复的，如5/10和6/12都是1/2。同样再加上将木棍分成15等份的刻度线，也是如此。所以，我们应该按容斥原理的方法来解决此问题。解答第一种和第二种刻度线重合的次数为(10,12)-1=1次第二种和第三种刻度线重合的次数为(12,15)-1=2次第一种和第三种刻度线重合的次数为(10,15)-1=4次三种刻度线一起重合的次数为(10,12,15)-1=0次因此最后实际上有(10-1)+(12-1)+(15-1)-1-2-4+0=27条刻度线因此木棍一共被锯成了27+1=28段答：木棍总共被锯成28段。评注这道题目不但要注重容斥原理的使用，还要注意计算每种刻度线的个数时存在一个植树问题，这实际上也是两类数学问题的结合。举一反三1、文宫中心校参加大型团体操的同学共240名，他们面对教练站成一排，自左至右按1，2，3，4依次报数，教练让每个同学记住自己报的数，并做以下动作：先让报数是3的倍数的学生向后转，接着又让报数是5的倍数的学生向后转，最后让报数是7的倍数的学生向后转，问此时还有多少名学生面对教练？2、边长为2的正方形与边长为3的正方形，如下列图放在桌面上，它们所盖住的面积有多大？3、边长分别为6，5，2的三个正方形，如下列图放在桌面上。问它们盖住的面积是多大？ 本章小结容斥原理说简单点,就是从多的往下减,减过头了在加回来,加多了再减,减多了再加,最终得到正确结果。对于计数中容易出现重复的题目,我们常常采用容斥原理,去掉重复的情况。 同学们在使用容斥原理时，必须要分析清楚不同类的元素。对于有两类元素的问题，要分清：哪些是A类元素？哪些是B类元素？哪些既是A类又是B类的元素？对于有两类元素的问题，如此要分清：哪些是A类元素？哪些是B类元素？哪些是C类元素？哪些既是A类又是B类的元素？哪些既是A类又是C类的元素？哪些既是B类又是C类的元素？哪些既是A类又是B类而且是C类的元素？这样，才能够正确地解决问题。本章自测1、某大学某班学生总数为32人，在第一次考试中有26人与格，在第二次考试中有24人与格，假如两次考试中，都没有与格的有4人，那么两次考试都与格的人数是多少？2、一次期末考试，某班有15人数学得总分为，有12人语文得总分为，并且有4人语、数都是总分为，那么这个班至少有一门得总分为的同学有多少人？3、在100个学生中，爱好音乐的有58人，爱好体育的有75人。那么，既爱好音乐又爱好体育的，至少有多少人？至多有多少人？ 4、某班45名同学参加体育测试，其中百米得优者20人，跳远得优者18人，又知百米、跳远都得优者7人，跳高、百米得优者6人，跳高、跳远均得优者8人，跳高得优者22人，全班只有1名同学各项都没达优秀，求三项都是优秀的人数。5、某班学生手中分别拿有红、黄、蓝三种颜色的球。手中有红球的共有34人，手中有黄球的共有26人，手中有蓝球的共有18人。其中手中有红、黄、蓝三种球的有6人。而手中只有红、黄两种球的有9人，手中只有黄、蓝两种球的有4人，手中只有红、蓝两球的有3人，那么这个班共有多少人？6、有40名运动员，其中有25人会摔跤，有20人会击剑，有10人击剑、摔跤都不会，问既会摔跤、又会击剑的运动员有多少人？7、某次语文竞赛共有五道题总分为不是100分，丁一只做对了1、2、3三题得了16分；于山只做对了2、3、4三题，得了25分；王水只做对了3、4、5三题，得了28分，X灿只做对了1、2、5三题，得了21分，李明五个题都对了他得了多少分？8、某校六1班有学生54人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有34人，足球、排球都参加的有12人，足球、游泳都参加的有18人，排球、游泳都参加的有14人，问：三项都参加的有多少人？9、某校参加数学竞赛有120名男生，80名女生，参加语文竞赛的有120名女生，80名男生，该校总共有260名学生参加竞赛，其中75名男生两科教参加了，那么只参加数学竞赛而没有参加语文竞赛的女生有多少人？10、某单位有青年员工85人，其中68人会骑自行车，62人会游泳，既不会骑车又不会游泳的有12人，如此既会骑车又会游泳的有多少人11、六一班60名同学，参加乒乓球赛的40人，参加足球赛的45人，参加篮球赛的48人，三项都参加的22人，问至多有几人三项都未参加？12、电视台向100人调查前一天收看电视的情况，有62人看过2频道，34人看过8频道，11人两个频道都看过。两个频道都没看过的有多少人？13、对某单位的100名员工进展调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，如此只喜欢看电影的有多少人？14、某校组织棋类比赛，分成围棋、中国象棋和国际象棋三个组进展。参加围棋比赛的共有42人，参加中国象棋比赛的共有51人，参加国际象棋比赛的共有30人。同时参加了围棋和中国象棋比赛的共有13人，同时参加了围棋和国际象棋比赛的7人，同时参加了中国象棋和国际象棋比赛的11人，其中三种棋赛都参加的3人。问参加棋类比赛的共有多少人？15、某年级的课外小组分为美术、音乐、手工三个小组，参加美术小组有20人，参加音乐小组有24人，参加手工小组有31人，同时参加美术和音乐两个小组有5人，同时参加音乐和手工两个小组有6人，同时参加美术和手工两个小组的有7人，三个小组都参加的有3人，这个年级参加课外小组的同学共有多少人?16、某校有学生960人，其中510人订阅中国少年报，330人订阅少年文艺；120人订阅中小学数学报；其中有270人订阅两种报刊，有58人订阅三种报刊。问这个学校没有订阅任何报刊的学生有多少人？17、某大学有外语教师120名，其中教英语的有50名，教日语的有45名，教法语的有40名，有15名既教英语又教日语，有10名既教英语又教法语，有8名既教日语又教法语，有4名教英语、日语和法语三门课，如此不教三门课的外语教师有多少名？18、从1到100的自然数中，1不能被6和10整除的数有多少个？2至少能被2，3，5中一个数整除的数有多少个？19、分母是385的最简真分数共有多少个？20、一次会议有1990名数学家参加，每人至少有1327位合作者，求证：可以找到4个数学家，他们中每两个人都合作过。9 / 9