2013高中数学奥数培训资料之容斥原理【精选】.doc

O(∩_∩)O 兰州成功私立中学高中奥数辅导资料 （内部资料） §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人合作过，那么，其中一定有四位数学家两两合作过。 5．把个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合。 6．给定1978个集合，每个集合都含有40个元素，已知其中任意两个集合都恰有一个公共元，证明：存在一个元素，它属于全部集合。 7．在个元素组成的集合中取个不同的三元子集。证明：其中必有两个，它们恰有一个公共元。 课后练习 1．一个集合含有10个互不相同的十进制两位数，证明：这个集合必有两个无公共元素的子集合，这两个子集元素和相等。 2．是否存在两个以非页整数为元素的集合A、B，使得任一个非负整数都可以被A、B之中各取一数之和唯一表出。 3．对每个使得在n元集合中，可以取出k个子集，其中任意两个的交非合。 4．能否把分成两个积相等的不交集合。 课后练习答案 1．我们可以发现对每个数，它出现在个子集之中，因此所有子集中的的和为，那么全部元素在全部子集之中的和为。 　　2．利用二进制来考虑此题，小明的前9包分别有钱 1分（2），10分（2），100分（2），1000分（2），10000分（2），100000分（2），1000000分（2）（2），100000000分（2），剩下一包装剩下的钱（以上数皆为二进制）就可以了。 　　3．不能。反证法。设存在合乎题中条件的一种分法，如果和同属于一个子集，则记为，否则记为，对，若分在三个集合中则称为好的。 　　都是好的。 　　，，而 ，故 　　在第二组中用代替，故是好的。故。 　　由此 即，但。矛盾！ 有这样一个结论阶集合的子集若满足且则的最大值为，代入本题得为。 例题答案： 1．分析；n=7时，集合{7，6，5，4，3，2，1}的非空子集有个，虽然子集数目有限，但是逐一计算各自的“交替和”再相加，计算量仍然巨大，但是，根据“交替和”的定义，容易看到集合{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”，剩下的即是合数。 　　解法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、1