|
阅读：1232回复：0
容斥原理深度分析
容斥原理类型的题目的难点就在于在运算的时候，计数的重复，遗漏问题。容斥原理的基本思想：先不考虑重叠的情况，把包含于某一内容中的所有对象的数目计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结既无重复也无遗漏。
这种类型是目前国家、各地区公务员考试的“常客”题型，对于大部分应试者来说，还是比较头痛的一种类型。因此大家需要认真去对待掌握。特别是对于基础的图形模型要了然于胸。容斥原理类型我们一般通过两种方法去解决，公式法和韦恩图解法。图解法是通过画图来求解，相信大家都能做到，这里介绍的一下公式法。 核心公式： (1) 两个集合的容斥关系公式： A＋B=A∪B＋A∩B (2) 三个集合的容斥关系公式： A＋B＋C=A∪B∪C＋A∩B＋B∩C＋C∩A－A∩B∩C 另外还将下面另外一种方程式的公式，首先请参考下图，通过一个例题来理解。 (1) 两个集合的容斥关系（二元）  2012-9-11 18:15 上传下载附件 (31.43 KB) 这个原图的核心部分再与中间的2个圆构成的内容，我们知道2圆相加必然重复算了一次中间部分T：x+y＝(A+T)+(B+T) 要计算实际的2圆元素数量 即必须把重复的去掉为x+y-T。如果要求A或者B是多少。我们只需把对应x或y去掉公共部分T就可得到。如果要求T是多少。我们只需把x+y－AB元素的总和即得到重复的部分T。另外，两个圆x和y构建的不一定是所有元素。这个时侯我们一定要想办法把这些不是圆内的元素去除掉，否则应用容斥原理就会有麻烦。反过来我们也可以利用这个求所有不参与圆的元素之和。 (2) 三个集合的容斥关系（三元）[font=;quot]  2012-9-11 18:17 上传下载附件 (28.93 KB) 例题：假设有100人参加了三个兴趣小组。其中参加数学兴趣小组的有55人，参加语文兴趣小组的有65人，参加英语兴趣小组的有70人，同时参加语文和数学兴趣小组的人数是31人，同时参加数学和英语兴趣小组的人数是40人，同时参加语文和英语兴趣小组的有25人，则三个兴趣小组都参加的人数是多少人？ （1） A+B+T=至少参与一项的总人数（无重叠） （2） A＋2B＋3T＝至少参与一项的总人数（含重叠部分） （3） B＋3T＝至少参与两项的总人数（含重叠） （4） T三项都参与的人数。 这里介绍一下A、B、T分别是什么 A＝x＋y＋z；表示只参加一个兴趣小组的人数，在图中反应的区域就是每个圆圈互不重叠的部分。 B＝a＋b＋c；表示仅参加了两个兴趣兴趣小组的人数，是图中两两相交的部分总和（不含中间的T区域） T＝全部都参加的人数。也就是图形当中最中间的部分T。 例题通过公式有如下解法： （1） A＋B＋T＝100； （2） A＋2B＋3T＝55＋65＋70＝190 （3） B＋3T＝31＋40＋25＝96 实际上我们要求的是T， （1）＋（3）－（2）＝T。 即得到答案T＝100＋96－190＝6 1、二元容斥应用 二元容斥主要涉及到的集合只有2个，在分析题目的时侯千万要弄清楚谁是集合对象，一般就要从提问入手，看提问中涉及到的关键词是什么。另外不要被其他成份的对象干扰。一定选准了集合对象就要瞄准这个方向走下去。 例题90：某代表团有756名成员，现要对A、B两议案分别分进行表决，且他们只能投赞成票或反对票。已知赞成A议案的有476人，赞成B议案的有294人，对A、B两议案都反对的有169人，则赞成A议案且反对B议案的有（ ） 【07浙江】 A.293 B.182 C.183 D.462 【天字1号解析】参考答案A。 我们先对提问分析，提问的含义实则是“只”反对B议案的人数是多少。那么我们可以通过反对议案这个角度构建容斥。 反对B的人数是756-294=462人，两者都反对的是169人。那么只反对B的就是462-169=293人。 例题91：旅行社对120人的调查显示，喜欢爬山的与不喜欢爬山的人数比为5：3；喜欢游泳的与不喜欢游泳的人数比为7：5；两种活动都喜欢的有43人。对这两种活动都不喜欢的人数是（ ）。 【09广东】 A．18 B．27 C．28 D．32 【天字1号解析】参考答案A。 至少喜欢一种的人数=喜欢游泳的+喜欢爬山的-重复部分既喜欢游泳又喜欢爬山的。因此有120×7/12+120×5/8-43=102. 两者都不喜欢的即等于总人数去掉至少喜欢一项的人数：120-102=18人。 如果你注意观察选项你也会发现18+27=45, 18+32=50 分别是不喜欢爬山和不喜欢游泳的人数。也能确定A选项。 例题92：某单位派60名运动员参加运动会开幕式，他们着装白色或黑色上衣，黑色或蓝色裤子。其中有12人穿白上衣蓝裤子，有34人穿黑裤子，29人穿黑上衣，那么穿黑上衣黑裤子的有多少人？ 【10黑龙江】 Ａ.12 Ｂ.14 Ｃ.15 Ｄ.29 【天字1号解析】参考答案C。 注意建立容斥关系，要求的是黑色上衣和黑色裤子的相交部分。已知条件告诉我们黑色上衣，黑色裤子各是多少。那么我们只需要知道穿黑色上衣或黑色裤子至少穿一个的人数是多少。 即从总人数中去掉不涉及黑色的人数60－12＝48. 剩下的就是2元容斥。即答案是（x+y）-参与的总人数=34+29-48＝15人。 例题93：某公司100名员工对甲、乙两名经理进行满意度评议，对甲满意的人数占全体参加评议的3/5，对乙满意的人数比甲的人数多6人，对甲乙都不满意的占满意人数的1/3多2人，则对甲乙都满意的人数是（ ） 【10广东】 A. 36 B. 26 C. 48 D. 42 【天字1号解析】参考答案D。 要求都满意的人数。我们可以建立等式参与人数＝参与A+参与B－参与AB。则有(100×3/5×2)+6-100=26,这是理想状态下没有都不满意的时侯的人数事实上我们少算了都不满意的人数，那么这个26+2＝28 就是都满意和都不满意差值占都满意的2/3 即答案是28×3/2=42. 也可直接列方程，令都满意的为a，则都不满意的为a/3 +2. 即可以建立方程 100-(a/3+2)=100×3/5×2+6-a 即也可解得a=42. 2、三元容斥公式应用实例 三元容斥涉及的对象比较多。我们通常建议考生根据不同提问情况区别对待。本小节先对一般情况的题目做一些分析。 例94：如图所示，X、Y、Z分别是面积为64、180、160的三个不同形状的纸片，覆盖住桌面的总面积是290，其中X与Y、Y与Z、Z与X重叠部分的面积依次是24、70、36，那么阴影部分的面积是： 【09国考】 A．15 B．16 C．14 D．18 【天字1号解析】参考答案为B。 这就是典型的容斥原理图形。求解的阴影面积即为三个集合都相交的区域。根据公式（1） A＋B＋T＝290 （2） A＋2B＋3T＝64＋180＋160＝404 （3） B＋3T＝24＋70＋36＝130 则组合这些表达式就会得到：（1）＋（3）－（2）＝T＝290＋130－404＝16 故答案是16 例95：某市对52种建筑防水卷材产品质量抽检，其中8种产品的低温度不合格，10种产品的可溶物含量不达标，9种产品的接缝剪切性能不合格，同时两项不合格的有7种，有1种产品这三项都不合格，则三项全部合格的建筑防水卷材产品有多少种？【11国考】 A.37 B.36 C.35 D.34 【天字1号解析】参考答案D。 这个题目很有意思，他把我们传统做容斥原理的习惯思维颠覆了一下。通常我们都是根据已知条件 多少合格的人后求多少不合格的。那么这里我们也可以把公式所代表的含义颠倒过来用，A表示至少有一项不合格，B表示至少有2项不合格，T表示三项都不合格。根据公式: (1) A+2B+3T=8+10+9=27; (2) B=7; (3) T＝1. 可得到A+B+T=27-B-2T=27-7-2=18. 因此合格的有52－18＝34. 例96：甲、乙、丙三个人共解出20道数学题，每人都解出了其中的12道题，每道题都有人解出。只有一人解出的题叫做难题，只有两人解出的题叫做中等题，三人解出的题叫做容易题，则难题比容易题多（ ）题? A．6 B．5 C．4 D．3 【天字1号解析】参考答案C。 稍微整理一下题目，难题也就是三个圆圈中不参与重叠的部分，也就是公式当中的A所表示的；中等题目是只重叠过1次，也就是公式当中的B，简单题则是公式当中的T。 （1）A＋B＋T＝20 （2）A＋2B＋3T＝12×3＝36 要求解的是A－T＝？；通过上述两个表达式变型可得到：(1)×2-(2)=A-T=20×2-36=4. 如果不知道怎么变型求解。可以利用我们上面讲的代入消去法去做，令B=0, 则可把三元变为2元。即 T=8，A=12. 即A-T=4. 3、“只”值容斥解题思路 “只”值容斥类型。其实是从提问方式角度划分出来的。有些题目会问只喜欢或只参加某种集合的人数。面对这种带“只”的题目，通常我们是采用逆向思考方式来化三元变为二元容斥。比如说，告诉你总人数，要求只喜欢A的人数。我们可以逆向思维。总人数－喜欢其他的人数和，剩下的就是只喜欢A的人数了。这就转化为只看其他2元的求和问题了。 例题99：对某单位的100名员工进行调查，结果发现他们喜欢看球赛、电影和戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，则只喜欢看电影的有（ ）。 【07国考】 A．22人 B．28人 C．30人 D．36人 【天字1号解析】参考答案A。 可以画图和列举公式来做的 不过耗时。这个“只喜欢”的问法 往往我们可以逆向思维 （1）只喜欢看电影的人数＝总人数－喜欢看戏剧和球赛的总人数 （2）喜欢看戏剧＋喜欢看球赛的＝58＋38＝96人 这部分即喜欢看戏剧又喜欢看球赛的人数是18人，所以 喜欢看戏剧和球赛的人数＝96－18＝78人，则答案是：只喜欢看电影的人数＝100－78＝22人。 可能很多人还是不能理解这里面的道理，没关系，我们可以再次看上面的三元容斥图。假设红色圆圈“x”就是我们要求的部分，他相当于整体去掉黑色圆+蓝色圆之和（无重复），这就是我们做此题的一个逆向思路。 从这个题目上我们应该有一个启发，很多东西不是按步就班的考察你的公式，而是考察你的能力，例如此题的逆向思维能力！ |
|
|
2012-9-11 18:19 上传