容斥原理方阵问题讲义,公务员考试,数量关系.doc

容斥原理在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。两个集合的容斥关系公式：AB = A+B - AB (:重合的部分） 三个集合的容斥关系公式：ABC = A+B+C - AB - BC - CA +ABC 2、文氏图分块标记如右图图：1245构成A，2356构成B，4567构成C 3、等式右边（）里指的是下图的1+2+3+4+5+6六部分： 那么ABC还缺部分7。 4、等式右边【】号里+C（4+5+6+7）后，相当于ABC多加了4+5+6三部分， 减去BC（即5+6两部分）后，还多加了部分4。 5、等式右边里减去CA （即4+5两部分）后，ABC又多减了部分5， 则加上ABC（即5）刚好是ABC。 容斥原理1 两集合标准型如果被计数的事物有A、B两类，那么，A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数既是A类又是B类的元素个数。(AB = A+B - AB ) 总数=两集合数之和+两集合之外数两集合公共数例1一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？ 分析依题意，被计数的事物有语、数得满分两类，“数学得满分”称为“A类元素”，“语文得满分”称为“B类元素”，“语、数都是满分”称为“既是A类又是B类的元素”，“至少有一门得满分的同学”称为“A类和B类元素个数”的总和。 答案15+12-4=23 试一试电视台向100人调查前一天收看电视的情况，有62人看过2频道，34人看过8频道，其中11人两个频道都看过。两个频道都没看过的有多少人？ 100-(62+34-11)=15 容斥原理2 三集合标准型如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数既是A类又是B类的元素个数既是A类又是C类的元素个数既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。 集合A、B、C，满足标准型公式：=总数-三者都不满足的个数总数=各集合数之和两集合数之和三集合公共数三集合之外数三集合标准型公式适用于题目中各类条件都明确给出的情况。另外，可使用尾数法，判断个位数的相加减快速确定正确答案。例2某校六（1）班有学生45人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？ 分析：参加足球队的人数25人为A类元素，参加排球队人数22人为B类元素，参加游泳队的人数24人为C类元素，既是A类又是B类的为足球排球都参加的12人，既是B类又C类的为足球游泳都参加的9人，既是C类又是A类的为排球游泳都参加的8人，三项都参加的是A类B类C类的总和设为X。注意：这个题说的每人都参加了体育训练队，所以这个班的总人数既为A类B类和C类的总和。 答案：25+22+24-12-9-8+X=45 解得X=3 例3在1到1000的自然数中，能被3或5整除的数共有多少个？不能被3或5整除的数共有多少个？ 分析：显然，这是一个重复计数问题（当然，如果不怕麻烦你可以分别去数3的倍数，5的倍数）。我们可以把“能被3或5整除的数”分别看成A类元素和B类元素，能“同时被3或5整除的数（15的倍数）”就是被重复计算的数，即“既是A类又是B类的元素”。求的是“A类或B类元素个数”。现在我们还不能直接计算，必须先求出所需条件。10003=3331，能被3整除的数有333个（想一想，这是为什么？）同理，可以求出其他的条件。 例4分母是1001的最简分数一共有多少个？ 分析：这一题实际上就是找分子中不能与1001进行约分的数。由于1001=71113，所以就是找不能被7，11，13整除的数。 解答：11001中,有7的倍数1001/7 = 143 (个)；有11的倍数1001/11 = 91 (个),有13的倍数1001/13 = 77 (个)；有7´11=77的倍数1001/77 = 13 (个),有7´13=91的倍数1001/91 = 11 (个),有11´13=143的倍数1001/43 = 7 (个).有1001的倍数1个. 由容斥原理知:在11001中,能被7或11或13整除的数有(143+91+7)-(13+11+7)+1=281(个),从而不能被7、11或13整除的数有1001-281=720(个).也就是说,分母为1001的最简分数有720个. 例5某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后，有4名学生在这三个项目上都没有达到优秀，其余每人至少有一项达到了优秀，达到了优秀的这部分学生情况如下表： 短跑游泳投掷短跑、游泳短跑、投掷游泳、投掷短跑、游泳、投掷1 71 81 56652求这个班的学生共有多少人？ 分析：这个班的学生数，应包括达到优秀和没有达到优秀的。 试一试：一个班有42人，参加合唱队的有30人，参加美术组的有25人，有5人什么都没有参加，求两种都参加的有多少人？ 原理一：给定两个集合A和B，要计算AB中元素的个数，可以分成两步进行：第一步：先求出A+B(或者说把A，B的一切元素都“包含”进来，加在一起);第二步：减去AB(即“排除”加了两次的元素)总结为公式：|AB|=A+B-AB原理二：给定三个集合A，B，C。要计算ABC中元素的个数，可以分三步进行：第一步：先求A+B+C;第二步：减去AB，BC，CA;第三步：再加上ABC。即有以下公式：ABC=A+B+C-AB-BC- |CA|+|ABC容斥原理3 三集合复合型三集合容斥问题中，有些条件未知时，就不能直接使用标准型公式，而是运用整体重复型公式同样可以解答。特别当题目中说明分别满足一种、两种、三种条件的个数时，使用整体重复型公式。并且，三集合整体重复型公式是现在国家公务员考试考查三集合容斥问题的重点。另外，仍可利用尾数法可以快速求解。三集合A、B、C，用W代表，满足一个条件的数量为x（仅单色区域），满足两个条件的数量为y（双色区域），满足三个条件的数量为z（三色区域），则有： W=x+y+z A+B+C=x+2y+3z【例题3】（国家-行测-2010-50）某高校对一些学生进行问卷调查。在接受调查的学生中，准备参加注册会计师考试的有63人，准备参加英语六级考试的有89人，准备参加计算机考试的有47人，三种考试都准备参加的有24人，准备选择两种考试参加的有46人，不参加其中任何一种考试的有15人。问接受调查的学生共有多少人？（ ） A. 120 B. 144 C. 177 D.192【答案】A。根据题意，分别已知两种条件、三种条件都满足的个数，使用三集合整体重复型公式：W=x+46+24 63+89+47=x+2*46+3*24 根据尾数法，解得x尾数是5，W尾数是5。因此，学生总数=W+15，尾数为0，选A。【例题4】（国家-行测-2011-74）某市对52种建筑防水卷材产品进行质量抽检，其中有8种产品的低温柔度不合格，10种产品的可溶物含量不达标，9种产品的接缝剪切性能不合格，同时两项不合格的有7种，有1种产品这三项都不合格。则三项全部合格的建筑防水卷材产品有多少种？（ ）A. 37 B. 36 C. 35 D. 34【答案】D。根据题意，分别已知满足一种条件、两种条件的个数，使用三集合整体重复型公式：W=x+7+1 8+9+10=x+2*7+3*1 根据尾数法，解得x尾数为0，W尾数为8。 因此，全合格的产品数=总数-W=52-W，尾数为4，选D。 三集合标准型公式和整体重复型公式的适用情况是不同的：标准型公式适用于各项条件都明确给出的情况，而整体重复型公式适用于分别给出满足一种、两种、三种条件的个数，因为这三者之间没有任何包含关系。区分好两种情形，特别是整体重复型公式，三集合容斥问题就迎刃而解了。容斥问题在数字整除中的运用例1 求不超过20的正整数中是2的倍数或3的倍数的数共有多少个。分析：设A=20以内2的倍数，B=20以内3的倍数，显然，要求计算2或3的倍数个数，即求AB。解1：A=2，4，6，20，共有10个元素，即|A|=10B=3，6，9，18，共有6个元素，即|B|=6AB=既是2的倍数又是3的倍数=6，12，18，共有3个元素，即|AB|=3所以AB=A+B-AB=10+6-3=13，即AB中共有13个元素。例2求在不超过100的自然数中，不是5的倍数，也不是7的倍数有多少个?分析：这个问题与前几个例题看似不相同，不能直接运用容斥原理，要计算的是“既不是5的倍数，也不是7的倍数的数的个数。”但是，只要同学们仔细分析题意，这只需先算出“100以内的5的倍数或7的倍数的数的个数。”再从100中减去就行了。解：设A=100以内的5的倍数B=100以内的7的倍数AB=100以内的35的倍数AB=100以内的5的倍数或7的倍数则有A=20，B=14，AB=2由容斥原理一有：AB=A+B-AB=20+14-2=32因此，不是5的倍数，也不是7的倍数的数的个数是：100-32=68(个)点评：从以上的解答可体会出一种重要的解题思想：有些问题表面上看好象很不一样，但经过细心的推敲就会发现它们之间有着紧密的联系，应当善于将一个问题转化为另一个问题。方阵问题基础学习 一. 解答题 2、实心方阵例1：30人一排的方阵，求最外层有多少人？【答案】116人。【解题关键点】利用公式四周人(或物)数=每边人(或物)数-14，（30-1）4=116 3、实心方阵例2：20人一排的方阵共有多少人？【答案】400（人）。【解题关键点】利用公式：实方阵总人(或物)数=每边人(或物)数每边人(或物)数，2020=400（人）。 5、空心方阵例1：小华用围棋摆了一个六层的空心方阵,共用264颗棋子,问最里层有多少个棋子？( )A 36 B 24 C 30 D 22【答案】B【解题关键点】法一：对于空心方阵，最外层每边数=总数4层数+层数最外层每边数=（26446）+6=17人；共六层，最外一层与最里一层相差5层。每层每边数差两个，所以最里层每边数=17-52=7个那么最里层个数是47-4=24个。法二：方阵每层相差8个。那么从里向外数，第二层比第一层多8个，第三比第一层多16个，第四层比第一层多24个，第五层比第一层多32个，第六层比第一层多40个；那么最里一层就是（264-8-16-24-32-40）6=24个【结束】 6、空心方阵例2：一个两层空心方阵最外层有16人，一共多少人？（）A.16 B.24 C.10 D.22【答案】B【解题关键点】最外层16人-四个角4人=12人 124=3，即每个边3人 内层每个边应该比外层少2人以占角拐弯，故每个边仅1人，加上4个角，内层共8人 综上，内外两层共24人总而言之，就是外层每排5人，内层每排3人，最中间空出一个人位置的两层空心方阵。7、方阵综合例1：方阵外一层总人数比内一层的总人数多8每边人数与该层人数关系是：最外层总人数（边人数1）4 方阵总人数最外层每边人数的平方 空心方阵的总人(或物)数=（最外层每边人(或物)数空心方阵的层数）空心方阵的层数4 去掉一行、一列的总人数=去掉的每边人数2-1 【例1】某校的学生刚好排成一个方阵，最外层的人数是96人，问这个学校共有学生？【答案】625【解题关键点】解答：最外层每边的人数是964+125，刚共有学生2525=6258、方阵综合例2：五年级学生分成两队参加学校广播操比赛，他们排成甲乙两个方阵，其中甲方阵每边的人数等于8，如果两队合并，可以另排成一个空心的丙方阵，丙方阵每边的人数比乙方阵每边的人数多4人，甲方阵的人数正好填满丙方阵的空心。五年级参加广播操比赛的一共有多少人?（）A 160 B 204 C 100 D 260【答案】D【解题关键点】设乙最外边每人数为Y，则丙为Y+4.88+YY+88=(Y+4)(Y+4)， 求出Y=14,则共有人数：1414+88260。9、方阵综合例3：明明用围棋子摆成一个三层空心方阵，如果最外层每边有围棋子15个，明明摆这个方阵最里层一周共有多少棋子？摆这个三层空心方阵共用了多少个棋子? 【答案】56个，144个。【解题关键点】最外层有(15-1)4=56个。则里二层为56-82=40，应用公式，用棋子（153）34144。 10、方阵综合例4：学校运动会上，晨光小学组成一个大型方阵队，方阵队最外层每边25人，共8层；中间部分是15名同学组成的运动会会徽，这个方阵共有多少名同学？【解题关键点】空心方阵问题总数的公式是：总数=(最外层每边数-层数)*层数*4 11、方阵综合例5：108人排成空心方阵，如果最外层每边12人，那么共有几层？【答案】3【解题关键点】可以把相邻两层每边人数想成是一个等差数列，公差是2（方阵问题中有这样一个知识点，就是相邻两边每边人数相差2）。通过“1212-108=36”计算我们知道了此方阵是中