施久亮容斥原理

浙大公务员辅导网 www.zjgwyks.com 容斥原理 一、    知识要点 1、容斥原理   在计数时，常常遇到这样的情况，作合并运算时会把重复的部分多算，需要减去；作排除运算时会把重复部分多减，需要加上，这就是容斥原理。它的基本形式是：   记A、B是两个集合，属于集合A的东西有 个，属于集合B的东西有 个，既属于集合A又属于集合B的东西记为 ，有 个；属于集合A或属于集合B的东西记为 ，有 个，则有： = + - 容斥原理可以用一个直观的图形来解释。如图， 左圆 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示集合A，右圆表示集合B，两圆的公共部分表示 ，两圆合起来的部分表示 ， 由图可知： = + - 容斥原理又被称作包含排除原理或逐步淘汰原则。 二、    例题精讲 例1 在1到200的整数中，既不能被2整除，又不能被3整除的整数有多少个？ 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ：根据容斥原理，应是200减去能被2整除的整数个数，减去能被3整除的整数个数，还要加上既能被2整除又能被3整除，即能被6整除的整数个数。 100，共100个；(2，…，2(1，2(解：在1到200的整数中，能被2整除的整数个数为：2   66，共66个；(2，…，3(1，3(在1到200的整数中，能被3整除的整数个数为：3 在1到200的整数中，既能被2整除又能被3整除，即能被6整除的整数个数为： 33，共33个；(2，…，6(1，6(6 所以，在1到200的整数中，既不能被2整除，又不能被3整除的整数个数为： 200-100-66+33=67(个) 例2 求1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S。 解：1到100的自然数中，所有自然数的和是：1+2+3+…+100=5050 1到100的自然数中，所有2的倍数的自然数和是： (1+2+3+…+50)=(50=2(2+…+2(1+2(2 1275=2550(2 1到100的自然数中，所有3的倍数的自然数和是： (1+2+3+…+33)=(33=3(2+…+3(1+3(3 561=1683(3 (1+2+3+…+16)=(16=6(2+…+6(1+6(1到100的自然数中，所有既是2的倍数又是3的倍数，即是6的倍数的自然数和是：6 136=816(6 所以，1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和 S=5050-2550-1683+816=1633 例3求不大于500而至少能被2、3、5中一个整除的自然数的个数。 分析：如图，用3个圆A、B、C分别表示不大于500而 能被2、3、5整除的自然数，   表示既能被2整除又能被3整除的自然数   表示既能被2整除又能被5整除的自然数   表示既能被3整除又能被5整除的自然数   表示既能被2整除又能被3整除，还能 被5整除的自然数 由图可看出：属于A、B、C之一的数的个数为： + + -( + + )+ 解：不大于500且能被2整除的自然数的个数是：250 不大于500且能被3整除的自然数的个数是：166 不大于500且能被5整除的自然数的个数是：100 不大于500既能被2整除又能被3整除，即能被6整除的自然数的个数是：83 不大于500既能被2整除又能被5整除，即能被10整除的自然数的个数是：50 不大于500既能被3整除又能被5整除，即能被15整除的自然数的个数是：33 不大于500既能被2整除又能被3整除，还能被5整除，即能被30整除的自然数的个数是：16 由容斥原理得：不大于500而至少能被2、3、5中一个整除的自然数的个数是：         250+166+100-(83+50+33)+16=366 例4 求前200个正整数中，所有非2、非3、非5的倍数的数之和。 解：前200个正整数的和是：1+2+3+…+200=20100 前200个正整数中，所有2的倍数的正整数和是： (1+2+3+…+100)=(100=2(2+…+2(1+2(2 5050=10100(2 前200个正整数中，所有3的倍数的正整数和是： (1+2+3+…+66)=(66=3(2+…+3(1+3(3 6633 前200个正整数中，所有5的倍数的正整数和是： (1+2+3+…+40)=(40=5(2+…+5(1+5(5 4100 (1+2+3+…+33)=(33=6(2+…+6(1+6(前200个正整数中，所有既是2的倍数又是3的倍数，即是6的倍数的正整数和是：6 3366 (1+2+3+…+20)=(33=10(2+…+10(1+10(前200个正整数中，所有既是2的倍数又是5的倍数，即是10的倍数的正整数和是：10 2100 (1+2+3+…+13)=(13=15(2+…+15(1+15(前200个正整数中，所有既是3的倍数又是5的倍数，即是15的倍数的正整数和是：15 1365 (1+2+3+4+5+6)=(6=30(2+…+30(1+30(前200个正整数中，所有既是2的倍数又是3的倍数还是5的倍数，即是30的倍数的正整数和是：30 630 所以，前200个正整数中，所有非2、非3、非5的倍数的数之和是 S=20100-(10100+6633+4100)+(3366+2100+1365)-630=630 例5 某班的全体学生进行了短跑、游泳、篮球三个项目的测试，有4名学生在这三个项目都没有达到优秀，其余每人至少有一个项目达到优秀，这部分学生达到优秀的项目、人数如下表： 短跑    游泳    篮球    短跑、 游泳    游泳、 篮球    篮球、 短跑    短跑、游泳、篮球 17    18    15    6    6    5    2 求这个班的学生数。(第三届华杯赛复赛试题) 解：有4名学生在这三个项目都没有达到优秀，在每个单项上达到优秀的人数分别是17、18、15，因而，总人数是17+18+15+4=54。 但其中有人获得两项优秀，所以上面的计数产生了重复，重复人数应当减去，即总人数变为：54-6-6-5=37 又考虑到获得三项优秀的人，他们一开始被重复计算了三次，但在后来又被重复减去了三次，所以最后还要将他们加进去。即这个班学生数为：37+2=39。 例6 从1到1000000这一百万个自然数中，能被11整除而不能被13整除的数多还是能被13整除而不能被11整除的数多？(第20届全俄九年级试题) 解：设1到1000000这一百万个自然数中，能被11整除而不能被13整除的数有m个，   能被13整除而不能被11整除的数有n个，既能被11又能被13整除的数有p个。   而在1到1000000这一百万个自然数中，能被11整除数有90909个，∴m+p=90909   在1到1000000这一百万个自然数中，能被13整除数有76923个，∴n+p=76923   ∴m+p> n+p   ∴m>n，即能被11整除而不能被13整除的数比能被13整除而不能被11整除的数多。 例7 50名学生面向老师站成一行，老师先让大家从左到右按1，2，3，…依次报数，再让报数是4的倍数的同学向后转，接着又让报数是6的倍数同学向后转，问此时还有多少同学面向老师？(1995年华杯赛试题) 分析：首先没有转的同学仍面向老师，即报数既不是4的倍数，也不是6的倍数的同学仍面向老师，其次，报数既是4的倍数，也是6的倍数，即是12的倍数同学连续转了两次，仍面向老师。 解：报数是4的倍数的同学有12个，报数是6的倍数的同学有8个，报数是12的倍数的同学有4个， 所以根据容斥原理得：报数既不是4的倍数，也不是6的倍数的同学有50-12-8+4=34个。 报数既是4的倍数，也是6的倍数，即是12的倍数同学有4个。 所以此时还应有34+4=38个同学面向老师。 评注：若将同学数50改成n，问此时还有多少同学面向老师？ 可以得出一个一般的结论： 例8 已知某校共有学生900名，其中男生528人，高中学生312人，团员670人，高中男生192人，男团员336人，高中团员247人，高中男团员175人，试问这些数据统计有无错误？ 解：用I表示全校学生，A表示该校男生，B表示该校高中学生，C表示团员，则有：   =900， =528， =312， =670，   且 =192， =336， =247， =175   这样，初中女生的非团员数是： - - - + + + - =900-528-312-670+192+336+247-175= -10<0 因人数做到负数，所以数据统计有错误。 例9 从自然数序列：1，2，3，4，…中依次划去3的倍数和4的倍数，但其中5的倍数均保留。划完后剩下的数依次组成一个新的序列：1，2，5，7，…求该序列中第2002个数。 55+22，说明2002是56段中的第22个数。(分析：因为3，4，5的最小公倍数是60，所以可将自然数序列：1，2，3，4，…以60的倍数来分段，先考虑1到60的整数，其中3的倍数有20个，4的倍数有15个，既是3的倍数又是4的倍数的数有5个，则划去3的倍数和4的倍数还剩60-20-15+5=30个，又还要保留其中的5的倍数6个，这样还剩36个，即1到60的整数中，划完后剩下36个，由此推得，每60个一段中，划完后剩下36个。因2002=36 解：先考虑1到60的整数   在1到60的整数中，3的倍数有20个，4的倍数有15个，既是3的倍数又是4的倍数的数有5个，所以划去3的倍数和4的倍数还剩60-20-15+5=30个。   又因为其中5的倍数有6个，需要保留，所以划完后剩下30+6=36个 因为3，4，5的最小公倍数是60，所以每60个整数一段中，划完后均剩下36个。   60+37=3337。(55+22，所以第2002个数是56段中的第22个数。因为第一段中的第22个数是37，所以该序列中第2002个数是55(因为2002=36 三、    巩固练习 选择题 1、在1到40这四十个自然数中选一些数组成数集，使其中任何一个数不是另一个数的2倍，则这个数集最多有(   )个数。 A、20     B、26   C、30   D、40 2、甲、乙、丙、丁四人排成一排照相，甲不排在首位，丁不排在末位，有(   )种不同的排法。 A、14     B、13   C、12   D、11 3、从1到1000中，能被2，3，5之一整除的整数有(   )个 A、767     B、734   C、701   D、698 4、从1到200中，能被7整除但不能被14整除的整数有(   )个 A、12     B、13   C、14   D、15 5、A、B、C是面积分别为150、170、230的三张不同形状的纸片，它们重叠放在一起的覆盖面积是350，且A与B、B与C、A与C的公共部分面积分别是100、70、90。则A、B、C的公共部分面积是(   ) A、12     B、13   C、60   D、15 6、50束鲜花中，有16束插放着月季花，有15束插放着马蹄莲，有21束插放着白兰花，有7束中既有月季花又有马蹄莲，有8束中既有马蹄莲又有白兰花，有10束中既有月季花又有白兰花，还有5束鲜花中，月季花、马蹄莲、白兰花都有。则50束鲜花中，这三种花都没有的花束有(     ) A、17     B、18   C、19   D、20 填空题 7、一张正方形的纸片面积是50平方厘米，一张圆形的纸片面积是40平方厘米。两张纸片覆盖在桌面上的面积是60平方厘米，则这两张纸片重合部分的面积是       。 8、某班有学生45人，已知其次考试数学30人优秀，物理28人优秀，数理两科都优秀的有20人。则数理两科至少有一科优秀的有     人，一科都未达到优秀的有     人。 9、某班有学生50人，参加数学兴趣小组的有35人，参加 语文 八上语文短文两篇二年级语文一匹出色的马课件部编版八上语文文学常识部编八上语文文学常识二年级语文一匹出色的马课件 兴趣小组的有30人，每人至少参加一个组，则两个组都参加的有       人。 10、一个数除以3余2，除以4余1，则这个数除以12的余数是       。 11、每边长是10厘米的正方形纸片，正中间挖一个正方形的洞，成为一个边宽是1厘米的方框。把5个这样的方框放在桌上，成为如图这样的图形。则桌面上被这些方框盖住的部分面积是       平方厘米。 12、200以内的正偶数中与5互质的数有       个。 解答题 13、在线段AB上取两个点以C、D，     已知AB=25，AD=19，CB=17，求CD长。 14、求1到200的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S。 15、100名学生面向老师站成一行，老师先让大家从左到右按1，2，3，…依次报数，再让报数是3的倍数的学生向后转，接着又让报数是7的倍数学生向后转，问此时还有多少学生面向老师？这些面向老师的学生的报数号的总和是多少？ 16、求前500个正整数中非5、非7、非11的倍数的数的个数。 17、某校初 一年级 小学一年级数学20以内加减练习题小学一年级数学20以内练习题小学一年级上册语文教学计划人教版一年级上册语文教学计划新人教版一年级上册语文教学计划 有120名学生，参加体育、文学、数学兴趣小组的人数之和为135，其中，既参加了体育兴趣小组又参加了文学兴趣小组有15人，既参加了体育兴趣小组又参加了数学兴趣小组有10人，既参加了文学兴趣小组又参加了数学兴趣小组有8人，三个兴趣小组都参加的有4人，求三个兴趣小组都没有参加的人数。 18、某班语文、数学、外语三门考试成绩统计结果如下： 课程    语文    数学    外语    语、数    数、外    语、外    至少一门 得满分人数    9    11    8    5    3    4    18 问：语文、数学、外语三门考试都得满分的人数是多少？ 19、求出分母是111的最简真分数的和。 20、有1997盏亮着的电灯，各有一个拉线开关控制着。现将其顺序编号为1，2，3，…，1997。将编号为2的倍数的灯线拉一下，再将编号为3的倍数的灯线拉一下，最后将编号为5的倍数的灯线拉一下，拉完后还有几盏灯是亮的？ PAGE 1 咨询电话：87953785