五年级数学竞赛第6讲 容斥原理VIP

第六讲 容斥原理在一些计数问题中，经常遇到有关集合元素个数的计算。我们用|A|表示有限集A的元素的个数。在两个集合的研究中，已经知道，求两个集合并集的元素个数，不能简单地把两个集合的元素个数相加，而要从两根集合的个数之中减去重复计算的元素个数，用式子可以表示成 |AB|=|A|+|B|AB|。【来源：21cnj*y.co*m】我们称这一公式为包含与排除原理，简称为容斥原理。包含与排除原理|告诉我们，要计算两个集合A、B的并集AB的元素个数，可以分一下两步进行：第一步：分别计算集合A、B的元素个数，然后加起来。即先求|A|+|B|（意思是把A、B的一切元素都“包含”进来，加在一起）；【出处：21教育名师】第二步“从上面的和中减去交集的元素的个数，即减去|AB|（意思是“排除”了重复计算的元素的个数）。【版权所有：21教育】例1求不超过20的正整数中是2的倍数或3的倍数的数共有多少？解：设I=1、2、3、19、20，A=I中2的倍数，B=I中3的倍数。显然题目中要求计算并集AB的元素个数，即求|AB|。我们知道A=2、4、6、20，所以|A|=10，B=3、6、9、12、15、18，|B|=6。AB=I中既是2的倍数又是3的倍数=6、12、18，所以|AB|=3，根据容斥原理有|AB|=|A|+|B|AB|=10+63=13.答：所求的数共有13个。此题可以直观地用图表示如下：例2某班统计考试成绩，数学得90分以上的有25人，语文得90分以上的有21人，两科中至少有一科在90分以上的有38人，问两科都在90分以上的有多少人？解：设A=数学在90分以上的学生，B=语文在90分以上的学生，由题意知|A|=25，|B|=21。AB=数学、语文至少一科在90分以上的学生，|AB|=38。AB=数学、语文都在90分以上的学生，由容斥原理知|AB|=|A|+|B|AB|，所以|AB |=|A|+|B|AB|=25+2138=8。答：两科都在90分以上的有8人。画图分析一下：其中A的人数是x+n=25，B的人数是y+n=21，AB的人数是x+n+y=38，求n等于多少？很明显n=(x+n)+(y+n)(x+y+n)=25+2138=8。例3如图所示，一个边长为2 的正方形与一个边长为3的正方形放在桌面上，它们所盖住的面积有多大？解：如果把两个正方形的面积加起来是32+22=9+4=13，就会发现多计算了一块阴影的面积，应该从上面的和中减去这一部分。21教育名师原创作品因此两个正方形所覆盖住的面积是32+221.52=132.25=10.75。例4有100位旅客，其中10人既不懂英语又不懂俄语，有75人懂英语，83人懂俄语。问既懂英语又懂俄语的有多少人？21*cnjy*com解：设A=懂英语的旅客，B=懂俄语的旅客，那么英语或俄语至少懂一种的旅客是AB，而两种语言都懂的旅客是AB。21由题意|A|=75，|B|=83，|AB|=10010=90，根据容斥原理得|AB|=|A|+|B|AB|=75+8390=68.答：两种语言都懂的旅客有68人。对于任意三个有限集合A、B、C，我们可以将上面的容斥原理推广得到如下的公式：|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC|。三个集合的容斥原理告诉我们要计算并集ABC的元素个数，可以分三步进行：第一步：求|A|+|B|+|C|；第二步：减去|AB|，|BC|，|CA|；第三步：加上|ABC|。结合下图作出说明。由于ABC可以有七个部分组成，其中I、II、III部分的元素仅属于某个集合，而IV、V、VI部分的元素分别属于某两个集合，第VII部分则是三个集合的交集。由于ABC的元素分别来自集合A、B、C，因此先计算|A|+|B|+|C|。在这个和里，第I、II、III部分的元素只计算了一次，而第IV、V、VI部分的元素各自计算了两次，第VII部分的元素计算了三次。21世纪*教育网在第二步中减去了|AB|，|BC|，|CA|后，得|A|+|B|+|C|AB|BC|AC|，这样显然消除了第IV、V、VI部分的元素的重复计算，但是请注意同时对第VII部分的元素是减去了三次，这样第VII部分的元素都被减去了，因此必须补回来，即再加上|ABC|。综上所述得|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC|。例5某校组织棋类比赛，分成围棋、中国象棋、国际象棋三个组进行。参加围棋比赛的有42人，参加中国象棋比赛的有51人，参加国际象棋比赛的有30人。同时参加围棋和中国象棋比赛的有13人，同时参加围棋和国际象棋比赛的有7人，同时参加中国象棋和国际象棋比赛的有11人，其中三种棋都参加的有3人。问参加棋类比赛的共有多少人？解：设A=参加围棋比赛的人，B=参加中国象棋比赛的人，C=参加国际象棋比赛的人。那么参加棋类比赛的人的集合为ABC。21cnjycom由题意知，|A|=42，|B|=51，|C|=30，又|AB|=13，|AC|=7，|BC|=11，|ABC|=3。根据容斥原理得|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC|=42+51+3013711+3=95（人）。答：参加棋类比赛的共有95人。画图来计算： A、B、C三个圆表示三个集合，先把三个圆相交的最中间部分填上3，由于同时参加围棋和中国象棋比赛的有13人，所以第IV部分应该是10人；同时参加中国象棋和国际象棋比赛的有11人，所以第V部分应该是8人；同时参加围棋和国际象棋比赛的有7人，所以第VI部分应该是4人；再根据参加围棋比赛的有42人，于是第I部分是421034=25人；参加中国象棋比赛的有51人，于是第II部分是511038=30人；参加国际象棋比赛的有30人。于是第III部分是30834=15人；由此得出参加棋类比赛的总人数是25+30+15+10+8+4+3=95（人）。例6边长分别为6、5、2的三个正方形，如图所示放在桌面上，问它们所盖住的面积是多大？解：设R表示正方形区域ABCD，M表示正方形区域A1B1C1D1，N表示正方形区域A2B2C2D2，则|R|=36，|M|=25，|N|=4，|RM|=9，|RN|=2，|MN|=2，|RMN|=1，所以|MMN|=|R|+|M|+|N|RM|RN|MN|+|RMN|=36+25+4922+1=53.答：三个正方形所盖住的面积是53.例7某班学生手中分别拿有红、黄、蓝三种颜色的球。已知手中有红球的共有34人，手中有黄球的共有26人，手中有篮球的共有18人，其中手中有红、黄、蓝三种球的有6人，而手中只有红、黄两种球的有9人，手中只有黄、蓝两种球的有4人，手中只有红、蓝两种球的有3人，那么这个班共有多少人？21教育网解：设A、B、C分别表示手中有、红球、黄球、篮球的人的集合，由题意，画出图来逐一填上人数计算。 最中间应该填上6，由手中只有红、黄两种球的有9人，手中只有红、蓝两种球的有3人，手中只有黄、蓝两种球的有4人，则在区域VI、V、VI中分别填上9、3、4。最后由手中有红球的共有34人，手中有黄球的共有26人，手中有篮球的共有18人，可以填出区域I、II、III内分别填上16、7、5。21世纪教育网版权所有所以全班共有16+7+5+9+3+4+6=50（人）。答：全班共有50人。解法2：设A、B、C分别表示手中有、红球、黄球、篮球的人的集合，则|A|=34，|B|=26，|C|=18，所以|A|+|B|+|C|=34+26+18=78，显然这样的计算中对于区域IV、V、VI的部分重复计算了一次（需要减去1次），而对于区域VII的部分重复计算了两次，也就是计算了三次（需要减去2次）。所以全班人数是34+26+18(9+4+3)26=50（人）。答：全班共有50人。例8求1到200的自然数中不能被2、3、5中任何一个数整除的数有多少个？解：设A=1到200中间能被2整除的自然数；B=1到200中间能被3整除的自然数；C=1到200中间能被5整除的自然数；那么AB=1到200中间能被23整除的自然数；AC=1到200中间能被25整除的自然数；BC=1到200中间能被35整除的自然数；ABC=1到200中间能被235整除的自然数；21*cnjy*com求出|A|=100，|B|=66，|C|=40，|AB|=33，|AC|=20，|BC|=13，|ABC|=6，所以|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC|=100+66+40332013+6=146.这是1到200中间的自然数至少有能被2、3、5中一个数整除的数的个数。 所以1到200的自然数中不能被2、3、5中任何一个数整除的数有200146=54（个）。练 习 题1某班有团员23人，这个班里男生共有20人，则这个班里女生团员比男生非团员多 人。解：设男生团员为x人，则女生团员为23x若，男生非团员为20x人，所以这个班里女生团员比男生非团员多(23x)(20x)=3（人）。答：这个班里女生团员比男生非团员多3人。2一张纸片的面积为7，另一张是边长为2的正方形纸片，把这两张纸片放在桌子上，覆盖的面积为8，则两张纸片重合部分的面积是 。www-2-1-cnjy-com解：设第一张纸片为A，第二张纸片为B，则|A|=7，|B|=4，|AB|=8，所以|AB|=7+48=3.答：两张纸片重合部分的面积是3.3从1到100的自然数中，（1）不能被6或10整除的数有 个；（2）至少能被2、3、5中一个数整除的数有 个。解：（1）设A=1到100中被6整除的数，B=1到100中被10整除的数， AB=1到100中被30整除的数，其中30是6与10的最小公倍数。则|A|=16，|B|=10，|AB|=3，所以|AB|=|A|+|B|AB|=16+103=23.在1到100中能被6或10整除的数有23个，不能被6或10整除的数有10023=77（个）。答：不能被6或10整除的数有77个。（2）设C=1到100中被2整除的数；D=1到100中被3整除的数；E=1到100中被5整除的数；CD=1到100中既能被2整除又能被3整除的数；CE=1到100中既能被2整除又能被5整除的数；DE=1到100中既能被3整除又能被5整除的数；CDE=1到100中同时能被2、3、5整除的数；2-1-c-n-j-y|C|=50、|D|=33，|E|=20，|CD|=16，|CE|=10，|DE|=6，|CDE|=3，所以|CDE|=|C|+|D|+|E|CD|CE|DE|+|CDE| =50+33+2016106+3=74（个）。答：至少能被2、3、5中一个数整除的数有74个。4盛夏的一天，有10个同学去冷饮店，向服务员交了一份需要冷饮的统计表：要可乐、雪碧、果汁的各有5人；可乐、雪碧都要的有3人；可乐、果汁都要的有2人；雪碧、果汁都要的有2人，三样都要的只有1人。证明：其中有1人这三种饮料都没有要。解：设A=要可乐的同学，B=要雪碧的同学，C=要果汁的同学，则|A|=5，|B|=5，|C|=5，|AB|=3，|AC|=2，|BC|=2，|ABC|=1，所以|ABC|=|A|+|B|+|C|AB|BC|AC|+|ABC| =5+5+5322+1=9（人）。可见一定有1人没有要饮料。5对100个学生课外学科活动的调查结果如下：32人参加数学小组；20人参加英语小组；45人参加生物小组。其中15人既参加了数学小组又参加了生物小组；7人既参加了英语小组又参加了数学小组；10人既参加了英语小组又参加了生物小组。还有30人没有参加上述任何一个学科小组。21cnjy（1）求三个学科小组都参加的人数；（2）在文氏图的8个小区域内填入相应的学生人数，其中A、B、C分别代表参加数学、英语、生物小组的学生的集合，被调查的100个学生的集合为全集I。解：（1）设A=参加数学小组的学生；B=参加英语小组的学生；C=参加生