2013高中数学奥数培训资料之容斥原理

《2013高中数学奥数培训资料之容斥原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、兰州成功私立中学高中奥数辅导资料（内部资料）§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、子集的“交替和”的总和。2．某班对数学、物理、化学三科总评成绩统计如下：优秀的人数：数学21个，物理19个，化学20个，数学物理都优秀9人，物理化学都优秀7人。化学数学都优秀8人。这个班有5人任何一科都不优秀。那么确定这个班人数以及仅有一科优秀的三科分别有多少个人。3．计算不超过120的合数的个数4．1992位科学家，每人至少与1329人合作过，那么，其中一定有四位数学家两两合作过。5．把个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等

3、于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合。6．给定1978个集合，每个集合都含有40个元素，已知其中任意两个集合都恰有一个公共元，证明：存在一个元素，它属于全部集合。7．在个元素组成的集合中取个不同的三元子集。证明：其中必有两个，它们恰有一个公共元。课后练习1．一个集合含有10个互不相同的十进制两位数，证明：这个集合必有两个无公共元素的子集合，这两个子集元素和相等。2．是否存在两个以非页整数为元素的集合A、B，使得任一个非负整数

4、都可以被A、B之中各取一数之和唯一表出。3．对每个使得在n元集合中，可以取出k个子集，其中任意两个的交非合。4．能否把分成两个积相等的不交集合。课后练习答案1．我们可以发现对每个数，它出现在个子集之中，因此所有子集中的的和为，那么全部元素在全部子集之中的和为。　　2．利用二进制来考虑此题，小明的前9包分别有钱1分（2），10分（2），100分（2），1000分（2），10000分（2），100000分（2），1000000分（2），10000000分（2），100000000分（2），剩下一包装剩下的钱（以上

5、数皆为二进制）就可以了。　　3．不能。反证法。设存在合乎题中条件的一种分法，如果和同属于一个子集，则记为，否则记为，对，若分在三个集合中则称为好的。　　都是好的。　　，，而，故　　在第二组中用代替，故是好的。故。　　由此即，但。矛盾！有这样一个结论阶集合的子集若满足且则的最大值为，代入本题得为。例题答案：1．分析；n=7时，集合{7，6，5，4，3，2，1}的非空子集有个，虽然子集数目有限，但是逐一计算各自的“交替和”再相加，计算量仍然巨大，但是，根据“交替和”的定义，容易看到集合{1，2，3，4，5，6，7

6、}与{1，2，3，4，5，6}的“交替和”是7；可以想到把一个不含7的集和A与的“交替和”之和应为7。那么，我们也就很容易解决这个问题了。　　解：集合{1，2，3，4，5，6，7}的子集中，除去{7}外还有个非空子集合，把这个非空子集两两结组后分别计算每一组中“交替和”之和，结组原则是设这是把结合为一组，显然，每组中，“交替和”之和应为7，共有组.所以,所有“交替和”之和应该为。　　说明：我们在这道题的证明过程中用了这类题目最典型的解法。就是“对应”的方法，“对应”的方法在解决相等的问题中应用得更多。2．分析

7、：自然地设A={数学总评优秀的人}　B={物理总评优秀的人}C={化学总评优秀的人}　　则已知

8、A

9、=21

10、B

11、=19

12、C

13、=20这表明全班人数在41至48人之间。仅数学优秀的人数是　　可见仅数学优秀的人数在4至11人之间。同理仅物理优秀的人数在3至10人之间。同理仅化学优秀的人数在5至12人之间。解：（略）。说明：先将具体的实际生活中的问题数学化，然后根据数学理论来解决这个问题不仅是竞赛中常见情况，也是在未来学习中数学真正有用的地方。3．分析1：用“筛法”找出不超过120的质数(素数)，计算它们的个数，从1

14、20中去掉质数，再去掉“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(个)(附：筛法：从小到大按顺序写