haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

第十一讲:容斥原理

发布时间:2013-12-31 16:56:04  

巨人学校 五年级尖子仁华预备班 第十一讲 容斥原理

第十一讲 容斥原理

『方法总结』:

一、二元容斥原理:|A?B|?|A|?|B|?|A?B|。

二、三元容斥原理:|A?B?C|?|A|?|B|?|C|?|A?B|?|A?C|?|B?C|?|A?B?C|

三、学会画出图形来表示两个或者三个对象之间的关系,利用田字格方块图来表示两个对象

的容斥原理,掌握对应数在图形中的特定位置,利用三圆环交叉画来理解三个对象的容斥原理。

例题:

1、六一班有学生46人,其中会骑自行车的17人,会游泳的14人,既会骑车又会游泳的4人,问两样都不会的有 人.

[分析与解答]

所求人数=全班人数-(会骑车人数+会游泳人数-既会骑车又会游泳人数)=46-(17+14-4)=19(人)

2、在1至10000中不能被5或7整除的数共有 个.

[分析与解答]

在1到10000中,能被5整除的有??10000??2000(个),能被7整除的有??5?

?10000??10000?(个),能被35整除的有?1428?285(个).因此能被5或7整除的共有????73?7????

2000+1428-285=3143(个).

从而不能被5或7整除的有10000-3143=6857(个).

3、在1至10000之间既不是完全平方数,也不是完全立方数的整数有 个.

[分析与解答

]

巨人学校 五年级尖子仁华预备班 第十一讲 容斥原理

1~10000中完全平方数有100个(因为100=10000),完全立方数有21个(因为21<10000<22),完全六次方数有4个(因为4<10000<5).

故1~10000中是完全平方数或完全立方数的数共有

100+21-4=117(个);

从而既不是完全平方数,又不是完全立方数的数有

10000-117=9883(个).

4、某班共有30名男生,其中20人参加足球队,12人参加蓝球队,10人参加排球队.已知没有一个人同时参加3个队,且每人至少参加一个队,有6人既参加足球队又参加蓝球队,有2人既参加蓝球队又参加排球队,那么既参加足球队又参加排球队的有 人.

[分析与解答]

如图所示,设既参加是球队又参加排球队的人数为x,则依容斥原理,有20+12+10-6-2-x=30,解得x=4.

5、分母是1001的最简真分数有 个.

[分析与解答]

1~1001中,有7的倍数?排球队 10 足球队 6 蓝球队 12 20 33662?1001??1001?(个);有11的倍数?143??11??91(个),有13的倍7????

?1001?数??77(个);有7?11=77的倍数??13(个),有7?13=91的倍数???13??77??1001?

?1001??1001?(个),有11?13=143的倍数?11?91??143??7(个).有1001的倍数1个. ????

由容斥原理知:在1~1001中,能被7或11或13整除的数有(43+91+7)-(13+11+7)+1=281(个),从而不能被7、11或13整除的数有1001-281=720(个).也就是说,分母为1001的最简分数有720个.

巨人学校 五年级尖子仁华预备班 第十一讲 容斥原理

6、在100个学生中,音乐爱好者有56人,体育爱好者有75人,那么既爱好音乐,又爱好体育的人最少有 人,最多有 人.

[分析与解答]

如图,当100人都是或者音乐爱好者,或者体育爱好者时,这两者都爱好的人数为最小值即56+75-100=31(个).

当所有的音乐爱好者都是音乐爱好者时,这两者都爱好的人数最大可为56人.

7、某进修班有50人,开甲、乙、丙三门进修课、选修甲这门课的有38人,选修乙这门课有的35人,选修丙这门课的有31人,兼选甲、乙两门课的有29人,兼选甲、丙两门课的有28人,兼选乙、丙两门课的有26人,甲、乙、丙三科均选的有24人.问三科均未选的人数?

[分析与解答]

如图,选甲乙而不选丙的有a=29-24=5(人),选甲丙而不选乙的b=28-

24=4(人),选乙丙而不选甲的有c=26-24=2(人), 仅选了丁的人有d=35-24-a-c=4(人),仅选了丙的人有e=31-24-b-c=1(人),故少选了一科的人数是:甲+d+c+e=45(人),故三门均未选的人数为50-45=5(人).

丙 甲 a e d 乙 音乐 爱好者 体育 8、求小于1001且与1001互质的所有自然数的和.

[分析与解答]

由第5题的结论知分母是1001的最简分数的个数是720.又真分数a和真分数1001

1001?a (a与1001互质)是成对出现的,故上述720个真分数可以分成360对,每一对=数1001

之和为1,故上述720个分母是1001的真分数之和为360.

所以所有小于1001且与1001互质的数之和为360?1001=360360.

巨人学校 五年级尖子仁华预备班 第十一讲 容斥原理

9、如图所示,A、B、C分别代表面积为8、9、11的三张不同形状的纸片,它们重叠放在一起盖住的面积是18,且A与B,B与C,C与A

C

三个图形公共部分(阴影部分)的面积. [分析与解答]

设阴影部分的面积是x,由容斥原理知

28-(5+3+4)+x=18,

故x=2.

10、分母是385的最简真分数有多少个,并求这些真分数的和.

[分析与解答]

因为385=5?7?11,故在1~385这385个自然数中,5的倍数有

?385??385??385?(个),7的倍数有(个),11的倍数有?76?55?35(个), ??????575??????

5?7=35的倍数有??385??385?(个),5?11=55的倍数有?11?7(个),7?11=77的倍数有????35??55?

?385??77?=5(个),385的倍数有1个. ??

由容斥原理知,在1~385中能被5、7或11整除的数有77+55+35-(11+7+5)+1=145(个),而5、7、11互质的数有385-145=240(个).即分母为385的真分数有240(个).

如果有一个真分数为a385?a,则必还有另一个真分数,即以385为分母的最简真385385

分数是成对出现的,而每一对之和恰为1.故以385为分母的240最简分数可以分成120时,它们的和为1?120=120.

11、64人订A、B、C三种杂志.订A种杂志的28人,订B种杂志的有41人,订C种杂志的有20人, 订A、B两种杂志的有10人,订B、C两种杂志的有12人,订A、C两种杂志的有12人,问三种杂志都订的有多少人?

[分析与解答]

设三种杂志均订的人数为x,则有28+41+20-10-12-12+x=64,解得x=9,即三种杂志都订的有9人.

巨人学校 五年级尖子仁华预备班 第十一讲 容斥原理

练习题 B A 1、求从1到1994中不能被5整除,也不能被6或7整除的自然数的个数.

[分析与解答]

在1~1994中,能被5整除的个数为??1994??1994?;能被6整除的个数为?398?332;能???56????

被7整除的个数为??1994??1994?;能被5?6=30整除的个数为?284?66;能被5?7=35整????7??30?

除的数为??1994??1994?;能被6?7=42整除的个数为?56??42??47;能被5?6?7=210整除的个35????

数为??1994??9. ??210?

根据容斥原理,1~1994中或能被5,或能被6,或能被7整除的数的个数为:(398+332+284)-(66+54+47)+9=854,从而不能被5整除,也不能被6或7整除的自然数的个数为1994-854=1140(个).

2、夏日的一天,有10个同学去吃冷饮.向服务员交出需要冷饮的统计,数字如下,有6个人要可可;有5个人要咖啡;有5个人要果汁;有3个人既要可可又要果汁;有2个人要可可又要咖啡;有3个人要咖啡又要果汁;有1个人既要可可、咖啡又要了果汁.

求证其中一定有一个人什么冷饮也没有要

[分析与解答]

要了冷饮的总人数为6+5+5-3-2-3+1=9(人),但总人数为10人,故一定有一个人什么冷饮也没有要.

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com