当前位置:首页 >> 学科竞赛 >>

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.对每个 个的交非合。

使得在 n 元集合中,可以取出 k 个子集,其中任意两

4.能否把

分成两个积相等的不交集合。

课后练习答案
1. 我们可以发现对每个数 , 它出现在 个子集之中, 因此所有子集中的 的和为 ,

那么全部元素在全部子集之中的和为



2. 利用二进制来考虑此题, 小明的前 9 包分别有钱 1 分 (2) 10 分 , (2) 100 分 , (2) , 1000 分 (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、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 的质数都不能 2 整除 a,那么 a 是质数。因为 120<121=11 ,√120<11,所以不超过 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(S2)+card(S3)+card(S4)-card(S1∩S2)- card(S1∩S3)-card(S1∩S4)-card(S2∩S3)-card(S2∩S4)-card(S3∩S4)+card(S1∩S2∩S3) +card(S1∩S2∩S4)+card(S1∩S3∩S4)+card(S2∩S3∩S4)-card(S1∩S2∩S3∩S4)=(60+40 +24+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 个集合中任意一个集合 此,存在 集合,而集合 合 , ? ,它和其它 1977 个集合都相交,因 中每个元素至多属于 49 个

,使得它至少属于其中 50 个集合,否则,集合 恰有 40 个元素,所以除

外至多有 1960 个集合,不可能,因此设 属于集

,下面证明它属于给定的 1978 个集合中任一个。 , ,? 的任一个集合 ,设 ,则 与 , , ,? 每

对于除了

一个都有至少一个元素的交,它们都与 不同,那么,

就至少要有 51 个元素,不可能,

因此 属于每个集合。 说明:这种题目最怕把它想难了,想行太难了,就会觉得无从下手,做数学竞赛题就需 要一方面在做题之前选好方向,另一方面就是大胆尝试去做。 7. 分析: 证明恰有一个公共元也许挺难。 那么证只有两个或零个公共元不可能是否可行呢? 如果具有两个公共元的集合 与 表示为 、那么~有传递性。是否有用呢? 与 ,

证明:设结论不真。则所给的 3 元子集要么不交,要么恰有两个公共元,如果子集 恰有两个公共元,则记 则 。设 是三个子集。可以证明如果 ,

,于是所有给定的 3 元子集可以分类,使得同一类中任意两个不同子集都恰有两

个公共元。而不同类的子集不相交。于是对每个子集类,有三种可能:(1)恰含 3 个元素

的类。(2)恰含 4 个元素的类。(3)至少含 5 个元素的类。 在(1)下,3 元子集类恰由一个 3 元子集组成。 在(2)下,子集类中至多有 4 个子集。 考虑(3) 设 , ,则还有一个 ,由 ,由 , , , ,有

。因此对子集类中任意子集

它包含 与 ,

于是类中子集个数比类中元素个数少 2,于是,每个类中子集个数不超过元素个数,但是题 中条件子集数大于元素个数,矛盾! 说明:此题为 1979 年美国竞赛题。题目难度较大,应该说是应用了高等代数中的一些 思想。


相关文章:
2013高中数学奥数培训资料之容斥原理
兰州成功私立中学高中奥数辅导资料 (内部资料) §24 容斥原理相对补集:称属于 A 而不属于 B 的全体元素,组成的集合为 B 对 A 的相对补集或差集,记作 A-B...
2013高中数学奥数培训资料之组合数学选讲
2013高中数学奥数培训资料之组合数学选讲_数学_高中教育_教育专区。2013年最新高中...1 个;依次类推,则由容斥原理,X 的覆盖共有 ? (22 n ?1 ? 1) ? ? ...
2013高中数学奥数培训资料之数列
2013高中数学奥数培训资料之数列_学科竞赛_高中教育_教育专区。2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,报送大学不再是幻想 ...
2013高中数学奥数培训资料之集 合
2013高中数学奥数培训资料之集 合_学科竞赛_高中教育_教育专区。2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,保送大学不再是幻想兰州...
2013高中数学奥数培训资料之塞瓦定理
兰州成功私立中学高中奥数辅导资料 (内部资料)平面几何的几个重要定理―――塞瓦定理 ___江西省上犹中学 塞瓦定理:设 P 、 Q 、 R 分别是 ? ABC 的 BC 、...
2013高中数学奥数培训资料之托勒密定理
2013高中数学奥数培训资料之托勒密定理_学科竞赛_高中教育_教育专区。2013年最新高中奥数培训教材兰州成功私立中学高中奥数辅导资料 (内部资料)平面几何的几个重要定理-...
2013高中数学奥数培训资料之递推数列
2013高中数学奥数培训资料之递推数列_学科竞赛_高中教育_教育专区。2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,报送大学不再是幻想兰州...
2013高中数学奥数培训资料之二次函数(2)
2013高中数学奥数培训资料之二次函数(2)_数学_高中教育_教育专区。2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,保送大学不再是幻想兰州...
2013高中数学奥数培训资料之数学归纳法
2013高中数学奥数培训资料之数学归纳法 2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,报送大学不再是幻想2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,...
2013高中数学奥数培训资料之二项式定理与多项式
2013高中数学奥数培训资料之二项式定理与多项式_学科竞赛_高中教育_教育专区。2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,保送大学不再是幻想兰州...
更多相关标签:
小学奥数容斥原理 | 容斥原理奥数 | 容斥原理例题精讲奥数 | 小学奥数容斥原理教案 | 五年级奥数容斥原理 | 小学奥数容斥原理公式 | 小学奥数容斥原理视频 | 四年级奥数容斥原理 |