高中数学竞赛系列讲座

高中数学竞赛系列讲座第一讲集合与容斥原理数学是一门非常迷人的学科，久远的历史，勃勃的生机使她发展成为一棵枝叶茂盛的参天大树，人们不禁要问：这根大树到底扎根于何处？为了回答这个问题，在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。集合是一种基本数学语言、一种基本数学工具。它不仅是高中数学的第一课，而且是整个数学的基础。对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上，而要随着数学学习的进程而不断深化，自觉使用集合语言(术语与符号)来表示各种数学名词，主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系，表示平面轨迹及其关系、表示方程(组)或不等式(组)的解、表示充要条件，描述排列组合，用集合的性质进行组合计数等。一、 学习集合要抓住元素这个关键。遇到集合问题，首先要弄请：集合里的元素是什么。集合学习中，新名词新概念多。如集合、元素、有限集、无限集、列举法、描述法、子集、真子集、空集、非空集合、全集、补集、交集、并集等。新关系新符号多，如属于、不属于、包含、包含于、真包含、真包含于、相等、不相等、相交、相并、互补(、 、N、N、Z、Q、R、CsA、I、)等，这些新概念新关系，多而抽象。在这千头万绪中，应该抓住“元素”这个关键，因为集合是由元素确定的，“子、全、补、交、并、空”等集合也都是通过元素来定义的。集合中元素的特征即“确定性”，“互异性”、“无序性”也就是元素的性质。集合的分类(有限集与无限集)与表示方法(列举法与描述法)也是通过元素来刻画的。元素是集合的基本内核，研究集合，首先就要确定集合里的元素是什么。例1设AXX=a2+b2,a、bZ，X1，X2A，求证：X1X2A。分析：A中的元素是什么？是自然数，即由两个整数a、b的平方和构成的自然数，亦即从0、1、4、9、16、25，n2，中任取两个(相同或不相同)数加起来得到的一个和数，本题要证明的是：两个这样的数的乘积一定还可以拆成两个自然数的平方和的形式，即(a2+b2)(c2+d2)=(X)2+(Y)2，X,YZ证明：设X1a2+b2，X2=c2+d2，a、b、c、dZ则X1X2(a2+b2)(c2+d2) a2c2+b2d2+b2c2+a2d2 a2c2+2acbd+b2d2+b2c2-2bcad+a2d2 (ac+bd)2+(bc-ad)2又a、b、c、dZ，故ac+bd、bc-adZ，从而X1X2A说明：本题的证明中根据A中元素的结构特点使用了配方法和“零”变换(02abcd-2abcd)。命题的结论说明集合A对于其中元素的“”运算是封闭的。类似的有：自然数集合N对于“”、“”运算是封闭的整数集合Z对于“”、“”、“”运算是封闭的有理数集合Q对于“”、“”、“”、“”运算是封闭的(除数不能是零)实数集合对于“”、“”、“”、“”四则运算是封闭的复数集合对于“”、“”、“”、“”、乘方、开方运算都是封闭的。例2已知集合M直线，N抛物线，则MN中元素的个数为()(A)0(B)0,1，2其中之一(C)无穷 (D)无法确定分析M中的元素为直线，是无限集；N中的元素为抛物线，它也是无限集。由于两集合中的元素完全不同，即既是直线又是抛物线(曲线)的图形根本不存在，故MN，选(A)说明若想当然地误认为M中的元素是直线上的点，N中的元素是抛物线上的点，当误认为是判断直线与抛物线的位置关系即相交，相切、相离时，会选(B)；例3已知AY|YX24X3，XR，BYYX22X2，XR求AB先看下面的解法：解：联立方程组YX24X3YX22X2消去Y，得2X22X10 因为(2)242140，方程无实根，故AB 说明上述解法对吗？画出两抛物线的图象：YX24X+3=(X-1)(X-3),开口向上，与X轴交于(1,0)、(3,0)，对称轴为X2，纵截距为3；YX22X2(X1)23，开口向下，与X轴交于(13,0)、(13,0)，对称轴为X1，观察可知，它们确实没有交点，但这解答对吗，亲爱的读者？图111回头审视两集合A、B，它们并不是由抛物线上的点构成的点集。两集合中的元素都是实数Y，即当XR时相应的二次函数的函数值所组成的集合，即二次函数的值域集合。故由YX24X3(X2)211，YX22X2(X1)233，可知AYY1，BYY3，它们的元素都是“实数”，从而有MNY1Y3你看，认清集合中元素的构成是多么重要！二、 集合中待定元素的确定例4已知集合MX，XY，lg(xy)，S0，X，Y，且MS，则(X1/Y)(X21/Y2)(X20021/Y2002)的值等于()，(据1987年全国高中数学联赛试题改编)。分析：解题的关键在于求出X和Y的值，而X和Y分别是集合M与S中的元素。这一类根据集合的关系反过来确定集合元素的问题，要求我们要对集合元素的基本性质即确定性、异性、无序性及集合之间的基本关系(子、全、补、交、异、空、等)有本质的理解，对于两个相等的有限集合(数集)，还会用到它们的简单性质：(a) 相等两集合的元素个数相等；(b) 相等两集合的元素之和相等；(c) 相等两集合的元素之积相等；对于本题，还会用到对数、绝对值的基本性质。解：由MS知，两集合元素完全相同。这样，M中必有一个元素为0，又由对数的性质知，0和负数没有对数，所以XY0，故X，Y均不为零，所以只能有lg(XY)0，从而XY1MX，1，0，S0，X，1/X再由两集合相等知当X1时，M1,1，0，S0,1，1，这与同一个集合中元素的互异性矛盾，故X1不满足题目要求；当X1时，M1,1，0，S0,1，1，MS，从而X1满足题目要求，此时Y1，于是X2K11/Y2K12(K0,1，2，)，X2K1/Y2K2(K1,2，)故所求代数式的值为0例5设AXX2+aX+b=0BXX2+CX+15=0若AB3,5，AB3，求a,b,c。分析：由方程的根的定义及一元二次方程的根与系数的关系(韦达定理)，结合、的 概念入手，可以寻得解题的突破口。解：由AB3 知3B,由韦达定理知此时，B3,5AB又由AB3知5A；而(AB)A(AB)，故A3，即二次方程X2aX+b0有二等根X1X23，根据韦达定理，有X1X26a，X1X29b所以，a6，b9，c8三有限集元素的个数(容斥原理)请看以下问题：开运动会时，高一某班共有28名同学参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳比赛和田径比赛的有3人，同时参加游泳比赛和球类比赛的有3人，没有人同时参加三项比赛，问同时参加田径比赛和球类比赛的有多少人？只参加游泳一项比赛的有多少人？解决这个问题需要我们研究集合元素的个数问题(请读者参阅高中教材数学第一册(上)P23P23阅读材料“集合元素的个数”。)为此我们把有限集合A的元素个数记作card(A)可以证明：(1) card(AB)card(A)card(B)card(AB)；(2) card(ABC)=card(A)+card(B)+card(C)-card(AB)-card(AC)-card(BC)+card(ABC)如下图所示：由图131，有card(AB)=+=(+)+(+)-card(A)+card(B)-card(AB)card(Cu(AB)=card(U)-card(AB)=card(U)-card(A)-card(B)+card(AB)又由图132，有card(ABC)=+(+)+(+)+(+)-(+)-(+)-(+)+card(A)+card(B)+card(C)-card(AB)-card(AC)-card(BC)+card(ABC)现在我们可以来回答刚才的问题了：设A参加游泳比赛的同学，B参加田径比赛的同学，C参加球类比赛的同学则card(A)=15，card(B)=8，card(C)=14，card(ABC)=28且card(AB)=3，card(AC)=3，card(ABC)=0由公式得281581433card(BC)+0即card(BC)=3所以同时参加田径和球类比赛的共有3人，而只参加游泳比赛的人有15339(人) 例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的合数有12013089(个)(附：筛法：从小到大按顺序写出1120的所有自然数：先划掉1，保留2，然后划掉2的所有倍数4,6，120等；保留3，再划掉所有3的倍数6,9117、120等；保留5，再划掉5的所有倍数10,15，120；保留7，再划掉7的所有倍数，这样，上面数表中剩下的数就是120以内的所有素数，这种方法是最古老的寻找素数的方法，叫做“埃斯托拉筛法”)说明：当n不很大时，计算1n中的合数的个数困难不大；但当n很大时，利用筛法就很困难、很费时了，必须另觅他途。分析2受解法1的启发，如果能找出1n中质数的个数m，则n1m就是不超过n的合数的个数。由初等数论中定理：a是大于1的整数。如果所有不大于a的质数都不能整除a，那么a是质数。因为120121112，12011，所以不超过120的合数必是2或3或5或7的倍数，所以只要分别计算出不超过120的2、3、5、7的倍数，再利用“容斥原理”即可。解法2：设S1a13120,2a；S2b1b120,3b；S3c13120,5c；S4=d1d120,7d，则有：card(S1)120/2=60，card(S2)120/340，card(S3)120/524，card(S4)120/717；(n表示n的整数部分，例如2,42，)card(S1S2)120/2320，card(S1S3)120/2512，card(S1S4)120/278，card(S2S3)120/358，card(S2S4)120/375，card(S3S4)120/573，card(S1S2S3)120/2354，card(S1S2S4)120/2372，card(S1S3S4)120/2571，card(S2S3S4)120/3571，card(S1S2S3S4)120/23570card(S1S2S3S4)card(S1)card(S2)card(S3)card(S4)card(S1S2)card(S1S3)card(S1S4)card(S2S3)card(S2S4)card(S3S4)card(S1S2S3)card(S1S2S4)card(S1S3S4)card(S2S3S4)card(S1S2S3S4)(60402417)-(20+12+8+8+5+3)+(4+2+1+1)-0141-568932，3，5，7是质数93489即不超过120的合数共有89个。四、 有限集合子集的个数问题：(1) 集合a一共有几个子集？(2) 集合a，b一共有几个子集？(3) 集合a,b,c一共有几个子集？(4) 集合a,b,c,d一共有几个子集？(5) 猜想集合a1,a2，an一共有几个子集？(6) 利用上述猜想确定符合下列条件的集合M的个数：1,2M1,2，3,4，5,6，7,8，9,10。以上诸问题都牵涉到有限集合子集的个数问题。有限集合a的子集有：，a；共两个有限集合a,b的子集有：，a，b，a,b；共422个；有限集合a,b,c的子集有：；a，b，c；a,b，a,c，b,c；a,b,c；823个；有限集合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；共1624个。这里，a,b,c,d的子集可以分成两部分，一部分不包括d，是a,b,c的子集；另一部分包括d，是a,b,c中每一个子集与d的并集。循此思路，注意到2，422，823，1624的规律，可以猜想有限集合a1,a2，an的子集共有2n个，其中非空子集有2n1个；真子集也有2n1个，非空真子集有2n112n2个。利用上述猜想，问题(6)中集合M的个数应当有28256个。例7一个集合含有10个互不相同的两位数。试证，这个集合必有2个无公共元素的子集合，此两子集的各数之和相等。分析：两位数共有10,11，,99，计99990个，最大的10个两位数依次是90,91，,99，其和为945，因此，由10个两位数组成的任意一个集合中，其任一个子集中各元素之和都不会超过945，而它的非空子集却有21011023个，这是解决问题的突破口。解：已知集合含有10个不同的两位数，因它含有10个元素，故必有2101024个子集，其中非空子集有1023个，每一个子集内各数之和都不超过909198999451023，根据抽屉原理，一定存在2个不同的子集，其元素之和相等。如此2个子集无公共元素，即交集为空集，则已符合题目要求；如果这2个子集有公共元素，则划去它们的公共元素即共有的数字，可得两个无公共元素的非空子集，其所含参数之和相等。说明：此题构造了一个抽屉原理模型，分两步完成，计算子集中数字之和最多有945个“抽屉”，计算非空子集得1023个“苹果”，由此得出必有两个子集数字之和相等。第二步考察它们有无公共元素，如无公共元素，则已符合要求；如有公共元素，则去掉相同的数字，得出无公共元素并且非空的两个子集，满足条件。可见，有限元素子集个数公式起了关键作用。例8设A1,2，3，n，对XA，设X中各元素之和为Nx，求Nx的总和解：A中共有n个元素，其子集共有2n个。A中每一个元素在其非空子集中都出现了2n-1次，(为什么？因为A的所有子集对其中任一个元素i都可分为两类，一类是不含i的，它们也都是1,2，i-1,i+1,n的子集，共2n-1个；另一类是含i的，只要把i加入到刚才的2n-1个子集中的每一个中去)。因而求A的所有子集中所有元素之和Nx的总和时，A中每一个元素都加了2n-1次，即出现了2n-1次，故得12n-122n-1n2n-1(12n)2n-1n(n+1)/22n-1n(n+1)2n-2说明：这里运用了整体处理的思想及公式12n(1/2)n(n+1)，其理论依据是加法的交换律、结合律、乘法的意义等。得出集合中每一个元素都在总和中出现了2n-1次，是打开解题思路之门的钥匙孔。习题一1、 化简集合2、 设集合A1，a,b,B=a,a2,ab,且AB，求实数a,b3、 高一(1)班的学生中，参加语文课外小组的有20人，参加数学课外小组的有22人，既参加语文小组又参加数学小组的有15人，既未参加语文小组又未参加数学小组的有15人。问高一(1)班共有学生几人？4、 设非空集合A1,2，3,4，5,6，7，且当aA时必有8aA，这样的A共有()个。5、 已知A296的约数，B999的约数，则card(AB)()6、 对于集合AXX3n,n=1,2,3,4BXX3k,k=1,2,3若有集合M满足ABMAB，则这样的M有多少个？参考答案1 A(11/13，3/13)，(列举法)或(描述法)2 A=-1,b=03 47个4 15个5 2，AB1,376 共8个易知A3,6，9,12B3,9，27，故AB3,9，AB3,6，9,12,27，故M可以这样构造问题归结为求N的个数，要即集合6,12,27的子集数，所以M有238个。