运动,不是生活的全部,但是生活的最高处
                     运动,不是生活的全部,但是生活的最高处

区空间  校空间  我的主页    照片   好友[文章  收藏   评论   留言     最新阅读     推荐文章 

自行车/6 |  游泳/18 |  奥数教材(转载)/23 |  我的学生/3 |  生活与保健/3 |  个人收藏/4 |  跑步/6 |  力量训练/3 |  奥数竞赛(转载)/3 |  羽毛球/1 | 
本博客空间统计:   6830 篇文章   71 个评论

加为好友  发送信息

博主说明:教师
姓名:蓝忠诚
学校:罗芳小学
空间等级:50 >
现有积分:41798
距离下一等级:1202分
空间排名:教师类 第18

 
最新文章
 
转载:山东情妇馆”真的要更换招牌了?
转载:10 个坏习惯,榨干年轻人
转载:郎平从球员到教练火了40年 命运和.
2020年第30跑
转载:姚明3200米13分16秒让年轻运.
关于香港国安立法决定的9个疑问,都有回应.
 
随机阅读
 
创新作业设计策略
《里程表》第二课时听课
《里程表》第一课时听课
臻美数学——创新作业设计策略
世界上最宝贵的东西
可怕的喷嚏
 
推荐文章
 
参加2017年深圳市“体彩杯”成人游泳锦.
2014年夏游记录
2012-2013年度冬泳记录

5月
13 2020
 

第八讲 容斥原理


   作者:蓝忠诚 发表时间-20 :32:33  阅读( 10 )| 评论( 0 )

第八讲 容斥原理

  在一些计数问题中,经常遇到有关集合元素个数的计算。我们用|A|表示有限集A的元素个数。在并集的讨论中,已经知道,求两个集合并集的元素的个数,不能简单地把两个集合的元素个数相加,而要从两个集合个数之和中减去重复计算的元素个数,即减去交集的元素个数,用式子可表示成

  |A∪B|=|A|+|B|-|A∩B|

  我们称这一公式为包含与排除原理,简称容斥原理。

  包含与排除原理告诉我们,要计算两个集合A、B的并集A∪B的元素的个数,可分以下两步进行:

  第一步 分别计算集合A、B的元素个数,然后加起来,即先求|A|+|B|(意思是把A、B的一切元素都“包含”进来,加在一起);

  第二步 从上面的和中减去交集的元素个数,即减去|A∩B|(意思是“排除”了重复计算的元素个数)。

例1 求不超过20的正整数中是2的数倍或3的倍数的数共有多少个。

分析与解:设I={1,2,3,…,19,20},A={I中2的倍数},B={I中3的倍数}。

  显然,题目要求计算并集|A∪B|的元素个数,即求|A∪B|。

  易知,

  A={2,4,6,…,18,20},

  共有10个元素,即|A|=10,

  B={3,6,9,12,15,18},

  共有6个元素,即|B|=6。

  A∩B={I中既是2的倍数又是3的倍数}

   ={6,12,18}

  共有3个元素,即|A∩B|=3,所以

  |A∪B|=|A|+|B|-|A∩B|

   =10+6-3=13

  答:所求的数共有13个。

  此题可直观地图示如下:

  图8-1中,A表示不超过20的正整数中2的倍数的集合。B表示不超过20的正整数中3的倍数的集合。在不超过20的正整数中既是2的倍数又是3的倍数的数有6,12,18,即A∩B中的数。

例2 某班统计考试成绩,数学得90分上的有25人;语文得90分以上的有21人;两科中至少有一科在90以上有38人。问两科都在90分以上的有多少人?(1985年初一迎春杯数学竞赛试题)

解:设A={数学成绩90分以上的学生),

   B={语文成绩90分以上的学生}。

  那么,集合A∪B表示两科中至少有一科在90分以上的学生,由题意知

  |A|=25,|B|=21,A∪B=38。

  现在要求两科都在90分以上的学生人数,即求|A∩B|。由容斥原理得

  |A∩B|=|A|+|B|-|A∪B|=25+21-38=8

  答:两科都在90分以上的学生有8人。

  在计算面积的问题中,有时也要用到容斥原理。

例3 边长为2的正方形与边长为3的正方形,如图8—2放在桌面上,它们所盖住的面积有多大?

分析与解:如果把两个正方形的面积加起来,得

  22+32=13

  就会发现,多计算了一块阴影部分面积。这块面积是1.52=2.25。应该从上面的和中减去这一部分。因此,两个正方形所盖住的面积应是

  22+32-1.52

  =13-2.25=10.75

  答:两个正方形所盖住的面积是10.75。

例4 有100位旅客,其中有10人既不懂英语又不懂俄语,有75人懂英语,83人懂俄语。问既懂英语又懂俄语的有多少人?(1985年小学迎春杯数学竞赛试题)

分析与解:设A={懂英语的旅客},B={懂俄语的旅客}。那么,英语和俄语这两种语言中至少懂一种的旅客的集合为A∪B,而两种语言都懂的旅客的集合为A∩B。题目要求|A∩B|。

  由题意知,|A|=75,|B|=83,|A∪B|=100-10=90。由容斥原理,得

  |A∩B|=|A|+|B|-|A∪B|

   =75+83-90=68

  答:既懂英语又懂俄语的旅客有68人。

  对于任意三个有限集合A、B、C,我们可以将上面的容斥原理推广得到如下的公式:

  |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|。

  三个集合的容斥原理告诉我们,要计算并集A∪B∪C的元素个数,可以分三步进行:

  第一步 求|A|+|B|+|C|;

  第二步 减去|A∩B|,|A∩C|,|B∩C|;

  第三步 加上|A∩B∩C|。

  结合图8—3还可以作出如下说明。由于A∪B∪C一般可分成如图的七个部分,或者说分成了七个不相交的子集。其中Ⅰ、Ⅱ、Ⅲ部分的元素仅属于某个集合,而Ⅳ、V、Ⅵ部分的元素分别属于某两个集合,第Ⅶ部分则是三个集合的交集由于A∪B∪C的元素分别来自集合A、B、C,因此,先计算|A|+|B|+|C|。在这个和里,Ⅰ、Ⅱ、Ⅲ部分的元素只计算了一次,而Ⅳ、V、Ⅵ部分的元素各计算了两次,第Ⅶ部分(A∩B∩C)的元素计算了三次。在第二步减去|A∩B|,|A∩C|,|B∩C|后得

  |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|。

  这样显然消除了IV、V、VI部分的重复计算,但同时连续三次减去了第Ⅶ部分,于是第Ⅶ部分的元素个数都被减去了,因此必须补上第Ⅶ部分的元素个数,即再加上|A∩B∩C|,综上所述得

  |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|。

例5 某校组织棋类比赛,分成围棋、中国象棋和国际象棋三个组进行。参加围棋比赛的共有42人,参加中国象棋比赛的共有51人,参加国际象棋比赛的共有30人。同时参加了围棋和中国象棋比赛的共有13人,同时参加了围棋和国际象棋比赛的7人,同时参加了中国象棋和国际象棋比赛的11人,其中三种棋赛都参加的3人。问参加棋类比赛的共有多少人?

解法1:设A={参加围棋比赛的人},B={参加中国象棋比赛的人},C={参加国际象棋比赛的人},那么参加棋类比赛的人的集合为A∪B∪C。由题意知:

  |A|=42,|B|=,|C|=30,

  |A∩B|=13,|A∩C|=7,|B∩C|=11,

  |A∩B∩C|=3。

  由容斥原理得

  |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∪C|-|B∩C|+|A∩B∩C|

  =42+51+30-13-7-11+3

  =95(人)

  答:参加棋类比赛的共有95人。

解法2:利用文氏图逐个填写各区域所表示的集合元素的个数,然后求出最后结果。

  设A、B、C分别表示参加围棋、中国象棋和国际象棋比赛的人的集合。其文氏图分割成七个互不相交的区域。区域Ⅶ(即A∩B∩C)表示三种棋赛都参加的数的集合。由题意应填数字3。区域IV表示仅参加围棋和中国象棋两项比赛的人的集合,其人数为13-3=10(人)。区域Ⅵ表示仅参加围棋和国际象棋两项比赛的人的集合,其人数为7-3=4(人)。区域Ⅰ表示只参加围棋一项比赛的人的集合,其人数为42-10-4-3=25(人)。同理可把区域Ⅱ、Ⅲ、V所表示的集合的人数逐个算出,分别填入相应的区域内(图8—4)。由此得出参加棋类比赛的总人数为

  25+30+15+15+10+8+4=3=95

说明:解法2简单直观,不易出错。由于各个区域所表示的集合的元素个数都计算出来了,因此提供了较多的信息,易于回答各种方式的提问。

例6 边长分别为6,5,2的三个正方形,如图8—5所示放在桌面上。问它们盖住的面积是多大?

分析与解:这个问题可用容斥原理来解。设R表示正方形区域ABCD,R1表示正方形区域A1B1C1D1,R2表示正方形区域A2B2C2D2。那么R∩R1表示正方形区域BOD1M,R∩R2表示矩形区域A2FND2,R1∩R2表示矩形区域A2B2GE,R∩R1∩R2表示正方形区域A2FOE个正方形所盖住的部分为R∪R1∪R2。如果用|R|表示区域R的面积,那么根据容斥原理可得

  |R∪R1∪R2|=|R|+|R1|+|R2|-|R∩Rl|

  -|R∩R2|-|R1∩R2|+|R∩R1∩R2|

  =62+52+22-(32+2×1+1×2)+12

  =53

  答:三个正方形所盖住的面积为53。

例7 某班学生手中分别拿有红、黄、蓝三种颜色的球。已知手中有红球的共有34人,手中有黄球的共有26人,手中有蓝球的共有18人。其中手中有红、黄、蓝三种球的有6人。而手中只有红、黄两种球的有9人,手中只有黄、蓝两种球的有4人,手中只有红、蓝两球的有3人,那么这个班共有多少人?(1986年初一迎春杯数学竞赛试题)

分析与解:此题用填写文氏图各区域元素个数的方法来解较为简便,设A、B、C分别表示手中有红球、黄球、蓝球的人的集合。由题意可逐一填出各区域元素的个数(如图)。所以全班共有

  16+7+5+9+4+3+6

  =50(人)

  答:这个班共有50人。

  这个题目也可以列式计算如下:

  (34+26+18)-(9+4+3)-2×6=50(人)

例8 求1到200的自然数中不能被2、3、5中任何一个数整除的数有多少?

解: 设A={1到200中间能被2整除的数},

  B={1到200中间能被3整除的数},

  C={1到200中间能被5整除的数}。

  那么,A∩B={1到200中间能被2×3整除的数},

  A∩C={1到200中间能被2×5整除的数},

  B∩C={1到200中间能被3×5整除的数},

  A∩B∩C={1到200中间能被2×3×5整除的数}。

  设[x]表示小于等于x的最大整数,那么

  |A|=[200/2]=100,|B|=[200/3]=66,

  |C|=[200/5]=40,|A∩B|=[200/6]=33,

  |A∩C|=[200/10]=20,|B∩C|=[200/15]=13,

  |A∩B∩C|=[200/30]=6。

  根据容斥原理,1到200的自然数中至少能被2,3,5中一个数整除的数共有

  |A∪B∪C|=|A|+|B|+|C|-|A∩B|

   =|A∩C|-|B∩C|+|A∩B∩C|

   =100+66+40-33-20-13+6=146(个)

  所以1到200的自然数中不能被2,3,5中任何一个数整除的数共有

  200-146=54(个)



上一篇文章:2020年第16跑    下一篇文章:习题八



个人空间评论从2017年1月起采用实名制: