集合与容斥原理

第一讲集合与容斥原理主讲：张贵学第一讲集合与容斥原理•集合是一种数学语言、一种基本的数学工具。它不仅是高中数学学习的第一课，而且是整个数学的基础，对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上，而应随着数学学习的进程而不断深化，自觉使用集合语言（术语与符号）来表示各种数学名词，主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系，表示平面轨迹及其关系，表示方程（组）或不等式（组）的解，表示充要条件，描述排列组合，用集合的性质进行组合计数等。第一讲集合与容斥原理一、学习集合要抓住元素这个关键。遇到集合问题，首先要弄请：集合里的元素是什么。元素是集合的基本内核，研究集合，首先就要确定集合里的元素是什么。例1、设A={x|x=a2+b2,a,b∈Z},x1,x2∈A求证：x1x2∈A第一讲集合与容斥原理分析:根据集合A的特性,只要证明x1x2能表示成两个整数的平方和的形式即可.解:设x1=a2+b2,x2=c2+d2,a,b,c,d∈A,则有x1x2=(a2+b2)(c2+d2)=(ac+bd)2+(ad-bc)2,显然x1x2∈A.第一讲集合与容斥原理例2、已知A={y|y=x2-4x+3,x∈R},B={y|y=-x2-2x+2,x∈R},求A∩B.分析：画出两抛物线的图象，观察可知，两条抛物线没有交点，这是否意谓A∩B=?解;A={y|y≥－1}，B={y|y≤3},它们的元素都是“实数”，从而有A∩B={y|－1≤y≤3}第一讲集合与容斥原理二、集合中待定元素的确定例3、已知M={x,xy,lg(xy)}，S={0,|x|,y},M=S,则(x+1／y)+(x2+1／y2)+…+(x2010+1／y2010)的值等于()。解：由M=S知，两集合元素完全相同。这样,M中必有一个元素为0，又由对数的性质知，0和负数没有对数，所以xy，故x,y均不为零，所以只能有lg(xy)=0，从而xy=1，再由两集合相等知x=-1,M=S={-1,1,0}.此时y=-1,所求代数式的值为0.第一讲集合与容斥原理例4、设A={x|x2+ax+b=0}B={x|x2+cx+15=0}，若A∩B＝{3}，求a,b,c的值。解：由A∩B＝{3}知3∈B,由韦达定理知此时，B＝{3,5}＝A∪B.又由A∩B＝{3}知5A；故A={3}，即二次方程x2+ax+b=0有二等根，根据韦达定理,有x1+x2=-6=a，x1x2=9=b,所以a=-6，b=9,c=-8.第一讲集合与容斥原理三、有限集元素的个数(容斥原理)请看以下问题：开运动会时，高一某班共有28名同学参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳比赛和田径比赛的有3人，同时参加游泳比赛和球类比赛的有3人，没有人同实参加三项比赛，问同时参加田径比赛和球类比赛的有多少人？只参加游泳一项比赛的有多少人？解决这个问题需要我们研究集合元素的个数问题。我们用|A|或card(A)表示集合A中元素的个数，（例如若A={1，2，3}，则|A|=3）可以证明：1、|A∪B|=∣A∣+∣B∣-∣A∩B∣2、∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣B∩C∣-|C∩A|+|A∩B∩C∣第一讲集合与容斥原理现在我们可以来回答刚才的问题了：设A＝{参加游泳比赛的同学}，B＝{参加田径比赛的同学}，C＝{参加球类比赛的同学}则|A|=15，|B|=8，|C|=14，|A∪B∪C|=28，且|A∩B|=3，|A∩C|=3，|A∩B∩C|=0由公式②得28＝15＋8＋14－3－3－|B∩C|+0，即|B∩C|=3所以同时参加田径和球类比赛的共有3人，而只参加游泳比赛的人有15－3－3＝9(人)第一讲集合与容斥原理例5、学校教导处对100名同学进行调查，结果有58人喜欢看球赛，有38人喜欢看戏剧，有52人喜欢看电影。另外还知道，既喜欢看球赛又喜欢看戏剧（但不喜欢看电影）的有6人，既喜欢看电影又喜欢看戏剧（但不喜欢看球赛）的有4人，三种都喜欢的有12人。问有多少同学只喜欢看电影？有多少同学既喜欢看球赛又喜欢看电影（但不喜欢看戏剧）？（假定每人至少喜欢一项）第一讲集合与容斥原理解：法1：画三个圆圈使它们两两相交，彼此分成7部分（如图）这三个圆圈分别表示三种不同爱好的同学的集合，由于三种都喜欢的有12人，把12填在三个圆圈的公共部分内（图中阴影部分），其它6部分填上题目中所给出的不同爱好的同学的人数（注意，有的部分的人数要经过简单的计算）其中设既喜欢看电影又喜欢看球赛的人数为χ，这样，全班同学人数就是这7部分人数的和，即16+4+6+（40-χ）+（36-χ）+12=100解得χ=14.只喜欢看电影的人数为36-14=22第一讲集合与容斥原理解法2：设A={喜欢看球赛的人}，B={喜欢看戏剧的人}，C={喜欢看电影的人}，依题目的条件有|A∪B∪C|=100，|A∩B|=6+12=18（这里加12是因为三种都喜欢的人当然喜欢其中的两种），|B∩C|=4+12=16，|A∩B∩C|=12，再设|A∩C|=12+χ由容斥原理二：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|得：100=58+38+52-（18+16+х+12）+12第一讲集合与容斥原理四、有限集合子集的个数这里介绍两个重要的结论：1、n个元素的有限集合的子集共有2n个，其中非空子集有2n－1个；真子集也有2n－1个，非空真子集有2n－1－1＝2n－2个。2、鸽笼原理(抽屉原理)：有n+1件或n+1件以上的物品要放到n个抽屉中,那么至少有一个抽屉里有两个或两个以上物品。第一讲集合与容斥原理例6、一个集合含有10个互不相同的两位数。试证，这个集合必有2个无公共元素的子集合，此两子集的各数之和相等。分析：两位数共有10,11，…,99，计99－9＝90个，最大的10个两位数依次是90,91，…,99，其和为945，因此，由10个两位数组成的任意一个集合中，其任一个子集中各元素之和都不会超过945，而它的非空子集却有个，这是解决问题的突破口。第一讲集合与容斥原理解：已知集合含有10个不同的两位数，因它含有10个元素，故必有210＝1024个子集，其中非空子集有1023个，每一个子集内各数之和都不超过90＋91＋…98＋99＝9451023，根据抽屉原理，一定存在2个不同的子集，其元素之和相等。如此2个子集无公共元素，即交集为空集，则已符合题目要求；如果这2个子集有公共元素，则划去它们的公共元素即共有的数字，可得两个无公共元素的非空子集，其所含参数之和相等。第一讲集合与容斥原理例7．设A＝{1,2，3，…，n}，对XA，设X中各元素之和为Nx，求Nx的总和分析：注意A中每一个元素在其非空子集中都出现了2n-1次。第一讲集合与容斥原理解：已知集合含有10个不同的两位数，因它含有10个元素，故必有210＝1024个子集，其中非空子集有1023个，每一个子集内各数之和都不超过90＋91＋…98＋99＝9451023，根据抽屉原理，一定存在2个不同的子集，其元素之和相等。如此2个子集无公共元素，即交集为空集，则已符合题目要求；如果这2个子集有公共元素，则划去它们的公共元素即共有的数字，可得两个无公共元素的非空子集，其所含参数之和相等。第一讲集合与容斥原理•巩固提高：•1、设集合A＝{1，a,b},B={a,a2,ab},且A＝B，求实数a,b•2、高一(1)班的学生中，参加语文课外小组的有20人，参加数学课外小组的有22人，既参加语文小组又参加数学小组的有15人，既未参加语文小组又未参加数学小组的有15人。问高一(1)班共有学生几人？•3、设非空集合A{1,2，3,4，5,6，7}，且当a∈A时必有（8－a）∈A，这样的A共有()个。•4、已知A＝{296的约数}，B＝{999}的约数，则card(A∩B)＝()•5、对于集合A＝{X∣X＝3n,n=1,2,3,4}，B＝{X∣X＝,k=1,2,3}•若有集合M满足A∩BMA∪B，则这样的M有多少个？•6、设＝{1,2,…,100},是的子集,且中至少含有一个立方数,则这种子集的个数是____________.•7、设，，则满足条件的所有实数a，b的值分别为．•8、求的所有子集元素的和之和。•9、给定1978个集合，每个集合都含有40个元素，已知其中任意两个集合都恰有一个公共元，证明：存在一个元素，它属于全部集合。•提示：这种题目最怕把它想难了，想得太难了，就会觉得无从下手，做数学竞赛题就需要一方面在做题之前选好方向，另一方面就是大胆尝试去做。本题我们可以先去找一个属于很多个集合的元素，最好它就是我们要找的那一个。