高中数学竞赛讲义-容斥原理 新人教A 版VIP免费

§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人合作过，那么，其中一定有四位数学家两两合作过。用心爱心专心15．把个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合。6．给定1978个集合，每个集合都含有40个元素，已知其中任意两个集合都恰有一个公共元，证明：存在一个元素，它属于全部集合。7．在个元素组成的集合中取个不同的三元子集。证明：其中必有两个，它们恰有一个公共元。例题答案：1．分析；n=7时，集合{7，6，5，4，3，2，1}的非空子集有个，虽然子集数目有限，但是逐一计算各自的“交替和”再相加，计算量仍然巨大，但是，根据“交替和”的定义，容易看到集合用心爱心专心2{1，2，3，4，5，6，7}与{1，2，3，4，5，6}的“交替和”是7；可以想到把一个不含7的集和A与的“交替和”之和应为7。那么，我们也就很容易解决这个问题了。解：集合{1，2，3，4，5，6，7}的子集中，除去{7}外还有个非空子集合，把这个非空子集两两结组后分别计算每一组中“交替和”之和，结组原则是设这是把结合为一组，显然，每组中，“交替和”之和应为7，共有组.所以,所有“交替和”之和应该为。说明：我们在这道题的证明过程中用了这类题目最典型的解法。就是“对应”的方法，“对应”的方法在解决相等的问题中应用得更多。2．分析：自然地设A={数学总评优秀的人}B={物理总评优秀的人}C={化学总评优秀的人}则已知|A|=21|B|=19|C|=20这表明全班人数在41至48人之间。仅数学优秀的人数是可见仅数学优秀的人数在4至11人之间。同理仅物理优秀的人数在3至10人之间。同理仅化学优秀的人数在5至12人之间。解：（略）。说明：先将具体的实际生活中的问题数学化，然后根据数学理论来解决这个问题不仅是竞赛中常见情况，也是在未来学习中数学真正有用的地方。3．分析1：用“筛法”找出不超过120的质数(素数)，计算它们的个数，从120中去掉质数，再去掉“1”，剩下的即是合数。用心爱心专心3解法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...