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

-------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册 ，应有尽有--------------

2013高中数学奥数培训资料之容斥原理（内部资料）
§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．对每个
个的交非合。



4．能否把






分成两个积相等的不交集合。
使得在n元集合中，可以取出k个子集，其中任意两






--------------------- ------------------------------------精品 文档
---- -------------------------------------------------- ---------------

-------------各类专业好文档，值得 你下载，教育，管理，论文，制度，方案手册，应有尽有--------------

课后练习答案
1．我们可以发现对每个数，它出现在个子集之中，因此所有子集中的的和为，
那么全部元素在全部子集之中的和为。
2．利用二进制来考虑此题，小明的前9包分别有钱 1分（2），10分（2），100分（2），
1 000分（2），10000分（2），100000分（2），1000000分（2），10000000分 （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、1 7、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的质数都不能
2
整除a，那么a是质数。因为120 <121＝11，√120<11，所以不超过120的合数必是2或3
或5或7的倍数，所以只要分别 计算出不超过120的2、3、5、7的倍数，再利用“容斥原
理”即可。
解法2：设S
1
＝{a∣1≤3≤120,2∣a}；S
2
＝{b∣1≤b≤120,3∣ b}；S
3
＝
{c∣1≤3≤120,5∣c}；S
4
={d∣1≤ d≤120,7∣d}，则有：
------------------------------- --------------------------精品 文档
-------------- -------------------------------------------------- -----

-------------各类专业好文档，值得你下载，教育，管理， 论文，制度，方案手册，应有尽有--------------

card(S
1
)＝[1202]=60，card(S
2
)＝[1203]＝40，card( S
3
)＝[1205]＝24，card(S
4
)
＝[1207]＝ 17；
([n]表示n的整数部分，例如[2,4]＝2，…)












c ard(S
1
∩S
2
)＝[1202×3]＝20，card(S
1
∩S
3
)＝[1202×5]＝12，
card(S
1
∩ S
4
)＝[1202×7]＝8，card(S
2
∩S
3
) ＝[1203×5]＝8，
card(S
2
∩S
4
)＝[1203 ×7]＝5，card(S
3
∩S
4
)[1205×7]＝3，
c ard(S
1
∩S
2
∩S
3
)[1202×3×5]＝4， card(S
1
∩S
2
∩S
4
)＝[1202×3×7]＝ 2，
card(S
1
∩S
3
∩S
4
)＝[120 2×5×7]＝1，card(S
2
∩S
3
∩S
4
)＝[1 203×5×7]＝1，
card(S
1
∩S
2
∩S
3< br>∩S
4
)＝[1202×3×5×7]＝0
∴card(S
1< br>∪S
2
∪S
3
∪S
4
)＝card(S
1< br>)＋card(S
2
)＋card(S
3
)＋card(S
4
)－card(S
1
∩S
2
)－
card(S
1< br>∩S
3
)－card(S
1
∩S
4
)－card(S
2
∩S
3
)－card(S
2
∩S
4
)－ card(S
3
∩S
4
)＋card(S
1
∩S
2
∩S
3
)
＋card(S
1
∩S
2
∩S< br>4
)＋card(S
1
∩S
3
∩S
4
)＋c ard(S
2
∩S
3
∩S
4
)－card(S
1< br>∩S
2
∩S
3
∩S
4
)＝(60＋40
＋2 4＋17)-(20+12+8+8+5+3)+(4+2+1+1)-0＝141-56＋8＝93
∵2，3，5，7是质数
∴93－4＝89
即不超过120的合数共有89个。
4．分析：在与一个人A合作的人中我们找到B。再说明一定有人与A和B都合作过为C。
最后 再说明有人与A、B、C都合作过为D，那么A、B、C、D就是找的人了。
证明：一个人A。不妨设B与之合作。那么
。即C
与A和B均合作过，分别表示与A、B合作过的人的集合。同样地，
。
所以存在。则A、B、C、D就是所求，证毕。
说明：把一个普通的叙述性问题转化为集 合的语言描述的问题通常为解题的关键之处，
也是同学们需加强的。
5．分析：首先考虑到是 一个很特殊的数，其次我们发现若两个集合的元素个数除以2的
若干次幂后若为奇数，那么，它们之间挪 后就应为偶数这一事实，若还不能想到解答就试一
下，时的情况，相信解答就不会难找到了。
证明：考虑含奇数个元素的子集（如果有这样的子集），因为所有子集所含元素的个数
-------- -------------------------------------------------精 品 文档
----------------------------------------- ----------------------------

---------- ---各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有------------ --

总和是偶数，所以具有奇数个元素的子集个数也是偶数，任意将所有含有奇数个元素的 子集
配成对，对每对子集按题目要求的规则移动：从较大的子集挪出一些元素，添加到较小的子
集，挪出的元素个数为较小子集的元素个数，于是得到的所有子集的元素个数都是偶数，现
在考虑元素个 数不被4整除的子集，如果
因此设
，则总共有两个元素，它们在同一个子集，
，因为子 集的元素个数的总数被4整除，因此这样的子集的个数为偶数，任意
将这样的子集配成对，对每一对子集 施行满足题目要求的挪动，于是得到的每个子集数均可
被4整除，依此做下去，最后得到的每个子集元素 个数均可被
子集，它的元素个数为，证毕。
整除，也就是只能有一个
说明：这道题的 证明中隐含了一种单一变量在变化时变化方向相同这一性质，就这道题
来说，一直在增加的就是各子集元 素个数被2的多少次幂整除的这个幂次数，这是一大类问
题，除了这种变化量，还要经常考虑变化中的不 变量。
6．分析：我们可以先去找一个属于很多个集合的元素，最好它就是我们要找的那一个。 证明：考虑给定的1978个集合中任意一个集合
此，存在
集合，而集合
合，…< br>，它和其它1977个集合都相交，因
中每个元素至多属于49个，使得它至少属于其中50个集 合，否则，集合
恰有40个元素，所以除外至多有1960个集合，不可能，因此设属于集
，下 面证明它属于给定的1978个集合中任一个。
，，…的任一个集合，设，则与，，，…每对于除了< br>一个都有至少一个元素的交，它们都与不同，那么，就至少要有51个元素，不可能，
因此属于每 个集合。
说明：这种题目最怕把它想难了，想行太难了，就会觉得无从下手，做数学竞赛题就需
要一方面在做题之前选好方向，另一方面就是大胆尝试去做。
7．分析：证明恰有一个公共元也许挺 难。那么证只有两个或零个公共元不可能是否可行呢？
如果具有两个公共元的集合与表示为、那么~有传 递性。是否有用呢？
与
，
证明：设结论不真。则所给的3元子集要么不交，要么恰有 两个公共元，如果子集
恰有两个公共元，则记
则
。设是三个子集。可以证明如果，，于是所有给定的3元子集可以分类，使得同一类中任意两个不同子集都恰有两
个公共元。而不同类 的子集不相交。于是对每个子集类，有三种可能：（1）恰含3个元素
的类。（2）恰含4个元素的类。 （3）至少含5个元素的类。
在（1）下，3元子集类恰由一个3元子集组成。
在（2）下，子集类中至多有4个子集。
----------------------- ----------------------------------精品 文档
------ -------------------------------------------------- -------------

-------------各类专业好文档，值得你下 载，教育，管理，论文，制度，方案手册，应有尽有--------------

考虑（3） 设，，则还有一个，由
，由，，
，，有
。因此对子集类中任意子 集它包含与，
于是类中子集个数比类中元素个数少2，于是，每个类中子集个数不超过元素个数，但是题
中条件子集数大于元素个数，矛盾！
说明：此题为1979年美国竞赛题。题目难度较大，应该说是应用了高等代数中的一些
思想。


------------------------------------ ---------------------精品 文档
------------------- --------------------------------------------------