竞赛讲座 20容斥原理

初一数学竞赛系列讲座容斥原理集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#初一数学竞赛系列讲座(15)容斥原理一、 知识要点1、容斥原理在计数时，常常遇到这样的情况，作合并运算时会把重复的部分多算，需要减去；作排除运算时会把重复部分多减，需要加上，这就是容斥原理。

它的基本形式是：记A 、B 是两个集合，属于集合A 的东西有A 个，属于集合B 的东西有B 个，既属于集合A 又属于集合B 的东西记为B A ，有B A 个；属于集合A 或属于集合B 的东西记为B A ，有B A 个，则有：B A =A +B -B A容斥原理可以用一个直观的图形来解释。

如图， 左圆表示集合A ，右圆表示集合B ，两圆的公共部分表示B A ，两圆合起来的部分表示B A ， 由图可知：B A =A +B -B A容斥原理又被称作包含排除原理或逐步淘汰原则。

二、 例题精讲例1 在1到200的整数中，既不能被2整除，又不能被3整除的整数有多少个分析：根据容斥原理，应是200减去能被2整除的整数个数，减去能被3整除的整数个数，还要加上既能被2整除又能被3整除，即能被6整除的整数个数。

解：在1到200的整数中，能被2整除的整数个数为：2?1，2?2，…，2?100，共100个；在1到200的整数中，能被3整除的整数个数为：3?1，3?2，…，3?66，共66个；在1到200的整数中，既能被2整除又能被3整除，即能被6整除的整数个数为： 6?1，6?2，…，6?33，共33个；所以，在1到200的整数中，既不能被2整除，又不能被3整除的整数个数为：200-100-66+33=67(个)例2 求1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S 。

解：1到100的自然数中，所有自然数的和是：1+2+3+…+100=50501到100的自然数中，所有2的倍数的自然数和是：2?1+2?2+…+2?50=2?(1+2+3+…+50)= 2?1275=25501到100的自然数中，所有3的倍数的自然数和是：3?1+3?2+…+3?33=3?(1+2+3+…+33)= 3?561=16831到100的自然数中，所有既是2的倍数又是3的倍数，即是6的倍数的自然数和是：6?1+6?2+…+6?16=6?(1+2+3+…+16)= 6?136=816所以，1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S=5050-2550-1683+816=1633例3求不大于500而至少能被2、3、5中一个整除的自然数的个数。

五年级下册数学奥数专题讲座第十二课《容斥原理》难题练习及题目答案五年级奥数下册：第十二讲容斥原理五年级奥数下册：第十二讲容斥问题习题五年级奥数下册：第十二讲容斥问题习题解答活动目的：教育学生懂得“水”这一宝贵资源对于我们来说是极为珍贵的，每个人都要保护它，做到节约每一滴水，造福子孙万代。

活动过程：1.主持人上场，神秘地说：“我让大家猜个谜语，你们愿意吗？”大家回答：“愿意！”主持人口述谜语：“双手抓不起，一刀劈不开，煮饭和洗衣，都要请它来。

”主持人问：“谁知道这是什么？”生答：“水！”一生戴上水的头饰上场说：“我就是同学们猜到的水。

听大家说，我的用处可大了，是真的吗？”主持人：我宣布：“水”是万物之源主题班会现在开始。

水说：“同学们，你们知道我有多重要吗？”齐答：“知道。

”甲：如果没有水，我们人类就无法生存。

小熊说：我们动物可喜欢你了，没有水我们会死掉的。

花说：我们花草树木更喜欢和你做朋友，没有水，我们早就枯死了，就不能为美化环境做贡献了。

主持人：下面请听快板《水的用处真叫大》竹板一敲来说话，水的用处真叫大；洗衣服，洗碗筷，洗脸洗手又洗脚，煮饭洗菜又沏茶，生活处处离不开它。

栽小树，种庄稼，农民伯伯把它夸；鱼儿河马大对虾，日日夜夜不离它；采煤发电要靠它，京城美化更要它。

主持人：同学们，听完了这个快板，你们说水的用处大不大？甲说：看了他们的快板表演，我知道日常生活种离不了水。

乙说：看了表演后，我知道水对庄稼、植物是非常重要的。

丙说：我还知道水对美化城市起很大作用。

2.主持人：水有这么多用处，你们该怎样做呢？（1）（生）：我要节约用水，保护水源。

（2）（生）：我以前把水壶剩的水随便就到掉很不对，以后我一定把喝剩下的水倒在盆里洗手用。

（3）（生）：前几天，我看到了学校电视里转播的“水日谈水”的节目，很受教育，同学们看得可认真了，知道了我们北京是个缺水城市，我们再不能浪费水了。

（4）（生）：我要用洗脚水冲厕所。

竞赛讲座20-容斥原理在一些计数问题中，经常遇到有关集合元素个数的计算。

我们用|A|表示有限集合A的元素个数(新教材中用CardA表示有限集合A的元素个数)。

原理一：给定两个集合A和B，要计算A∪B中元素的个数，可以分成两步进行：第一步：先求出∣A∣+∣B∣（或者说把A，B的一切元素都“包含”进来，加在一起）；第二步：减去∣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求不超过20的正整数中是2的倍数或3的倍数的数共有多少个。

例2 某班统计考试成绩，数学得90分上的有25人；语文得90分以上的有21人；两科中至少有一科在90以上的有38人。

问两科都在90分以上的有多少人？例3 某校组织棋类比赛，分成围棋、中国象棋和国际象棋三个组进行。

参加围棋比赛的共有42人，参加中国象棋比赛的共有51人，参加国际象棋比赛的共有30人。

同时参加了围棋和中国象棋比赛的共有13人，同时参加了围棋和国际象棋比赛的7人，同时参加了中国象棋和国际象棋比赛的11人，其中三种棋赛都参加的3人。

问参加棋类比赛的共有多少人？例4边长分别为6，5，2的三个正方形，如图8—5所示放在桌面上。

问它们盖住的面积是多大？例5求1到200的自然数中不能被2、3、5中任何一个数整除的数有多少？练习题1. 某班共有48名学生，都参加了语文兴趣小组或数学兴趣小组，其中参加语文兴趣小组的有30人，参加数学兴趣小组的有28人，问同时参加语文、数学兴趣小组的人数是多少．2.纸片面积为7，一张边长为2的正方形纸片，把这两张纸片放在桌面上覆盖的面积为8，问两张纸片重合部分的面积是多少？3. 不超过110且与110互质的自然数有几个？4.求在1至1000的自然数中，不能被5或7整除的数有多少个。

学习奥数的优点1、激发学生对数学学习的兴趣，更容易让学生体验成功，树立自信。

2、训练学生良好的数学思维习惯和思维品质。

要使经过奥数训练的学生，思维更敏捷，考虑问题比别人更深层次。

3、锻炼学生优良的意志品质。

可以培养持之以恒的耐心和克服困难的信心，以及战胜难题的勇气。

可以养成坚韧不拔的毅力4、获得扎实的数学基本功，发挥创新精神和创造力的最大空间。

容斥原理学生姓名授课日期教师姓名授课时长知识定位容斥原理中的知识点比较简单，是计数问题中比较浅的一支。

这个知识点经常和数论知识结合出综合型题目。

这个原理本身并不是很难理解，不过经常和数论知识结合出题，所以对学生的理解层次要求较高，学生必须充分理解、吃透。

1.充分理解和掌握容斥原理的基本概念2.利用图形分析解决容斥原理问题知识梳理授课批注：本讲的知识点必须让学生充分理解、吃透，这个原理本身并不是很难理解，不过经常和数论知识结合出题所以对学生的理解层次要求较高。

一. 容斥原理的概念定义在一些计数问题中，经常遇到有关集合元素个数的计算。

我们用|A|表示有限集A 的元素个数。

求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，用式子可表示成：|A∪B| = |A| + |B| - |A∩B|，我们称这一公式为包含与排除原理，简称容斥原理。

图示如右:A表示小圆部分，B表示大圆部分，C表示大圆与小圆的公共部分，记为：A∩B，即阴影面积。

用法：包含与排除原理告诉我们，要计算两个集合A、B的并集A∪B的元素的个数，可分以下两步进行：第一步：分别计算集合A、B的元素个数，然后加起来，即先求|A|+|B|（意思是把A、B的一切元素都“包含”进来，加在一起）；第二步：从上面的和中减去交集的元素个数，即减去C=|A∩B|（意思是“排除”了重复计算的元素个数）二.竞赛考点1.容斥原理的基本概念2.与数论相结合的综合型题目例题精讲【试题来源】【题目】在一个炎热的夏日，10个小学生去冷饮店每人都买了冷饮。

容斥原理教学目标：1、理解容斥原理，会画图分析其中关系，正确的找出答案。

2、培养学生的逻辑思维和数学思考能力。

3、培养学生良好的书写习惯。

一、教学内容（一）知识介绍容斥问题涉及到一个重要原理——包含与排除原理，也叫容斥原理。

即当两个计数部分有重复包含时，为了不重复计数，应从它们的和中排除重复部分。

容斥原理：对n 个事物，如果采用不同的分类标准，按性质a 分类与性质b 分类（如图），那么具有性质a 或性质b 的事物的个数=N a ＋N b －N ab 。

（二）例题精讲 例1、一个班有48人，班主任在班会上问：“谁做完语文作业？请举手！”有37人举手。

又问：“谁做完数学作业？请举手！”有42人举手。

最后问：“谁语文、数学作业都没有做完？”没有人举手。

求这个班语文、数学作业都完成的人数。

例2、某班有36个同学在一项测试中，答对第一题的有25人，答对第二题的有23人，两题都答对的有15人。

问多少个同学两题都答得不对？例3、某班有56人，参加语文竞赛的有28人，参加数学竞赛的有27人，如果两科都没有参加的有25人，那么同时参加语文、数学两科竞赛的有多少人？Nab NbNa例4、1到100的自然数中，既不是5的倍数也不是6的倍数的数有多少个？例5、光明小学举办学生书法展览。

学校的橱窗里展出了每个年级学生的书法作品，其中有24幅不是五年级的，有22幅不是六年级的，五、六年级参展的书法作品共有10幅，其他年级参展的书法作品共有多少幅？二、教学练习1、五年级有122名学生参加语文、数学考试，每人至少有一门功课取得优秀成绩。

其中语文成绩优秀的有65人，数学优秀的有87人。

语文、数学都优秀的有多少人？2、五（1）班有40个学生，其中25人参加数学小组，23人参加科技小组，有19人两个小组都参加了。

那么，有多少人两个小组都没有参加？3、一个旅行社有36人，其中会英语的有24人，会法语的有18人，两样都不会的有4人。

两样都会的有多少人？4、在1到200的全部自然数中，既不是5的倍数又不是8的倍数的数有多少个？5、科技节那天，学校的科技室里展出了每个年级学生的科技作品，其中有110件不是一年级的，有100件不是二年级的，一、二年级参展的作品共有32件。

§24容斥原理相对补集：称属于A而不属于B的全体元素，组成的集合为B对A的相对补集或差集，记作A-B。

容斥原理：以表示集合A中元素的数目，我们有，其中为n个集合称为A的阶。

n阶集合的全部子集数目为。

例题讲解1．对集合{1，2，…，n}及其每一个非空了集，定义一个唯一确定的“交替和”如下：按照递减的次序重新排列该子集，然后交替地减或加后继的数所得的结果，例如，集合的“交替和”是9-6+4-2+1=6.的“交替和”是6-5=1，的交替和是2。

那么，对于n=7。

求所有子集的“交替和”的总和。

2．某班对数学、物理、化学三科总评成绩统计如下：优秀的人数：数学21个，物理19个，化学20个，数学物理都优秀9人，物理化学都优秀7人。

化学数学都优秀8人。

这个班有5人任何一科都不优秀。

那么确定这个班人数以及仅有一科优秀的三科分别有多少个人。

3．计算不超过120的合数的个数4．1992位科学家，每人至少与1329人合作过，那么，其中一定有四位数学家两两合作过。

5．把个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合。

6．给定1978个集合，每个集合都含有40个元素，已知其中任意两个集合都恰有一个公共元，证明：存在一个元素，它属于全部集合。

7．在个元素组成的集合中取个不同的三元子集。

证明：其中必有两个，它们恰有一个公共元。

例题答案：1．分析；n=7时，集合{7，6，5，4，3，2，1}的非空子集有个，虽然子集数目有限，但是逐一计算各自的“交替和”再相加，计算量仍然巨大，但是，根据“交替和”的定义，容易看到集合{1，2，3，4，5，6，7}与{1，2，3，4，5，6}的“交替和”是7；可以想到把一个不含7的集和A与的“交替和”之和应为7。

1. 了解容斥原理二量重叠和三量重叠的内容；2. 掌握容斥原理的在组合计数等各个方面的应用．一、两量重叠问题在一些计数问题中，经常遇到有关集合元素个数的计算．求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，用式子可表示成：A B A B A B =+-U I (其中符号“U ”读作“并”，相当于中文“和”或者“或”的意思；符号“I ”读作“交”，相当于中文“且”的意思．)则称这一公式为包含与排除原理，简称容斥原理．图示如下:A 表示小圆部分，B 表示大圆部分，C 表示大圆与小圆的公共部分，记为：A B I ，即阴影面积．图示如下:A 表示小圆部分，B 表示大圆部分，C 表示大圆与小圆的公共部分，记为：A B I ，即阴影面积．包含与排除原理告诉我们，要计算两个集合A B 、的并集A B U 的元素的个数，可分以下两步进行：第一步：分别计算集合A B 、的元素个数，然后加起来，即先求A B +(意思是把A B 、的一切元素都“包含”进来，加在一起)；第二步：从上面的和中减去交集的元素个数，即减去C A B =I (意思是“排除”了重复计算的元素个数)．二、三量重叠问题A 类、B 类与C 类元素个数的总和A =类元素的个数B +类元素个数C +类元素个数-既是A 类又是B 类的元素个数-既是B 类又是C 类的元素个数-既是A 类又是C 类的元素个数+同时是A 类、B 类、C 类的元素个数．用符号表示为：A B C A B C A B B C A C A B C =++---+U U I I I I I ．图示如下：教学目标知识要点1．先包含——A B +重叠部分A B I 计算了2次，多加了1次； 2．再排除——A B A B +-I把多加了1次的重叠部分A B I 减去．图中小圆表示A 的元素的个数，中圆表示B 的元素的个数，大圆表示C 的元素的个数．1．先包含：A B C ++重叠部分A B I 、B C I 、C A I 重叠了2次，多加了1次． 2．再排除：A B C A B B C A C ++---I I I重叠部分A B C I I 重叠了3次，但是在进行A B C ++- A B B C A C --I I I 计算时都被减掉了． 3．再包含：A B C A B B C A C A B C ++---+I I I I I ．7-7-4 容斥原理之数论问题在解答有关包含排除问题时，我们常常利用圆圈图(韦恩图)来帮助分析思考．例题精讲【例 1】在1~100的全部自然数中，不是3的倍数也不是5的倍数的数有多少个？【巩固】在自然数1100~中，能被3或5中任一个整除的数有多少个？【巩固】在前100个自然数中，能被2或3整除的数有多少个？【例 2】在从1至1000的自然数中，既不能被5除尽，又不能被7除尽的数有多少个?【巩固】求在1至100的自然数中能被3或7整除的数的个数．【例 3】以105为分母的最简真分数共有多少个？它们的和为多少？【巩固】分母是385的最简真分数有多少个？并求这些真分数的和.【例 4】在1至2008这2008个自然数中，恰好是3、5、7中两个数的倍数的数共有个．【例 5】求1到100内有____个数不能被2、3、7中的任何一个整除。

集合的概念与容斥原理一、基础知识本讲内容包括集合概念及其性质(集合的元素满足确定性、互异性、无序性)；元素与集合、集合与集合的关系(属于、包含、子集、空集、全集)；集合的运算(交、并、补)及容斥原理等.“交、并、补”是集合的三种运算，它们的含义可以用“且、或、非”來理解.这对于运用集合语言描述数学现象，或解读运用集合语言描述的问题都有帮助.集合及其运算有如下一些常用的性质和公式：= B « Be A, A\JB = B « AcB；(A|JB)UC = AU(BUC), (A门B)门C = A门(fine);AU(Bnc)=(AUB)n(xuc), xn(BUc)=(AnB)u(/inc)；C f (A U fi) = (C, A)门(C, 5), C, (A 门 fi) = (C, A) U (C, 5).容斥原理：card(A\J B) = card(A) + card(B) - card(A B) •，card(A\J B\JC) = card(A) + card(B) + card(C)-card(Ar\B)-card(0 C) - card(C0 A)+card( Ar\Br\C).该结论可以推广到n个集合：一般地，对于"个有限集合'，&，…，S。

，则有…J；| 尽…+\<i<n \<i< j<n \<i< j<k<n(-1/—1 Zl 八叫n…叭 |+…ns2…AS，, I，其屮…I表示，…，乂中任取々个集合的交的元素个数的总和.I^i, <i2二、基础训练1、己知集合从中的元素都是自然数，且若xe ,则8-xeM,则满足这样条件的集合有____________ 个.【解】列举法可得有31个.2、若非空集合A={X|26Z +K X S3“一5},B={X\3<X<22},则能使？1。

竞赛讲座(容斥原理)一、 知识要点1、容斥原理在计数时，常常遇到这样的情况，作合并运算时会把重复的部分多算，需要减去；作排除运算时会把重复部分多减，需要加上，这就是容斥原理。

它的基本形式是： 记A 、B 是两个集合，属于集合A 的东西有A 个，属于集合B 的东西有B 个，既属于集合A 又属于集合B 的东西记为B A ，有B A 个；属于集合A 或属于集合B 的东西记为B A ，有B A 个，则有：B A =A +B -B A容斥原理可以用一个直观的图形来解释。

如图，左圆表示集合A ，右圆表示集合B ，两圆的公共部分表示B A ，两圆合起来的部分表示B A ， 由图可知：B A =A +B -B A容斥原理又被称作包含排除原理或逐步淘汰原则。

二、 例题精讲例1 在1到200的整数中，既不能被2整除，又不能被3整除的整数有多少个？分析：根据容斥原理，应是200减去能被2整除的整数个数，减去能被3整除的整数个数，还要加上既能被2整除又能被3整除，即能被6整除的整数个数。

解：在1到200的整数中，能被2整除的整数个数为：2⨯1，2⨯2，…，2⨯100，共100个；在1到200的整数中，能被3整除的整数个数为：3⨯1，3⨯2，…，3⨯66，共66个；在1到200的整数中，既能被2整除又能被3整除，即能被6整除的整数个数为： 6⨯1，6⨯2，…，6⨯33，共33个；所以，在1到200的整数中，既不能被2整除，又不能被3整除的整数个数为： 200-100-66+33=67(个)例2 求1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S 。

解：1到100的自然数中，所有自然数的和是：1+2+3+…+100=50501到100的自然数中，所有2的倍数的自然数和是：2⨯1+2⨯2+…+2⨯50=2⨯(1+2+3+…+50)= 2⨯1275=25501到100的自然数中，所有3的倍数的自然数和是：3⨯1+3⨯2+…+3⨯33=3⨯(1+2+3+…+33)= 3⨯561=16831到100的自然数中，所有既是2的倍数又是3的倍数，即是6的倍数的自然数和是：6⨯1+6⨯2+…+6⨯16=6⨯(1+2+3+…+16)= 6⨯136=816.所以，1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S=5050-2550-1683+816=1633.例3求不大于500而至少能被2、3、5中一个整除的自然数的个数。

第二十讲容斥原理（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=55>42，这是因为两队都参加的人被计算了两次，因此55-42=13，即是两队都参加的人数。

[解答]解：（30+25）-42=13（人）答：两队都参加的有13人。

[评注]可能有很多同学还是刚刚接触容斥原理，所以我们用图形来形象地描绘整个问题。