高中数学竞赛系列讲座01

高中数学竞赛系列讲座第一讲集合与容斥原理数学是一门非常迷人的学科，久远的历史，勃勃的生机使她发展成为一棵枝叶茂盛的参天大树，人们不禁要问：这根大树到底扎根于何处？为了回答这个问题，在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。集合是一种基本数学语言、一种基本数学工具。它不仅是高中数学的第一课，而且是整个数学的基础。对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上，而要随着数学学习的进程而不断深化，自觉使用集合语言(术语与符号)来表示各种数学名词，主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系，表示平面轨迹及其关系、表示方程(组)或不等式(组)的解、表示充要条件，描述排列组合，用集合的性质进行组合计数等。一、学习集合要抓住元素这个关键。遇到集合问题，首先要弄请：集合里的元素是什么。集合学习中，新名词新概念多。如集合、元素、有限集、无限集、列举法、描述法、子集、真子集、空集、非空集合、全集、补集、交集、并集等。新关系新符号多，如属于、不属于、包含、包含于、真包含、真包含于、相等、不相等、相交、相并、互补(∈、、、、N、N※、Z、Q、R、∩、∪、CsA、I、＝、≠……)等，这些新概念新关系，多而抽象。在这千头万绪中，应该抓住“元素”这个关键，因为集合是由元素确定的，“子、全、补、交、并、空”等集合也都是通过元素来定义的。集合中元素的特征即“确定性”，“互异性”、“无序性”也就是元素的性质。集合的分类(有限集与无限集)与表示方法(列举法与描述法)也是通过元素来刻画的。元素是集合的基本内核，研究集合，首先就要确定集合里的元素是什么。例1．设A＝{X∣X=a2+b2,a、b∈Z}，X1，X2∈A，求证：X1×X2∈A。分析：A中的元素是什么？是自然数，即由两个整数a、b的平方和构成的自然数，亦即从0、1、4、9、16、25……，n2，……中任取两个(相同或不相同)数加起来得到的一个和数，本题要证明的是：两个这样的数的乘积一定还可以拆成两个自然数的平方和的形式，即(a2+b2)(c2+d2)=(X)2+(Y)2，X,Y∈Z证明：设X1＝a2+b2，X2=c2+d2，a、b、c、d∈Z则X1×X2＝(a2+b2)(c2+d2)＝a2c2+b2d2+b2c2+a2d2＝a2c2+2ac·bd+b2d2+b2c2-2bc·ad+a2d2＝(ac+bd)2+(bc-ad)2又a、b、c、d∈Z，故ac+bd、bc-ad∈Z，从而X1X2∈A说明：本题的证明中根据A中元素的结构特点使用了配方法和“零”变换(0＝2abcd-2abcd)。命题的结论说明集合A对于其中元素的“·”运算是封闭的。类似的有：自然数集合N对于“＋”、“×”运算是封闭的整数集合Z对于“＋”、“－”、“×”运算是封闭的有理数集合Q对于“＋”、“－”、“×”、“÷”运算是封闭的(除数不能是零)实数集合对于“＋”、“－”、“×”、“÷”四则运算是封闭的复数集合对于“＋”、“－”、“×”、“÷”、乘方、开方运算都是封闭的。例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＝－40，方程③无实根，故A∩B＝φ[说明]上述解法对吗？画出两抛物线的图象：Y＝X2－4X+3=(X-1)(X-3),开口向上，与X轴交于(1,0)、(3,0)，对称轴为X＝2，纵截距为3；Y＝－X2－2X＋2＝－(X＋1)2＋3，开口向下，与X轴交于(－1－√3,0)、(－1＋√3,0)，对称轴为X＝－1，观察可知，它们确实没有交点，但这解答对吗，亲爱的读者？图1－1－1回头审视两集合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}你看，认清集合中元素的构成是多么重要！二、集合中待定元素的确定例4．已知集合M＝{X，XY，lg(xy)}，S＝{0，∣X∣，Y}，且M＝S，则(X＋1/Y)＋(X2＋1/Y2)＋……＋(X2002＋1/Y2002)的值等于()，(据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∣，1/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，于是X2K＋1＋1/Y2K＋1＝－2(K＝0,1，2，……)，X2K＋1/Y2K＝2(K＝1,2，……)故所求代数式的值为0例5．设A＝{X∣X2+aX+b=0}B＝{X∣X2+CX+15=0}若A∪B＝{3,5}，A∩B＝{3}，求a,b,c。分析：由方程的根的定义及一元二次方程的根与系数的关系(韦达定理)，结合∩、∪的概念入手，可以寻得解题的突破口。解：由A∩B＝{3}知3∈B,由韦达定理知此时，B＝{3,5}＝A∪B又由A∩B＝{3}知5A；而(A∩B)A(A∪B)，故A＝{3}，即二次方程X2＋aX+b＝0有二等根X1＝X2＝3，根据韦达定理，有X1＋X2＝6＝－a，X1X2＝9＝b所以，a＝－6，b＝9，c＝－8三．有限集元素的个数(容斥原理)请看以下问题：开运动会时，高一某班共有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是质数。因为120121＝112，√12011，所以不超过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(