第一讲集合与容斥原理
数学是一门非常迷人的学科,久远的历史,勃勃的生机使她发展成为一棵枝叶茂盛的参天大树,人们不禁要问:这根大树到底扎根于何处?为了回答这个问题,在19世纪末,德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架,他创立的这个学科一直是我们数学发展的根植地,这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为,数学的所有内容都是在“集合”中讨论、生长的。
集合是一种基本数学语言、一种基本数学工具。它不仅是高中数学的第一课,而且是整个数学的基础。对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上,而要随着数学学习的进程而不断深化,自觉使用集合语言(术语与符号)来表示各种数学名词,主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系,表示平面轨迹及其关系、表示方程(组)或不等式(组)的解、表示充要条件,描述排列组合,用集合的性质进行组合计数等。集合的划分反映了集合与子集之间的关系,这既是一类数学问题,也是数学中的解题策略——分类思想的基础,在近几年来的数学竞赛中经常出现,日益受到重视,本讲主要介绍有关的概念、结论以及处理集合、子集与划分问题的方法。
1.集合的概念
集合是一个不定义的概念,集合中的元素有三个特征:
(1)确定性设A是一个给定的集合,a是某一具体对象,则a或者是A的元素,或者不是A的元素,两者必居其一,即a∈A与a?A仅有一种情况成立。
(2)互异性一个给定的集合中的元素是指互不相同的对象,即同一个集合中不应出现同一个元素.
(3)无序性
2.集合的表示方法
主要有列举法、描述法、区间法、语言叙述法。常用数集如:R
,
,应熟记。
N,
Z
Q
3.实数的子集与数轴上的点集之间的互相转换,有序实数对的集合与平面上的点集可以互相转换。对于方程、不等式的解集,要注意它们的几何意义。
4.子集、真子集及相等集
(1)A??
B A?B或A=B;
(2)A?B?A?B且A≠B;
(3)A=B?A?B且A?B。
5.一个n阶集合(即由个元素组成的集合)有n2个不同的子集,其中有n2-1个非空子集,也有n2-1个真子集。
6.集合的交、并、补运算
x∈}
A B={A
|且B
x∈
x
x∈}
A B={A
|或B
x
x∈
x?}
A∈
{且A
=|
I
x
x
要掌握有关集合的几个运算律:
(1)交换律A B=B A,A B=B A;
(2)结合律A (B C)=(A B) C,
A (
B C)=(A B) C;
(3)分配律 A (B C )=(A B ) (A C ) A (B C )= (A B ) (A C )
(4)0—1律 A ?=A ,A I =A A I =I ,A ?=? (5)等幂律 A A =A ,A A =A
(6)吸收律 A (A B )=A ,A (A B )=A (7)求补律 A A =I ,A A =? (8)反演律 B A B A B A B A ==, 7.有限集合所含元素个数的几个简单性质 我们把有限集合A 的元素个数记作card (A) 可以证明:
(1) card (A∪B)=card (A)+card (B)-card (A∩B); (2) card (A∪B∪C)=card (A)+card (B)+card (C)
-card (A∩B)-card (A∩C)-card (B∩C) +card (A∩B∩C) 8.映射、一一映射、逆映射
(1)映射 设A 、B 是两个集合,如果按照某种对应法则f ,对于集合A 中的
任何一个元素,在集合B 中都有唯一的元素和它对应,这样的对应叫做从集合A 到集合B 的映射,记作f :A →B 。上述映射定义中的A 、B ,可以是点集,数集,也可以是其他集合。
和A 中元素a 对应的B 中的元素b 叫做a (在f 下)的象,a 叫做b 的原象。A 中的任何一个元素都有象,并且象是唯一的。
(2)一一映射 设A 、B 是两个集合,f :A →B 是从集合A 到集合B 的映
射,如果在这个映射的作用下,对于集合A 中的不同元素,在集合B 中有不同的象,且B 中的每一个元素都有原象,那么这个映射叫做A 到B 上的一一映射。
(3)逆映射 设f :A →B 是集合A 到集合B 上的一一映射,如果对于B 中的 每一个元素b ,使b 在A 中的原象a 和它对应,这样所得映射叫做映射
f :A →B 的逆映射,记作1
-f
:B →A 。
注意:只有一一映射,才有逆映射。
要能够根据这三个概念的定义,准确地判断一个给定的对应是不是映射,是不是一一映射,并能求出一一映射的逆映射。 一、 集合中待定元素的确定
例4.已知集合M ={x ,xy ,lg(xy )},S ={0,∣x ∣,y },且M =S ,则(x +1y
)+(x 2
+
2
1y
)
+……+(x 2004+
2004
1y
)的值等于( ),(据1987年全国高中数学联赛试题改编)。
分析:解题的关键在于求出x 和y 的值,而x 和y 分别是集合M 与S 中的元素。这一类根据集合的关系反过来确定集合元素的问题,要求我们要对集合元素的基本性质即确定性、异性、无序性及集合之间的基本关系(子、全、补、交、异、空、等)有本质的理解,对于两个相等的有限集合(数集),还会用到它们的简单性质: (a) 相等两集合的元素个数相等; (b) 相等两集合的元素之和相等; (c) 相等两集合的元素之积相等;
对于本题,还会用到对数、绝对值的基本性质。
解:由M =S 知,两集合元素完全相同。这样,M 中必有一个元素为0,又由对数的性质知,0和负数没有对数,所以xy ≠0,故x ,y 均不为零,所以只能有lg(xy )=0,从而xy =1 ∴M={x ,1,0},S ={0,∣x ∣,
1x
}
再由两集合相等知||
11x x x =???=?? 或11||
x x x ?=?
?
?=?
当x =1时,M ={1,1,0},S ={0,1,1},这与同一个集合中元素的互异性矛盾,故x =1不满足题目要求;
当x =-1时,M ={-1,1,0},S ={0,1,-1},M =S ,从而x =-1满足题目要求,此时
y =-1,于是
2121
1k k x y +++=-2(k =0,1,2,……),
221k k x y
+
=2(k =1,2,……)
故所求代数式的值为0
例5.设A ={x ∣x 2+ax +b =0} B ={x ∣x 2+cx +15=0} 若A∪B={3,5},A∩B={3},求a ,b ,c 。
分析:由方程的根的定义及一元二次方程的根与系数的关系(韦达定理),结合∩、∪的概念入手,可以寻得解题的突破口。
解:由A∩B={3} 知3∈B,由韦达定理知
c =-8此时,B ={3,5}=A∪B
又由A∩B={3}知5A ;而(A∩B)A (A∪B),故A ={3},即二次方程x 2+ax +b =0
有二等根x 1=x 2=3,根据韦达定理,有x 1+x 2=6=-a ,x 1x 2=9=b
所以,a =-6,b =9,c =-8 二、集合与元素之间的关系
遇到集合问题,首先要弄请:集合里的元素是什么。
集合学习中,新名词新概念多。如集合、元素、有限集、无限集、列举法、描述法、子集、真子集、空集、非空集合、全集、补集、交集、并集等。新关系新符号多,如属于、不属于、包含、包含于、真包含、真包含于、相等、不相等、相交、相并、互补(∈、
、、、
N 、N ※、Z 、Q 、R 、∩、∪、C S A 、I 、
=、≠……)等,这些新概念新关系,多而抽象。在这
千头万绪中,应该抓住“元素”这个关键,因为集合是由元素确定的,“子、全、补、交、并、空”等集合也都是通过元素来定义的。集合中元素的特征即“确定性”,“互异性”、“无序性”也就是元素的性质。集合的分类(有限集与无限集)与表示方法(列举法与描述法)也是通过元素来刻画的。元素是集合的基本内核,研究集合,首先就要确定集合里的元素是什么。 1.设A ={a |a =22y x -,Z y x ∈,},求证:(1)12-k ∈A (Z k ∈); (2))( 24Z k A k ∈?-
分析:如果集合A ={a |a 具有性质p },那么判断对象a 是否是集合A 的元素的基本方法就是检验a 是否具有性质p 。
解:(1)∵k ,1-k ∈Z 且12-k =22)1(--k k ,故12-k ∈A ; (2)假设)( 24Z k A k ∈∈-,则存在Z y x ∈,,使24-k =22y x - 即)12(2))((-=+-k y x y x (*)
由于y x -与y x +具有相同的奇偶性,所以(*)式左边有且仅有两种可能:奇数或4的倍数,另一方面,(*)式右边只能被4除余2的数,故(*)式不能成立。由此,)( 24Z k A k ∈?-。
2.设集合A =(-3,2)。已知N y x ∈,,x >y ,x y y x 191933+=+,判断 a =)(log
2
1y x +与集合A 的关系。
分析:解决本题的关键在于由已知条件确定y x +的取值范围,从而利用对数函数的单调性确定a =)(log
21y x +的范围。
解:因为)(193
3
y x y x -=-且N y x ∈,,x >y ,所以
x x +2
<2
2
2
319x y
xy x <=++
由此及N x ∈得x =3,从而y =2. 所以-3<a =25log
)23(log 2
12
1-==+,即a ∈A 。
3.以某些整数为元素的集合P 具有下列性质:①P 中的元素有正数,有负数;
②P 中的元素有奇数,有偶数;③-1?P ;④若x ,y ∈P ,则x +y ∈P 试判断实数0和2与集合P 的关系。
解:由④若x ,y ∈P ,则x +y ∈P 可知,若x ∈P ,则)( N k P kx ∈∈ (1)由①可设x ,y ∈P ,且x >0,y <0,则-y x =|y |x (|y |∈N ) 故x y ,-y x ∈P ,由④,0=(-y x )+x y ∈P 。
(2)2?P 。若2∈P ,则P 中的负数全为偶数,不然的话,当-(12+k )∈P (N k ∈)
时,-1=(-12-k )+k 2∈P ,与③矛盾。于是,由②知P 中必有正奇数。设),( 12,2N n m P n m ∈∈--,我们取适当正整数q ,使
12|2|->-?n m q ,则负奇数P n qm ∈-+-)12(2。前后矛盾。
4.设S 为满足下列条件的有理数的集合:①若a ∈S ,b ∈S ,则a +b ∈S ,
S ab ∈;②对任一个有理数r ,三个关系r ∈S ,-r ∈S ,r =0有且仅有一个成立。证
明:S 是由全体正有理数组成的集合。
证明:设任意的r ∈Q ,r ≠0,由②知r ∈S ,或-r ∈S 之一成立。再由①,若r ∈S ,则S r ∈2;若-r ∈S ,则S r r r ∈-?-=)()(2。总之,S r ∈2。
取r =1,则1∈S 。再由①,2=1+1∈S ,3=1+2∈S ,…,可知全体正整数都属于S 。 设S q p ∈,,由①S pq ∈,又由前证知S q
∈2
1,所以
2
1q
pq q
p ?
=∈S 。因此,S 含
有全体正有理数。
再由①知,0及全体负有理数不属于S 。即S 是由全体正有理数组成的集合。 例1.设A ={X ∣X =a 2
+b 2
,a 、b ∈Z },X 1,X 2∈A ,求证:X 1×X 2∈A 。
分析:A 中的元素是什么?是自然数,即由两个整数a 、b 的平方和构成的自然数,亦即从0、1、4、9、16、25……,n 2
,……中任取两个(相同或不相同)数加起来得到的一个和数,本题要证明的是:两个这样的数的乘积一定还可以拆成两个自然数的平方和的形式,即
(a 2+b 2)(c 2+d 2)=(X )2+(Y )2,X ,Y ∈Z
证明:设X 1=a 2+b 2,X 2=c 2+d 2,a 、b 、c 、d ∈Z 则X 1×X 2=(a 2
+b 2
)(c 2
+d 2
) =a 2c 2+b 2d 2+b 2c 2+a 2d 2
=a 2c 2+2ac ·bd +b 2d 2+b 2c 2-2bc ·ad +a 2d 2 =(ac +bd )2+(bc -ad )2
又a 、b 、c 、d ∈Z,故ac +bd 、bc -ad ∈Z ,从而X 1X 2∈A
说明:本题的证明中根据A 中元素的结构特点使用了配方法和“零”变换(0=2abcd -2abcd )。命题的结论说明集合A 对于其中元素的“·”运算是封闭的。类似的有: 自然数集合N 对于“+”、“×”运算是封闭的 整数集合Z 对于“+”、“-”、“×”运算是封闭的
有理数集合Q 对于“+”、“-”、“×”、“÷”运算是封闭的(除数不能是零) 实数集合对于“+”、“-”、“×”、“÷”四则运算是封闭的
复数集合对于“+”、“-”、“×”、“÷”、乘方、开方运算都是封闭的。 三、集合与集合之间的关系
在两个集合之间的关系中,我们感兴趣的是“子集”、“真子集”、“相等”这三种特殊关系。这些关系是通过元素与集合的关系来揭示的,因而判断两个集合之间的关系通常可从判断元素与这两个集合的关系入手。
5.设函数),( )(2
R b a b ax x x f ∈++=,集合}),(|{R x x f x x A ∈==,
})],([|{R x x f f x x B ∈==。
(1)证明:B A ?;
(2)当}3,1{-=A 时,求B 。
(3)当A 只有一个元素时,求证:B A =.
解:(1)设任意0x ∈A ,则0x =)(0x f .而000)()]([x x f x f f == 故0x ∈B ,所以B A ?. (2)因}3,1{-=A ,所以
???=+?+-=+-?+-
3331
)1()1(2
2b a b a 解得3,1-=-=b a 故 3)(2--=x x x f 。由)]([x f f x =得
03)3()3(2
2
2
=-------x x x x x
解得 3 ,3 ,1±
-=x
B ={}3,
3,3,1--。
6.321,,S S S 为非空集合,对于1,2,3的任意一个排列k j i ,,,若j i S y S x ∈∈,,则k S y x ∈-
(1)证明:三个集合中至少有两个相等。 (2)三个集合中是否可能有两个集无公共元素? 证明:(1)若j i S y S x ∈∈,,则
i k S x y x y S x y ∈-=--∈-)(,
所以每个集合中均有非负元素。
当三个集合中的元素都为零时,命题显然成立。
否则,设321,,S S S 中的最小正元素为a ,不妨设1S a ∈,设b 为32,S S 中最小的非负元素,不妨设,2S b ∈则b -a ∈3S 。
若b >0,则0≤b -a <b ,与b 的取法矛盾。所以b =0。
任取,1S x ∈因0∈2S ,故x -0=x ∈3S 。所以?1S 3S ,同理3S 1S ?。 所以1S =3S 。
(3)可能。例如1S =2S ={奇数},3S ={偶数}显然满足条件,1S 和2S 与3S 都无公共元素。 7.已知集合:
}1|),{(},1|),{(},1|),{(2
2
=+==+==+=y
x y x C ay x y x B y ax y x A 问
(1)当a 取何值时,C B A )(为含有两个元素的集合? (2)当a 取何值时,C B A )(为含有三个元素的集合?
解:C B A )(=)()(C B C A 。C A 与C B 分别为方程组 (Ⅰ)??
?=+=+1122y x y ax (Ⅱ)?
??=+=+11
2
2y x ay x 的解集。由(Ⅰ)解得(y x ,)=(0,1)=(2
12a
a +,
2
211a
a +-);由(Ⅱ)解得
(y x ,)=(1,0),(
2
211a
a
+-,
2
12a
a +)
(1)使C B A )(恰有两个元素的情况只有两种可能:
①???????=+-=+111012222a a a a ②???????=+-=+01111222
2
a
a a a
由①解得a =0;由②解得a =1。
故a =0或1时,C B A )(恰有两个元素。 (2)使C B A )(恰有三个元素的情况是:2
12a
a +=
2
211a
a +-
解得21±
-=a ,故当21±
-=a 时,C B A )(恰有三个元素。
8. 设N n ∈且n ≥15,B A ,都是{1,2,3,…,n }真子集,φ=B A ,且 B A ={1,2,3,…,n }。证明:A 或者B 中必有两个不同数的和为完全平方数。
证明:由题设,{1,2,3,…,n }的任何元素必属于且只属于它的真子集B A ,之一。 假设结论不真,则存在如题设的{1,2,3,…,n }的真子集B A ,,使得无论是A 还是B 中的任两个不同的数的和都不是完全平方数。
不妨设1∈A ,则3?A ,否则1+3=22,与假设矛盾,所以3∈B 。同样6?B ,所以6∈A ,这时10?A ,,即10∈B 。因n ≥15,而15或者在A 中,或者在B 中,但当15∈A 时,因1∈A ,1+15=24,矛盾;当15∈B 时,因10∈B ,于是有10+15=2
5,仍然矛盾。因此假设不真。即结论成立。
例2.已知集合M ={直线},N ={抛物线},则M ∩N 中元素的个数为() (A)0 (B)0,1,2其中之一 (C)无穷 (D)无法确定
[分析]M中的元素为直线,是无限集;N中的元素为抛物线,它也是无限集。由于两集合中的元素完全不同,即既是直线又是抛物线(曲线)的图形根本不存在,故M∩N=φ,选(A) [说明]若想当然地误认为M中的元素是直线上的点,N中的元素是抛物线上的点,当误认为是判断直线与抛物线的位置关系即相交,相切、相离时,会选(B);
例3.已知A={Y|Y=X2-4X+3,X∈R},B={Y∣Y=-X2-2X+2,X∈R}
求A∩B
先看下面的解法:
解:联立方程组
Y=X2-4X+3 ①
Y=-X2-2X+2 ②
①-②消去Y,得
2X2-2X+1=0 ③
因为Δ=(-2)2-4×2×1=-4<0,方程③无实根,故A∩B=
[说明]上述解法对吗?
回头审视两集合A、B,它们并不是由抛物线上的点构成的点集。两集合中的元素都是实数Y,即当X∈R时相应的二次函数的函数值所组成的集合,即二次函数的值域集合。故由Y =X2-4X+3=(X-2)2-1≥-1,Y=-X2-2X+2=-(X+1)2+3≤3,可知A={Y∣Y≥-1},B={Y∣Y≤3},它们的元素都是“实数”,从而有
M∩N={Y∣-1≤Y≤3}
你看,认清集合中元素的构成是多么重要!
四、有限集元素的个数(容斥原理)
请看以下问题:
开运动会时,高一某班共有28名同学参加比赛,有15人参加游泳比赛,有8人参加田径比赛,有14人参加球类比赛,同时参加游泳比赛和田径比赛的有3人,同时参加游泳比赛和球类比赛的有3人,没有人同时参加三项比赛,问同时参加田径比赛和球类比赛的有多少人?只参加游泳一项比赛的有多少人?
解决这个问题需要我们研究集合元素的个数问题(请读者参阅高中教材《数学》第一册(上)P23-P23阅读材料“集合元素的个数”。)
为此我们把有限集合A的元素个数记作card(A)
可以证明:
(1) card(A∪B)=card(A)+card(B)-card(A∩B);
(2) card(A∪B∪C)=card(A)+card(B)+card(C)
-card(A∩B)-card(A∩C)-card(B∩C)
+card(A∩B∩C)
如下图所示:
由图1-3-1,有
card(A∪B)=①+②+③=(①+②)+(②+③)-②=card(A)+card(B)-card(A∩B)
card(Cu(A∪B))=card(U)-card(A∪B)=card(U)-card(A)-card(B)+card(A∩B)
又由图1-3-2,有
card(A∪B∪C)=①+②+③+④+⑤+⑥+⑦=
(①+④+⑤+⑦)+(②+⑤+⑥+⑦)+(③+④+⑥+⑦)-(⑤+⑦)-(⑥+⑦)-(④+⑦)+⑦=
card(A)+card(B)+card(C)-card(A∩B)-card(A∩C)-card(B∩C)+card(A∩B∩C)现在我们可以来回答刚才的问题了:
设A={参加游泳比赛的同学},B={参加田径比赛的同学},C={参加球类比赛的同学} 则card(A)=15,card(B)=8,card(C)=14,card(A∪B∪C)=28
且card(A∩B)=3,card(A∩C)=3,card(A∩B∩C)=0
由公式②得28=15+8+14-3-3-card(B∩C)+0
即card(B∩C)=3
所以同时参加田径和球类比赛的共有3人,而只参加游泳比赛的人有15-3-3=9(人) 例6.计算不超过120的合数的个数
分析1:用“筛法”找出不超过120的质数(素数),计算它们的个数,从120中去掉质数,再去掉“1”,剩下的即是合数。
解法1:120以内:
① 既不是素数又不是合数的数有一个,即“1”;
② 素数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、
67、71、73、79、83、89、97、101、103、107、109、113、共30个。
所以不超过120的合数有120-1-30=89(个)
(附:筛法:从小到大按顺序写出1-120的所有自然数:
先划掉1,保留2,然后划掉2的所有倍数4,6,…120等;保留3,再划掉所有3的倍数6,9…117、120等;保留5,再划掉5的所有倍数10,15,…120;保留7,再划掉7的所有倍数,…这样,上面数表中剩下的数就是120以内的所有素数,这种方法是最古老的寻找素数的方法,叫做“埃斯托拉‘筛法’”)
说明:当n不很大时,计算1-n中的合数的个数困难不大;但当n很大时,利用筛法就很困难、很费时了,必须另觅他途。
[分析2]受解法1的启发,如果能找出1-n中质数的个数m,则n-1-m就是不超过n 的合数的个数。由初等数论中定理:a是大于1的整数。如果所有不大于√a的质数都不能整除a,那么a是质数。因为120<121=112,√120<11,所以不超过120的合数必是2或3或5或7的倍数,所以只要分别计算出不超过120的2、3、5、7的倍数,再利用“容斥原理”即可。
解法2:设S1={a∣1≤3≤120,2∣a};S2={b∣1≤b≤120,3∣b};S3=
{c∣1≤3≤120,5∣c};S4={d∣1≤d≤120,7∣d},则有:
card(S1)=[120/2]=60,card(S2)=[120/3]=40,card(S3)=[120/5]=24,card(S4)=[120/7]=17;
([n]表示n的整数部分,例如[2,4]=2,…)
card(S1∩S2)=[120/2×3]=20,card(S1∩S3)=[120/2×5]=12,
card(S1∩S4)=[120/2×7]=8,card(S2∩S3)=[120/3×5]=8,
card(S2∩S4)=[120/3×7]=5,card(S3∩S4)[120/5×7]=3,
card(S1∩S2∩S3)[120/2×3×5]=4,card(S1∩S2∩S4)=[120/2×3×7]=2,
card(S1∩S3∩S4)=[120/2×5×7]=1,card(S2∩S3∩S4)=[120/3×5×7]=1,
card(S1∩S2∩S3∩S4)=[120/2×3×5×7]=0
∴card(S1∪S2∪S3∪S4)=card(S1)+card(S2)+card(S3)+card(S4)-card(S1∩S2)-card(S1∩S3)-card(S1∩S4)-card(S2∩S3)-card(S2∩S4)-card(S3∩S4)+card(S1∩S2∩S3)+card(S1∩S2∩S4)+card(S1∩S3∩S4)+card(S2∩S3∩S4)-card(S1∩S2∩S3∩S4)=(60+40+24+17)-(20+12+8+8+5+3)+(4+2+1+1)-0=141-56+8=93
∵2,3,5,7是质数
∴93-4=89
即不超过120的合数共有89个。 五、 有限集合子集的个数 问题:
(1) 集合{a }一共有几个子集? (2) 集合{a ,b }一共有几个子集? (3) 集合{a ,b ,c }一共有几个子集? (4) 集合{a ,b,c ,d }一共有几个子集? (5) 猜想集合{a 1,a 2…,a n }一共有几个子集?
(6) 利用上述猜想确定符合下列条件的集合M 的个数:
{1,2}?M ?{1,2,3,4,5,6,7,8,9,10}。
以上诸问题都牵涉到有限集合子集的个数问题。 有限集合{a }的子集有:φ,{a };共2个
有限集合{a ,b }的子集有:φ,{a },{b },{a ,b };共4=22个;
有限集合{a ,b ,c }的子集有:φ;{a },{b },{c };{a ,b },{a ,c },{b ,c };{a ,b ,c };8=23个;
有限集合{a ,b ,c ,d }的子集有:φ;{a },{b },{c },{d };{a ,b},{a ,c }, {a ,d },{b ,c },{b ,d },{c ,d };{a ,b ,c },{a ,b ,d },{a ,c ,d },{b ,c ,d }; {a ,b ,c ,d };共16=24
个。这里,{a ,b ,c ,d }的子集可以分成两部分,一部分不包括d ,是{a ,b ,c }的子集;另一部分包括d ,是{a ,b ,c }中每一个子集与{d }的并集。
循此思路,注意到2,4=22,8=23,16=24的规律,可以猜想有限集合{a 1,a 2…,a n }的子集共有2n 个,其中非空子集有2n -1个;真子集也有2n -1个,非空真子集有2n -1-1=2n -2个。
利用上述猜想,问题(6)中集合M 的个数应当有28=256个。
例7.一个集合含有10个互不相同的两位数。试证,这个集合必有2个无公共元素的子集合,此两子集的各数之和相等。
分析:两位数共有10,11,……,99,计99-9=90个,最大的10个两位数依次是90,91,……,99,其和为945,因此,由10个两位数组成的任意一个集合中,其任一个子集中各元素之和都不会超过945,而它的非空子集却有210-1=1023个,这是解决问题的突破口。 解:已知集合含有10个不同的两位数,因它含有10个元素,故必有210=1024个子集,其中非空子集有1023个,每一个子集内各数之和都不超过90+91+…98+99=945<1023,根据抽屉原理,一定存在2个不同的子集,其元素之和相等。如此2个子集无公共元素,即交集为空集,则已符合题目要求;如果这2个子集有公共元素,则划去它们的公共元素即共有的数字,可得两个无公共元素的非空子集,其所含参数之和相等。
说明:此题构造了一个抽屉原理模型,分两步完成,计算子集中数字之和最多有945个“抽屉”,计算非空子集得1023个“苹果”,由此得出必有两个子集数字之和相等。第二步考察它们有无公共元素,如无公共元素,则已符合要求;如有公共元素,则去掉相同的数字,得出无公共元素并且非空的两个子集,满足条件。可见,有限元素子集个数公式起了关键作用。 例8.设A ={1,2,3,…,n },对X ?A ,设X 中各元素之和为N X ,求N X 的总和X X A
N ?∑
解:A 中共有n 个元素,其子集共有2n
个。A 中每一个元素在其非空子集中都出现了2
n -1
次,(为什么?因为A 的所有子集对其中任一个元素i 都可分为两类,一类是不含i 的,它们也都是{1,2,…,i -1,i +1,…n }的子集,共2n -1个;另一类是含i 的,只要把i 加入到刚才的2n-1个子集中的每一个中去)。因而求A 的所有子集中所有元素之和Nx 的总和时,A 中每一个元素都加了2n -1次,即出现了2n -1次,故得
X X A
N ?∑
=1×2n -1
+2×2n -1
+…+n ×2n -1
=(1+2+…+n )·2n -1 =
(1)
2
n n +×2n -1
=n (n +1)×2n -2
说明:这里运用了整体处理的思想及公式1+2+…+n =
(1)
2
n n + ,其理论依据是加法
的交换律、结合律、乘法的意义等。得出集合中每一个元素都在总和中出现了2n -1次,是打开解题思路之门的钥匙孔。 习题一
1、 化简集合231(,)323x y A x y x y ??+=??
?
=??
?-=?????
2、 设集合A ={1,a ,b },B ={a ,a 2,ab },且A =B ,求实数a ,b
3、 高一(1)班的学生中,参加语文课外小组的有20人,参加数学课外小组的有22人,既参加语文小组又参加数学小组的有15人,既未参加语文小组又未参加数学小组的有15人。问高一(1)班共有学生几人?
4、 设非空集合A ?{1,2,3,4,5,6,7},且当a ∈A 时必有8-a ∈A ,这样的A 共有( )个。
5、 已知A ={296的约数},B ={999}的约数,则card (A ∩B )=( )
6、 对于集合
A ={x ∣x =3n ,n =1,2,3,4}
B ={x ∣x =3k ,k =1,2,3}
若有集合M 满足A ∩B ?M ?A ∪B ,则这样的M 有多少个? 参考答案
1. A ={(1113,313-)},(列举法)或1113(,)313x A x y y ???
=??????
=??????
=-??????
(描述法)
2. A =-1,b =0 3. 47个 4. 15个
5. 2,A ∩B ={1,37}
6.共8个
易知A={3,6,9,12},B={3,9,27},故A∩B={3,9},A∪B={3,6,9,12,27},故M可以这样构造{3,9}
N?,问题归结为求N的个数,要即集合{6,12,27}的子M N
= ,其中{6,12,27}
集数,所以M有23=8个。
三集合容斥原理 华图教育梁维维 我们知道容斥原理的本质是把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复的一种计数的方法。之前我们叙述过了两集合容斥原理,下面我们来看一下三集合容斥原理,相对于两集合容斥原理而言,三集合容斥原理的难度有所增加,但总体难度适中,所以三集合容斥原理在国家公务员考试中出现的频率较高,在其他省份考试以及各省份联考当中也时有出现,下面我们了解一下三集合容斥原理的公式。 三集合容斥原理公式: 三者都不满足的个数。 总个数- = + - - - + + =| | | | | | | | | | | | | || |C B A C B C A B A C B A C B A 有些问题,可以直接代入三集合容斥原理的公式进行求解。 【例1】如图所示,X、Y、Z分别是面积为64、180、160的三张不同形状的纸片。它们部分重叠放在一起盖在桌面上,总共盖住的面积为290。且X与Y、Y与Z、Z与X重叠部分面积分别为24、70、36。问阴影部分的面积是多少?( ) A.15 B.16 C.14 D.18 【解析】依题意,假设阴影部分的面积为x,代入公式可得:64+180+160-24-70-36+x=290,解得x=16,正确答案为B选项。 近几年,直接套用三集合公式的题目有所减少,开始出现条件变形的题目,往往告诉大家“只满足两个条件的共有多少”这样的信息,看似无法直接套用公式,其实只要掌握本质,仍然可以直接套用公式。 【例2】(2012河北-44)某通讯公司对3542个上网客户的上网方式进行调查,其中1258个客户使用手机上网,1852个客户使用有线网络上网,932个客户使用无线网络上网。如果使用不只一种上网方式的有352个客户,那么三种上网方式都使用的客户有多少个?() A. 148 B. 248
国家公务员| 事业单位| 村官| 选调生| 教师招聘| 银行招聘| 信用社| 乡镇公务员| 各省公务员|政法干警| 招警| 军转干| 党政公选| 法检系统| 路转税| 社会工作师 三集合非标准型容斥原理 ———————————————海南华图数资老师,胡军亮近些年考试经常出现容斥原理的题型,容斥原理分为两集合型跟三集合型,三集合容斥原理又包括标准型和非标准型,三集合容斥原理与三集合标准型容斥原理都是相对好掌握的。这里给大家讲解三集合非标准型容斥原理题的解题方法。首先看下面三个公式 (1) 都不满足 总数- ) (= + + + - + +C B A C A C B B A C B A (2)三条件都不满足 总数 只满足两条件- * 2 -= - + +C B A C B A (3)满足三条件 只满足两条件 只满足一个条件* 3 * 2+ + = + +C B A 公式(1)是标准型公式,公式(2)、(3)都是非标准型公式。 【例1】某乡镇对集贸市场36种食品进行检查,发现超过保质期的7种,防腐添加剂不合格的9种,产品外包装标识不规范的6种。其中,两项同时不合格的5种,三项同时不合格的2种。问三项全部合格的食品有多少种?() A. 14 B. 21 C. 23 D. 32 解析:该题目为典型的容斥原理题,但是题目提到“两项同时不合格的有5种”,这句话的意思就是只满足两个条件的数量是5,该题属于三集合容斥原理非标准型题,带入公式(2)得到: 7+9+6-5-2*2=36-X,尾数法知道答案选C。 【例2】某市对52种建筑防水卷材产品进行质量抽检,其中有8种产品的低温柔度不合格,10种产品的可溶物含量不达标,9种产品的接缝剪切性能不合格,同时两项不合格的有7种,有1种产品这三项都不合格。则只有一项不合格的建筑防水卷材产品有多少种? A. 17 B. 12 C. 15 D. 20 解析:该题涉及到只满足一项不合格、同时两项不合格、三项都不合格,属于三个集合非标准型容斥原理的题,带入公式(3)得到: 8+10+9=X+2*7+1,尾数法知道答案选B。 从上面的两道例题的讲解可以看到三集合非标准型容斥原理虽然不是很好理解,但是记住题型的特征,用正确的公式直接套用来解题还是很容易掌握的。
1. 现有50名学生都做物理、化学实验,如果物理实验做正确的有40人,化学实验做正确的有31人,两种实验都错的有4人,则两种实验都做对的有( ) 【答案】B 【解析】直接代入公式为:50=31+40+4- A H B 得A H B=25,所以答案为B。 2. 某服装厂生产出来的一批衬衫大号和小号各占一半。其中25%是白色的, 75%是蓝色的。如果这批衬衫共有100件,其中大号白色衬衫有10件,小号蓝色衬衫有多少件?() A 、15 B 、 25 C 、35 D40 【答案】C 【解析】这是一种新题型,该种题型直接从求解出发,将所求答案设为A H B,本题设小号和蓝色分别为两个事件A和B,小号占50%蓝色占75%直接代入公式
为:100=50+75+10- A H B,得:A H B=35 3. 某高校对一些学生进行问卷调查。在接受调查的学生中,准备参加注册会计师考试的有63人,准备参加英语六级考试的有89人,准备参加计算机考试的有47人,三种考试都准备参加的有24人,准备只选择两种考试都参加的有46人,
【解析】本题画图按中路突破原则,先填充三集合公共部分数字 24,再推 其他部分数字: 根据每个区域含义应用公式得到: 总数=各集合数之和-两两集合数之和+三集合公共数+三集合之外数 =63+89+47— {(x+24)+(z+24)+(y+24)}+24+15 =199— { (x+z+y ) +24+24+24}+24+15 根据上述含义分析得到:x+z+y 只属于两集合数之和,也就是该题所讲的只 选择两种考试都参加的人数,所以 x+z+y 的值为46人;得本题答案为120. 4. 对某单位的100名员工进行调查,结果发现他们喜欢看球赛和电影、戏剧。 其中58人喜欢看球赛,38人喜欢看戏剧,52人喜欢看电影,既喜欢看球赛又喜 欢看戏剧的有18人,既喜欢看电影又喜欢看戏剧的有16人,三种都喜欢看的有 12人,则只喜欢看电影的有多少人( ) A.22 人 B.28 人 C.30 人 D.36 人 【答案】A 【解析】本题画图按中路突破原则,先填充三集合公共部分数字 12,再推 其他部分数字: 根据各区域含义及应用公式得到: 总数=各集合数之和-两两集合数之和+三集合公共数+三集合之外数 100= 58+38+52- {18+16+ (12+ x ) }+12+0,因为该题中,没有三种都不喜 欢的 人,所以三集合之外数为 0,解方程得到:x = 14。52= x+12+4+Y = 14+12+4+Y 得到Y = 22人。 不参加其中任何一种考试的都15人。问接受调查的学生共有多少人?( )
三集合容斥原理按题型可以分为两种题型,一种为标准型公式,另一种为变异型公式,接下来,我们就着重看看三集合容斥原理的标准型公式。 集合Ⅰ、Ⅱ、Ⅲ,满足标准型公式: 三集合容斥原理标准型公式:Ⅰ+Ⅱ+Ⅲ-Ⅰ·Ⅱ-Ⅰ·Ⅲ-Ⅱ·Ⅲ+Ⅰ·Ⅱ·Ⅲ=总个数-三者都不满足个数 通过观察公式,我们可以看到在公式中,出现了9个量,而这个式子的适用前提就是知8求1,即在题目中,若我们看到了8个已知量,要求1个未知量的时候,就要使用这个公式(注:而题目中有时候也是知7求1,其中的三者都不满足的个数可能为零),具体题目如下: (陕西2015)针对100名旅游爱好者进行调查发现,28人喜欢泰山,30人喜欢华山,42人喜欢黄山,8人既喜欢黄山又喜欢华山,10人既喜
欢泰山又喜欢黄山,5人既喜欢华山又喜欢黄山,3人喜欢这三个景点,则不喜欢这三个景点中任何一个的有( )人。 A.20 B.18 C.17 D.15 E.14 F.13 G.12 H.10 解:通过观察,我们发现了八个已知量,还要我们求另一个未知量,故可以用上述公式,我们将数据逐个代入可得: 28+30+42-8-10-5+3=100-x,其中x为我们要求的量,求得x=20,答案选择A。 接着,我们来看一下三集合变异型的公式,如下图示:
从上式中,我们可以看出,要使用变异型公式,题目中必须要出现仅满足2个情况的个数,这就是与标准型公式最大的不同,下面我们就看看具体的题目: (广东2015)某乡镇举行运动会,共有长跑、跳远和短跑三个项目。参加长跑的有49人,参加跳远的有36人,参加短跑的有28人,只参加其中两个项目的有13人,参加全部项目的有9人。那么参加该次运动会的总人数为( )。 A.75 B.82 C.88 D.95 解:由于题目中出现“只参加其中两个项目的有13人”,故使用变异型公式,得到下面列式:49+36+28-1×13-2×9=x,通过尾数法(若题目中选项的尾数都不一样的话,就可以用尾数法快速得到答案),判断出答案为82,选B。 但是,现在变异型公式也出现一些变形的形式,例如国考2015中的这道三集合容斥原理,就给我带来了一写在解题是需要着重注意的地方,下面我们仔细分析一下题目 (国家2015)某企业调查用户从网络获取信息的习惯,问卷回收率为90%。调查对象中有179人使用搜索引擎获取信息,146人从官方网站获取信息,246人从社交网络获取信息,同时使用这三种方式的有115人,使用其中两种的有24人,另有52人这三种方式都不使用,问这次调查共发出了多少份问卷?( ) A.310 B.360
方法精讲-数量 4(笔记) 学习任务: 1.课程内容:容斥原理、排列组合与概率 2.授课时长:3小时 3.对应讲义:178页~184页 4.重点内容: (1)掌握两集合公式,三集合的三种公式——标准型、非标准型、常识 型 (2)掌握图示法在容斥原理中的运用,理解容斥原理结合最值的考法 (3)掌握常用的排列组合公式,理解分类讨论与分步计算的区别,正难 反易则从 反面求解 (4)掌握两种经典方法(捆绑法、插空法)的适用范围和操作步骤 (5)掌握概率问题的两种题型——给情况求概率或给概率求概率 第八节容斥原理 【注意】本节课主要讲容斥原理和排列组合和概率,预习的时候可能觉得很难。容斥问题有公式和方法,需要学习方法和公式;排列组合和概率是高中知识,比较难,但是考试不会像高中一样深,本节课会用最浅显的形式讲解,无论高中学过与否,这节课要从零开始全部拿下。 【知识点】容斥原理:多个集合有交叉有重复。比如班级有男有女,此时男生是一个集合,女生是一个集合,但是没有交叉,故不是容斥。班级中无论男女有行测学得好的,也有申论学得好的,此时一定有交叉(行测和申论都学得好),行测学得好的是一个集合,申论学得好的是一个集合,重合部分是一个交叉,多个集合有交叉,是容斥问题。
【知识点】两集合: 1.推导:左边的圆为 A,右边的圆为 B,中间重合部分是 AB 的交集,即中间部分相加的时候出现两次,需要减去一次,“A+B-A∩B”完整对应圆覆盖的整体,“全部”是外面框框,代表一个总体范围,“都不”是框内空白区域,公式:A+B-A ∩B=全部-都不。 2.例子:左边 A 是行测比较好的,有 70 人;右边B 是申论比较好的,有 60 人,班级中有 31 人行测和申论都比较好,全班一共有 100 人,求行测和申论都不好的有多少人。 答:代入公式:70+60-31=100-都不,99=100-都不,解得:都不=1。 3.公式:A+B-A∩B=全部-都不。 【例 1】(2017 广东)某单位有 107 名职工为灾区捐献了物资,其中 78 人捐献衣物,77 人捐献食品。该单位既捐献衣物,又捐献食品的职工有多少人? A.48 B.50 C.52 D.54 【解析】例 1.出现“既……又……”,两个集合有重复,两集合容斥原理问题,公式:A+B-A∩B=总数-都不。设都捐献的为 x,已知“有 107 名职工为灾区捐献了物资”,即都不=0,代入数据:78+77-x=107-0,利用尾数法,尾数 5-x=尾数 7,x 的尾数为 8,对应A 项。【选A】 【注意】本题不是很严谨,“都不”可以不是 0,比如捐帐篷,此时也是衣物和食品都不捐。
容斥原理 标准三集合 【例 1】某专业有学生50人,现开设甲.乙.丙三门选修课。有40人选修甲课程,36人选修乙课程,30人选修丙课程,兼选甲乙两门课程的有28人,兼选甲丙两门课程的有26人,兼选乙丙两门课程的有24人,甲乙丙三门课程均选的有20人,问三门课程均未选的有多少人? A.1 B.2 C.3 D.4 【答案】B 【解析】至少选一门的有:40+36+30-28-26-24+20=48人,则均为选的有 50-48=2人。 【例 2】某公司招聘员工,按规定每人至多可投考两个职位,结果共42人报名,甲、乙、丙三个职位报名人数分别是22人、16人、25人,其中同时报甲、乙职位的人数为8人,同时报甲、丙职位的人数为6人,那么同时报乙、丙职位的人数为()(2012联考) A. 7人 B. 8人 C. 5人 D. 6人 【答案】A 【解析】假设同时报乙、丙职位的人数为x,则: 22+16+25-8-6-x+0=42,解得x=7 只满足一项条件型 【例 1】一次运动会上,18名游泳运动员中,有8名参加了仰泳,有10名参加了蛙泳,有12名参加了自由泳,有4名既参加仰泳又参加蛙泳,有6名既参加蛙泳又参加自由泳,有5
名既参加仰泳又参加自由泳,有2名这3个项目都参加,这18名游泳运动员中,只参加1个项目的人数为( )(2012-424联考) A.5名 B.6名 C.7名 D.4名 【答案】B 【解析】画图法 【例 2】 88名学生参加运动会,参加游泳比赛的有23人,参加田径比赛的有33人,参加球类比赛的有54人,既参加游泳比赛又参加田径比赛的有5人,既参加田径比赛又参加球类比赛的有16人。已知每名学生最多可参加两项比赛,问只参加田径比赛的有多少人?() A. 20 B. 17 C. 15 D. 12 【答案】D 【解析】画图 关于整体的三集合 【知识点】在三集合的题中,假设满足三个条件的元素数量分别为A 、B 、C ,至少满足三个条件之一的总量为W ,其中满足一个条件的元素数量为x ,满足两个条件的元素数量为y ,满足三个条件的元素数量为z , 则有:W=x+y+z A+B+C=x ×1+y ×2+z ×3 2 3 2 4
容斥原理问题——基础学习 一、解答题
2、两个集合容斥原理例1:四年级一班有54人,定阅《小学生优秀作文》和《数学大世界》两种读物的有13人,订阅《小学生优秀作文》的有45人每人至少订阅一种读物,订阅《数学大世界》的有多少人?() A.13 B.22 C.33 D.41 【答案】B 【解题关键点】设A={定阅《小学生优秀作文》的人},B={订阅《数学大世界》的人},那么A∩B={同时订阅两本读物的人},A∪B={至少订阅一样的人},由容斥原则,B= A∪B+A∩B-A=54+13-45=22人。 【结束】 3、两个集合容斥原理例2:五年级有122名同学参加语文、数学考试,每个至少有一门功课取得优秀成绩,其中语文成绩优秀的有65人,数学成绩优秀的有87人。语文、数学都优秀的有多少人?() A. 30 B.35 C.57 D.65 【答案】A
【解题关键点】此题是典型的两个集合的容斥问题,因此,可以直接有两个集合的容斥原理得到,语文和数学都优秀的学生有65+87-122=30人。 【结束】 4、两个集合容斥原理例3:学校文艺组每人至少会演奏一种乐器,已知会拉手提琴的有24人,会弹电子琴的有17人,其中两样都会的有8人。这个文艺组共有多少人?()A.25 B.32 C.33 D.41 【答案】C 【解题关键点】设A={会拉手提琴的},B={会弹电子琴的},因此A∪B ={文艺组的人},A∩B={两样都会的},由两个集合的容斥原理可得:A∪B=A+B- A∩B=24+17-8=33。 【结束】 5、两个集合容斥原理例4:某班有36个同学在一项测试中,答对第一题的有25人,答对第二题的人有23人,两题都答对的有15人,问多少个同学两道题都没有答对?()A.1 B.2 C.3 D.4 【答案】C 【解题关键点】有两个集合的容斥原理得到,至少答对一道题的同学有25+23-15=33人,因此两道题都没有答对的同学有36-33=3人。 【结束】
2014年公务员行测:巧解三集合容斥原理问题 华图教育 三集合容斥原理此类题型主要出现在近年来各省的省考中,主要是有三个独立的个体,此类题型主要的做题方法是公式法和作图法。近年来直接套用三集合公式的题目有所减少,开始出现条件变形的题目,不管容斥原理的题目怎么变化,但我们只要掌握住核心思想——剔除重复,那么做任何一个容斥原理题目都能够得心应手。 根据上图,可得三集合容斥原理核心公式: =A +B +C -A B -B C -A C +A B C =-x A B C 总数 一、直接利用公式型 【例1】(2012年4月联考)某公司招聘员工,按规定每人至多可投考两个职位,结果共42人报名,甲、乙、丙三个职位报名人数分别是22人、16人、25人,其中同时报甲、乙职位的人数为8人,同时报甲、丙职位的人数为6人,那么同时报乙、丙职位的人数为: A. 7人 B. 8人 C. 5人 D. 6人 【答案】A 【解析】设同时报乙、丙职位的人数为x ,则根据三集合容斥原理公式有:22+16+25-8-6-x+0=42-0,解得x=7。因此,本题答案为A 选项。 二、三集合容斥原理作图型 若在题目中任何一个位置看到“只满足”或“仅满足”,则公式法不能够再用,采用作图法来解题,注意,在作图的时候不管三七二十一,先画三个两两相交的圈,再往里填数字即可,填的时候注意从中间往外一层一层填。 【例2】(2007年江苏)一次运动会上,17名游泳运动员中,有8名参加了仰泳,有10 C x B A
名参加蛙泳,有12名参加了自由泳,有4名既参加仰泳又参加蛙泳,有6名既参加蛙泳又参加自由泳,有5名既参加仰泳又参加自由泳,有2名这3个项目都参加,这17名游泳运动员中,只参加1个项目的人有多少?() A.5名 B.6名 C.7名 D.4名 【答案】B 【解析】本题问题中出现了“只”,故只能采用作图法。于是有 仰 1 2 2 2 3 4 3 蛙自由 只参加1个项目的人数为1+2+3=6。因此,本题答案为B选项。 【例3】(2012年河北)某乡镇对集贸市场36种食品进行检查,发现超过保持期的7种,防腐添加剂不合格的9种,产品外包装标识不规范的6种。其中,两项同时不合格的5种,三项同时不合格的2种。问三项全部合格的食品有多少种?() A.14 B.21 C.23 D.32 【答案】C 【解析】 a d b c 其中d为三项同时不合格的部分,a+b+c为两项同时不合格的部分。设三项全部合格的食品有x种。根据题意有:36-x=7+9+6-5-2×2,解得x=23。因此,本题答案为C选项。 【注】该题注意,由于7+6+9这部分把三项同时不合格的部分共加了3次,减去5的
、 1.现有50名学生都做物理、化学实验,如果物理实验做正确的有40人,化学实验做正确的有31人,两种实验都错的有4人,则两种实验都做对的有( ) A、27人 B、25人 C、19人 D、10人 【答案】B 【解析】直接代入公式为:50=31+40+4-A∩B 得A∩B=25,所以答案为B。 2.某服装厂生产出来的一批衬衫大号和小号各占一半。其中25%是白色的,75%是蓝色的。如果这批衬衫共有100件,其中大号白色衬衫有10件,小号蓝色衬衫有多少件() A、15 B、25 C、35 D、40 【答案】C 【解析】这是一种新题型,该种题型直接从求解出发,将所求答案设为A∩B,本题设小号和蓝色分别为两个事件A和B,小号占50%,蓝色占75%,直接代入公式为:100=50+75+10-A∩B,得:A∩B=35。 3.某高校对一些学生进行问卷调查。在接受调查的学生中,准备参加注册会计师考试的有63人,准备参加英语六级考试的有89人,准备参加计算机考试的有
47人,三种考试都准备参加的有24人,准备只选择两种考试都参加的有46人,不参加其中任何一种考试的都15人。问接受调查的学生共有多少人()A.120 B.144 C.177 D.192 【答案】A 【解析】本题画图按中路突破原则,先填充三集合公共部分数字24,再推其他部分数字: 根据每个区域含义应用公式得到: 总数=各集合数之和-两两集合数之和+三集合公共数+三集合之外数 =63+89+47-{(x+24)+(z+24)+(y+24)}+24+15 =199-{(x+z+y)+24+24+24}+24+15 根据上述含义分析得到:x+z+y只属于两集合数之和,也就是该题所讲的只选择两种考试都参加的人数,所以x+z+y的值为46人;得本题答案为120. 4.对某单位的100名员工进行调查,结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛,38人喜欢看戏剧,52人喜欢看电影,既喜欢看球赛又喜欢看戏剧的有18人,既喜欢看电影又喜欢看戏剧的有16人,三种都喜欢看的有12人,则只喜欢看电影的有多少人() 人人人人 【答案】A 【解析】本题画图按中路突破原则,先填充三集合公共部分数字12,再推其他部分数字: 根据各区域含义及应用公式得到: 总数=各集合数之和-两两集合数之和+三集合公共数+三集合之外数
三集合非规范型容斥原理 ———————————————海南华图数资老师,胡军亮近些年考试经常出现容斥原理的题型,容斥原理分为两集合型跟三集合型,三集合容斥原理又包括规范型和非规范型,三集合容斥原理与三集合规范型容斥原理都是相对好掌握的。这里给大家讲解三集合非规范型容斥原理题的解题方法。首先看下面三个公式 (1) (2) (3) 公式(1)是规范型公式,公式(2)、(3)都是非规范型公式。 【例1】某乡镇对集贸市场36种食品进行检查,发现超过保质期的7种,防腐添加剂不合格的9种,产品外包装标识不规范的6种。其中,两项同时不合格的5种,三项同时不合格的2种。问三项全部合格的食品有多少种?() A. 14 B. 21 C. 23 D. 32 解读:该题目为典型的容斥原理题,但是题目提到“两项同时不合格的有5种”,这句话的意思就是只满足两个条件的数量是5,该题属于三集合容斥原理非规范型题,带入公式(2)得到: 7+9+6-5-2*2=36-X,尾数法知道答案选C。 【例2】某市对52种建筑防水卷材产品进行质量抽检,其中有8种产品的低温柔度不合格,10种产品的可溶物含量不达标,9种产品的接缝剪切性能不合格,同时两项不合格的有7种,有1种产品这三项都不合格。则只有一项不合格的建筑防水卷材产品有多少种? A. 17 B. 12 C. 15 D. 20 解读:该题涉及到只满足一项不合格、同时两项不合格、三项都不合格,属于三个集合非规范型容斥原理的题,带入公式(3)得到: 8+10+9=X+2*7+1,尾数法知道答案选B。 从上面的两道例题的讲解可以看到三集合非规范型容斥原理虽然不是很好理解,但是记住题型的特征,用正确的公式直接套用来解题还是很容易掌握的。 1 / 1
容斥原理公式及运用 在计数时,必须注意无一重复,无一遗漏。为了使重叠部分不被重复计算,研究出一种新的计数方法。这种方法的基本思路是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。 一、容斥原理1:两个集合的容斥原理 如果被计数的事物有A、B两类,那么,先把A、B两个集合的元素个数相加,发现既是A类又是B类的部分重复计算了一次,所以要减去。如下图所示。 【示例1】一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?数学得满分人数→A,语文得满分人数→B,数学、语文都是满分人数→A∩B,至少有一门得满分人数→A∪B。A∪B=15+12-4=23,共有23人至少有一门得满分。 二、容斥原理2:三个集合的容斥原理 如果被计数的事物有A、B、C三类,那么,将A、B、C三个集合的元素个数相加后发现两两重叠的部分重复计算了1次,三个集合公共部分被重复计算了2次。如下图所示,灰色部分A∩B-A∩B∩C、B∩C-A∩B∩C、C∩A-A∩B∩C都被重复计算了1次,黑色部分A∩B∩C被重复计算了2次,因此总数A∪B∪C=A+B+C-(A∩B-A∩B∩C)-(B∩C-A∩B∩C)-(C∩A-A∩B∩C)-2A∩B∩C=A+B+C-A∩
B-B∩C-C∩A+A∩B∩C。即得到: 【示例2】某班有学生45人,每人都参加体育训练队,其中参加足球队的有25人,参加排球队的有22人,参加游泳队的有24人,足球、排球都参加的有12人,足球、游泳都参加的有9人,排球、游泳都参加的有8人,问:三项都参加的有多少人? 参加足球队→A,参加排球队→B,参加游泳队→C,足球、排球都参加的→A∩B,足球、游泳都参加的→C∩A,排球、游泳都参加的→B∩C,三项都参加的→A∩B ∩C。三项都参加的有A∩B∩C=A∪B∪C-A-B-C+A∩B+B∩C+C∩ A=45-25-22-24+12+9+8=3人。
1.现有50名学生都做物理、化学实验,如果物理实验做正确的有40人,化学实验做正确的有31人,两种实验都错的有4人,则两种实验都做对的有( ) A、27人 B、25人 C、19人 D、10人 【答案】B 【解析】直接代入公式为:50=31+40+4-A∩B 得A∩B=25,所以答案为B。 2.某服装厂生产出来的一批衬衫大号和小号各占一半。其中25%是白色的,75%是蓝色的。如果这批衬衫共有100件,其中大号白色衬衫有10件,小号蓝色衬衫有多少件() A、15 B、25 C、35 D、40 【答案】C 【解析】这是一种新题型,该种题型直接从求解出发,将所求答案设为A∩B,本题设小号和蓝色分别为两个事件A和B,小号占50%,蓝色占75%,直接代入公式为:100=50+75+10-A∩B,得:A∩B=35。 3.某高校对一些学生进行问卷调查。在接受调查的学生中,准备参加注册会计师考试的有63人,准备参加英语六级考试的有89人,准备参加计算机考试的有47人,三种考试都准备参加的有24人,准备只选择两种考试都参加的有46人,
不参加其中任何一种考试的都15人。问接受调查的学生共有多少人()A.120 B.144 C.177 D.192 【答案】A 【解析】本题画图按中路突破原则,先填充三集合公共部分数字24,再推其他部分数字: 根据每个区域含义应用公式得到: 总数=各集合数之和-两两集合数之和+三集合公共数+三集合之外数 =63+89+47-{(x+24)+(z+24)+(y+24)}+24+15 =199-{(x+z+y)+24+24+24}+24+15 根据上述含义分析得到:x+z+y只属于两集合数之和,也就是该题所讲的只选择两种考试都参加的人数,所以x+z+y的值为46人;得本题答案为120. 4.对某单位的100名员工进行调查,结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛,38人喜欢看戏剧,52人喜欢看电影,既喜欢看球赛又喜欢看戏剧的有18人,既喜欢看电影又喜欢看戏剧的有16人,三种都喜欢看的有12人,则只喜欢看电影的有多少人() 人人人人 【答案】A 【解析】本题画图按中路突破原则,先填充三集合公共部分数字12,再推其他部分数字: 根据各区域含义及应用公式得到: 总数=各集合数之和-两两集合数之和+三集合公共数+三集合之外数 100=58+38+52-{18+16+(12+ x)}+12+0,因为该题中,没有三种都不喜欢的人,所以三集合之外数为0,解方程得到:x=14。52=x+12+4+Y=14+12+4+Y,得到Y=22人。
容斥原理公式及运用 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
在计数时,必须注意无一重复,无一遗漏。为了使重叠部分不被重复计算,研究出一种新的计数方法。这种方法的基本思路是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。 一、容斥原理1:两个集合的容斥原理 如果被计数的事物有A、B两类,那么,先把A、B两个集合的元素个数相加,发现既是A类又是B类的部分重复计算了一次,所以要减去。如下图所示。 【示例1】??一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人? 数学得满分人数→A,语文得满分人数→B,数学、语文都是满分人数→A∩B,至少有一门得满分人数→A∪B。A∪B=15+12-4=23,共有23人至少有一门得满分。 二、容斥原理2:三个集合的容斥原理 如果被计数的事物有A、B、C三类,那么,将A、B、C三个集合的元素个数相加后发现两两重叠的部分重复计算了1次,三个集合公共部分被重复计算了2次。 如下图所示,灰色部分A∩B-A∩B∩C、B∩C-A∩B∩C、C∩A-A∩B∩C都被重复计算了1次,黑色部分A∩B∩C被重复计算了2次,因此总数A∪B∪C=A+B+C-(A∩B-A∩B∩C)-(B∩C-A∩B∩C)-(C∩A-A∩B∩C)-2A∩B∩C=A+B+C-A∩B-B∩C-C∩A+A∩B∩C。即得到: 【示例2】??某班有学生45人,每人都参加体育训练队,其中参加足球队的有25人,参加排球队的有22人,参加游泳队的有24人,足球、排球都参加的有12人,足球、游泳都参加的有9人,排球、游泳都参加的有8人,问:三项都参加的有多少人? 参加足球队→A,参加排球队→B,参加游泳队→C,足球、排球都参加的→A∩B,足球、游泳都参加的→C∩A,排球、游泳都参加的→B∩C,三项都参加的→A∩B∩C。三项都参加的有A∩B∩C=A∪B∪C-A-B-C+A∩B+B∩C+C∩A=45-25-22-24+12+9+8=3人。
行测数学运算技巧:三集合整体重复型公式巧解容斥原理问题 一、介绍三集合整体重复型核心公式 在三集合题型中,假设满足三个条件的元素数量分别是A、B和C,而至少满足三个条件之一的元素的总量为W。其中,满足一个条件的元素数量为x,满足两个条件的元素数量为y,满足三个条件的元素数量为z,可以得到以下两个等式: W=x+y+z A+B+C=x×1+y×2+z×3 二、典型的三集合整体重复型的题目讲解 例1、某班有35个学生,每个学生至少参加英语小组、语文小组、数学小组中的一个课外活动。现已知参加英语小组的有17人,参加语文小组的有30人,参加数学小组的有13人。如果有5个学生三个小组全参加了,问有多少个学生只参加了一个小组?(2004年浙江公务员考试行测第20题) A. 15人 B.16人 C.17人 D.18人 【答案】A 解析:此题有两种解法可以解出: 解一:分别设只参加英语和语文、英语和数学、语文和数学小组的人为x、y、z,则只参加英语小组的人为17-5-x-y,只参加语文小组的人有30-5-x-z,只参加数学小组的人有13-5-y-z,则只参加三个小组中的一个小组的人和只参加其中两个小组的人和三个小组都参加的人的总和为总人数,即17-5-x-y+30-5-x-z+13-5-y-z+x+y+z+5=35。则求x+y+z=15,所以只参加一个小组的人数的和为15。 解二:套用三集合整体重复型公式: W=x+y+z A+B+C=x×1+y×2+z×3 35=x+y+5 17+30+13=x×1+y×2+5×3 解得:x= 15,y=15
例2、某调查公司就甲、乙、丙三部电影的收看情况向125人进行调查,有89人看过甲片,有47人看过乙片,有63人看过丙片,其中有24人三部电影全看过,20人一部也没有看过,则只看过其中两部电影的人数是( )(2009年江苏公务员考试行测A类试卷第19题) A. 69 B.65 C.57 D.46 【答案】D 解析:本题也是一道典型的三集合整体重复型题目,直接套用三集合整体重复型公式: W=x+y+z A+B+C=x×1+y×2+z×3 这里需要注意的是W=105,而非125, 105=x+y+24 89+47+63=x×1+y×2+24×3 两个方程,两个未知数,解出y=46,这里y表示只看过两部电影的人数,即所求。 例3、某高校对一些学生进行问卷调查。在接受调查的学生中,准备参加注册会计师考试的有63人,准备参加英语六级考试的有89人,准备参加计算机考试的有47人,三种考试?准备参加的有24人,准备选择两种考试参加的有46人,不参加其中任何一种考试的有15人。问接受调查的学生共有多少人?(2010年国家公务员考试行测第47题) A. 120 B.144 C.177 D.192 【答案】A 解析:本题的特征也很明显,直接套用公式,只是要注意的是,题目中最后问的是接受调查的总人数,我们求出W之后,还需要再加上不参加其中任何一种考试的那15个人, W=x+46+24 63+89+47=x×1+46×2+24×3 通过解方程,可以求出W=105,这只是至少准备参加一种考试的人数,所以接受调查的总人数为105+15=120。 例4、某市对52种建筑防水卷材产品进行质量抽检,其中有8种产品的低温柔度不合格,10种产品的可溶物含量不达标,9种产品的接缝剪切性能不合格,同时两项不合格的有7种,有1种产品这三项都不合格,则三项全部合格的建筑防水卷材产品有多少种?(2011 年国家公务员考试行测试卷第74题) A. 37 B.36 C.35 D.34
公务员考试行测备考:巧解三集合容斥原理问题 三集合容斥原理此类题型主要出现在近年来各省的省考中,主要是有三个独立的个体,此类题型主要的做题方法是公式法和作图法。近年来直接套用三集合公式的题目有所减少,开始出现条件变形的题目,不管容斥原理的题目怎么变化,但我们只要掌握住核心思想--剔除重复,那么做任何一个容斥原理题目都能够得心应手。 根据上图,可得三集合容斥原理核心公式: 一、直接利用公式型 【例1】(2012年4月联考)某公司招聘员工,按规定每人至多可投考两个职位,结果共42人报名,甲、乙、丙三个职位报名人数分别是22人、16人、25人,其中同时报甲、乙职位的人数为8人,同时报甲、丙职位的人数为6人,那么同时报乙、丙职位的人数为: A. 7人 B. 8人 C. 5人 D. 6人 【答案】A 【解析】设同时报乙、丙职位的人数为x,则根据三集合容斥原理公式有: 22+16+25-8-6-x+0=42-0,解得x=7。因此,本题答案为A选项。 二、三集合容斥原理作图型 国家公务员| 事业单位| 村官| 选调生| 教师招聘| 银行招聘| 信用社| 乡镇公务员| 各省公务员|
若在题目中任何一个位置看到“只满足”或“仅满足”,则公式法不能够再用,采用作图法来解题,注意,在作图的时候不管三七二十一,先画三个两两相交的圈,再往里填数字即可,填的时候注意从中间往外一层一层填。 【例2】(2007年江苏)一次运动会上,17名游泳运动员中,有8名参加了仰泳,有10名参加蛙泳,有12名参加了自由泳,有4名既参加仰泳又参加蛙泳,有6名既参加蛙泳又参加自由泳,有5名既参加仰泳又参加自由泳,有2名这3个项目都参加,这17名游泳运动员中,只参加1个项目的人有多少?() A.5名 B.6名 C.7名 D.4名 【答案】B 【解析】本题问题中出现了“只”,故只能采用作图法。于是有 仰 只参加1个项目的人数为1+2+3=6。因此,本题答案为B选项。 国家公务员| 事业单位| 村官| 选调生| 教师招聘| 银行招聘| 信用社| 乡镇公务员| 各省公务员|
容斥原理之三者容斥问题 浙江行测答题技巧:容斥原理之三者容斥问题 中公教育考试研究院宋丽娜:容斥原理是行测数学运算中常考知识点。容斥原理是指在计数时,必须注意无一重复,且无遗漏。这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。 例1:一个班级的学生数学和语文每人至少喜欢其中一种,其中喜欢数学课的有49人,喜欢语文课的有52人,二者都喜欢的有21人,则这个班级有多少人? 中公点拨:本题就是一个容斥问题,解决此问题的方法就是先算:49+52=101(把含于某内容中的所有对象的数目先计算出来),然后再把计数时重复计算的数目排斥出去即:101-21=80人,则整个班级的人数就有80人。 三者容斥问题是行测数学运算中常考也相对较复杂的容斥问题。所谓三者容斥是指在题干中有三种集合(集合就是具有共同属性所以元素的的整体,例如上题中喜欢数学的人构成一个集合)。 三者容斥问题有一个基本公式:A,B,C代表三个集合,则有 A∪BUC=A+B+C-A∩B-A∩C-B∩C+ A∩B∩C 这个公式表达的含义是,A+B+C再减去两两相交之后,中间E(即A∩B∩C)这部分被减没了。而容斥原理的基本思想是计数时不重复不漏掉,故要再加回来,所以又加了一个A∩B∩C。 例2. 实验小学的小记者对本校100名同学进行调查,调查他们对三种大球(篮球、足球、排球)的与否。结果显示:他们都至少喜欢三种大球中的一种,其中有58人喜欢篮球,有68人喜欢足球,有62人喜欢排球,而且,篮球和足球都喜欢的有45人,足球和排球都喜欢的有33人,三种球都喜欢的有12人。篮球和排球都喜欢的多少人?
国考:公式法解容斥问题(三集合标准型)河北公务员考试的《行测职业能力测验》包括五大部分内容:言语理解与表达、数量关系、判断推理、常识判断和资料分析,主要考察考生是否具有从事公务员职业必须具备的基本素质和潜在能力。河北华图教育精心整理了河北公务员行测真题及其他公务员笔试资料供考生备考学习。 在行测考试当中,有一类问题叫做容斥问题。什么题目我们归结为容斥问题呢?一般情况下,有符合A,有符合B,有符合AB,有AB都不符合等这一类题干,我们就把他归结为容斥问题。容斥问题可以分为二集合容斥和三集合容斥。解题思路有画图法和公式法。一般情况下,只要我们能牢牢地背会相关公式,考试的时候就能很快的做出答案,节省考试时间。今天我们一起来看一下三集合容斥标准型公式。 三集合容斥标准型公式:A+B+C-AB-BC-AC+ABC=总数-都不符合。 下面我们一起来看寄到容斥问题的例题: 【例】(2009-国家-81)如图所示,X、Y、Z 分别是面积为64、180、160 的三张不同形状的纸片。它们部分重叠放在一起盖在桌面上,总共盖住的面积为290。且X 与Y、Y 与Z、Z 与X 重叠部分面积分别为24、70、36。问阴影部分的面积是多少?() A.15 B.16 C.14 D.18 【解析】此题为容斥原理问题,根据三集合容斥标准型公式:A+B+C-AB-BC-AC+ABC=总数-都不符合。根据题意,设阴影部分为x,列方程有:290=64+180+160-24-70-36+x,解得x=16。选择B。 由此可见,如果能够熟练地记住公式,其实这类问题我们完全可以在1分钟以内做出来的。我们再来看一道例题: 【例】对39 种食物中是否含有甲、乙、丙三种维生素进行调查,结果如下:含甲的有17 种,含乙的有18 种,含丙的有15 种,含甲、乙的有7 种,含甲、丙的有6种,含乙、丙的有9 种,三种维生素都不含的有7 种,则三种
三集合容斥非标准公式原理 容斥原理一直都是各省行测考试的重点,尤其是三集合容斥原理,屡出不穷。这次,小编带领大家一起来好好的看看目前的有关三集合容斥原理的题型概况和通用思路。 三集合容斥原理按题型可以分为两种题型,一种为标准型公式,另一种为变异型公式,接下来,我们就着重看看三集合容斥原理的解题方法 1.解题步骤 涉及三个事件的集合,解题步骤分三步:①画文氏图;②弄清图形中每一部分所代表的含义,填充各部分的数字;③代入公式(A∪B∪C=A+B+C-A∩B-A∩C-B∩C+A∩B∩C)进行求解。 2.解题技巧 三集合类型题的解题技巧主要包括一个计算公式和文氏图。 公式:总数=各集合数之和-两集合数之和+三集合公共数+三集合之外数 【例1】(陕西2015)针对100名旅游爱好者进行调查发现,28人喜欢泰山,30人喜欢华山,42人喜欢黄山,8人既喜欢黄山又喜欢华山,10人既喜欢泰山又喜欢黄山,5人既喜欢华山又喜欢黄山,3人喜欢这三个景点,则不喜欢这三个景点中任何一个的有()人。 A.20 B.18 C.17 D.15 【解析】可以用上述公式,我们将数据逐个代入可得:28+30+42-8-10-5+3=100-x,其中x为我们要求的量,求得x=20,答案选择A。 【例2】(国家2015)某企业调查用户从网络获取信息的习惯,问卷回收率为90%。调查对象中有179人使用搜索引擎获取信息,146人从官方网站获取信息,246人从社交网络获取信息,同时使用这三种方式的有115人,使用其中两种的有24人,另有52人这三种方式都不使用,问这次调查共发出了多少份问卷?() A.310 B.360
教学目标 1. 了解容斥原理二量重叠和三量重叠的内容; 2. 掌握容斥原理的在组合计数等各个方面的应用. 知识要点 一、两量重叠问题 在一些计数问题中,经常遇到有关集合元素个数的计算?求两个集合并集的元素的个数,不能简单地把 两个集合的元素个数相加,而要从两个集合个数之和中减去重复计算的元素个数,即减去交集的元素个数, 用式子可表示成: AUB A B AI B (其中符号“ U ”读作“并”,相当于中文“和”或者“或”的意思; 符号“ I ”读作“交”,相当于中文“且”的意思. )则称这一公式为包含与排除原理,简称容斥原理?图示 AI B ,即阴影面积?图示 第一步:分别计算集合 A 、B 的元素个数,然后加起来,即先求 A B (意思是把A B 的一切元素都“包含” 进来,加在一起); 第二步:从上面的和中减去交集的元素个数,即减去 C AI B (意思是“排除”了重复计算的元素个数 )? 、三量重叠问题 A 类、 B 类与 C 类元素个数的总和 A 类元素的个数 B 类元素个数 C 类元素个数 既是A 类又是B 类 的元素个数 既是B 类又是C 类的元素个数 既是A 类又是C 类的元素个数 同时是A 类、B 类、C 类的元 素个数.用符号表示为: AUBUC A B C AI B BI C AI C AI BI C .图示如下: 如下:A 表示小圆部分, B 表示大圆部分, C 表示大圆与小圆的公共部分,记为: 包含与排除原理告诉我们,要计算两个集合 A B 的并集AU B 的元素的个数,可分以下两步进行:
例题精讲 【例1】 “走美”主试委员会为三?八年级准备决赛试题。 每 个年级12道题,并且至少有8道题与其他各年 级都不同。如果每道题出现在不同年级,最多只能出现 3次。本届活动至少要准备 道决赛 试题。 【考点】容斥原理之最值问题 【难度】4星 【题型】填空 【关键词】走美杯,4年级,决赛,第9题 【解析】每个年级都有自己8道题目,然后可以三至五年级共用 4道题目,六到八年级共用 4道题目,总共有 8 6 4 2 56 (道)题目。 【答案】56题 【例2】 将1?13这13个数字分别填入如图所示的由四个大小相同的圆分割成的 个圆内的7个数相加,最后把四个圆的和相加,问:和最大是多少? 【考点】容斥原理之最值问题 【难度】4星 【题型】填空 【解析】越是中间,被重复计算的越多,最中心的区域被重复计算四次,将数字按从大到小依次填写于 被重复计算多的区格中,最大和为: 13 X 4+ (12+11 + 10+9 ) X 3+ 8+7+6+5 ) X 2+ 4+3+2+1 ) =240. 【答案】240 【例3】如图,5条同样长的线段拼成了一个五角星?如果每条线段上恰有 这个五角星上红色点最少有多少个 ? 目 tMlF 13个区域中,然后把每 1994个点被染成红色,那么在