小学奥数 容斥原理之数论问题 精选练习例题 含答案解析(附知识点拨及考点)
- 格式:doc
- 大小:857.51 KB
- 文档页数:8
1. 了解容斥原理二量重叠和三量重叠的内容;
2. 掌握容斥原理的在组合计数等各个方面的应用.
一、两量重叠问题 在一些计数问题中,经常遇到有关集合元素个数的计算.求两个集合并集的元素的个数,不能简单地把两个集合的元素个数相加,而要从两个集合个数之和中减去重复计算的元素个数,即减去交集的元素个数,用式子可表示成:A B A B A B =+-(其中符号“”读作“并”,相当于中文“和”或者“或”的意思;符号“”读作“交”,相当于中文“且”的意思.)则称这一公式为包含与排除原理,简称容斥原理.图示如下:A 表示小圆部分,B 表示大圆部分,C 表示大圆与小圆的公共部分,记为:A B ,即阴影面积.图示如下:A 表示小圆部分,B 表示大圆部分,C 表示大圆与小圆的公共部分,记为:A B ,即阴影面积.
包含与排除原理告诉我们,要计算两个集合A B 、的并集A B 的元素的个数,可分以下两步进行:
第一步:分别计算集合A B 、的元素个数,然后加起来,即先求A B +(意思是把A B 、的一切元素都“包含”进来,加在一起);
第二步:从上面的和中减去交集的元素个数,即减去C A B =(意思是“排除”了重复计算的元素个数).
二、三量重叠问题
A 类、
B 类与
C 类元素个数的总和A =类元素的个数B +类元素个数C +类元素个数-既是A 类又是B 类的元素个数-既是B 类又是C 类的元素个数-既是A 类又是C 类的元素个数+同时是A 类、B 类、C 类的元素个数.用符号表示为:A B C A B C A B B C A C A B C =++---+.图示如下:
教学目标
知识要点
1.先包含——A B +
重叠部分A
B 计算了2次,多加了1次; A B A B +-1
A B
7-7-4 容斥原理之数论问题
在解答有关包含排除问题时,我们常常利用圆圈图(韦恩图)来帮助分析思考.
【例 1】 在1~100的全部自然数中,不是3的倍数也不是5的倍数的数有多少个?
A B
【考点】容斥原理之数论问题 【难度】2星 【题型】解答
【解析】 如图,用长方形表示1~100的全部自然数,A 圆表示1~100中3的倍数,B 圆表示1~100中5的倍
数,长方形内两圆外的部分表示既不是3的倍数也不是5的倍数的数.
由1003331÷=可知,1~100中3的倍数有33个;由100520÷=可知,1~100中5的倍数有20个;
由10035610÷⨯=()可知,1~100既是3的倍数又是5的倍数的数有6个.
由包含排除法,3或5的倍数有:3320647+-=(个).从而不是3的倍数也不是5的倍数的数有
1004753-=(个).
【答案】53
【巩固】 在自然数1100~中,能被3或5中任一个整除的数有多少个?
【考点】容斥原理之数论问题 【难度】2星 【题型】解答
【解析】 1003331÷=,100520÷=,10035610÷⨯=().根据包含排除法,能被3或5中任一个整除的
数有3320647+-=(个).
【答案】47
【巩固】 在前100个自然数中,能被2或3整除的数有多少个?
【考点】容斥原理之数论问题 【难度】2星 【题型】解答
【解析】 如图所示,A 圆内是前100个自然数中所有能被2整除的数,B 圆内是前100个自然数中所有能被3整
除的数,C 为前100个自然数中既能被2整除也能被3整除的数.
前100个自然数中能被2整除的数有:100250÷=(个).由1003331÷=知,前100个自然数中能被
3整除的数有:33个.由1002316
4÷⨯=()知,前100个自然数中既能被2整除也能被3整除的数
有16个. 例题精讲 图中小圆表示A 的元素的个数,中圆表示B 的元素的个数,
C
1.先包含:A B C ++
重叠部分A B 、B C 、C A 重叠了2次,
多加了1次. 2.再排除:A B C A B B C A C ++--- A B C 3A B C ++-
A B B C A C
--A B C A B B C A C A B C ++---+
所以A 中有50个数,B 中有33个数,C 中有16个数.因为A ,B 都包含C ,根据包含排除法得到,
能被2或3整除的数有:50331667+-=(个).
【答案】67
【例 2】 在从1至1000的自然数中,既不能被5除尽,又不能被7除尽的数有多少个?
【考点】容斥原理之数论问题 【难度】2星 【题型】解答
【解析】 1~1000之间,5的倍数有10005⎡⎤⎢⎥⎣⎦=200个,7的倍数有10007⎡⎤⎢⎥⎣⎦
=142个,因为既是5的倍数,又是7的倍数的数一定是35的倍数,所以这样的数有100035⎡⎤⎢⎥⎣⎦
=28个. 所以既不能被5除尽,又不能被7除尽的数有1000-200-142+-28=686个.
【答案】686
【巩固】 求在1至100的自然数中能被3或7整除的数的个数.
【考点】容斥原理之数论问题 【难度】2星 【题型】解答
【解析】 记 A :1~100中3的倍数,100333
1÷=,有33个; B :1~100中7的倍数,1007142÷=,有14个;
A B :1~100中3和7的公倍数,即21的倍数,10021416÷=,有4个. 依据公式,1~100中3的倍数或7的倍数共有3314443+-=个,则能被3或7整除的数的个数为43
个. 【答案】43
【例 3】 以105为分母的最简真分数共有多少个?它们的和为多少?
【考点】容斥原理之数论问题 【难度】4星 【题型】解答
【解析】 以105为分母的最简真分数的分子与105互质,105=3×5×7,所以也是求1到105不是3、5、7倍
数的数有多少个,3的倍数有35个,5的倍数有21个,7的倍数有15个,15的倍数有7个,21的
倍数有5个,35的倍数有3个,105的倍数有1个,所以105以内与105互质的数有
105-35-21-15+7+5+3-1=48个,显然如果n 与105互质,那么(105-n )与n 互质,所以以105为分母
的48个最简真分数可两个两个凑成1,所以它们的和为24.
【答案】48个,和24
【巩固】 分母是385的最简真分数有多少个?并求这些真分数的和.
【考点】容斥原理之数论问题 【难度】4星 【题型】解答
【解析】 385=5×7×11,不超过385的正整数中被5整除的数有77个;被7整除的数有55个;被11整除的
数有35个;被77整除的数有5个;被35整除的数有11个;被55整除的数有7个;被385整除的
数有1个;最简真分数的分子可以有385-77-55-35+5+11+7-1=240.对于某个分数a/385如果是最简真
分数的话,那么(385-a )/385也是最简真分数,所以最简真分数可以每两个凑成整数1,所以这些
真分数的和为120.
【答案】240个,120个
【例 4】 在1至2008这2008个自然数中,恰好是3、5、7中两个数的倍数的数共有 个.
【考点】容斥原理之数论问题 【难度】3星 【题型】填空
【关键词】西城实验
【解析】 1到2008这2008个自然数中,3和5的倍数有200813315⎡⎤=⎢⎥⎣⎦个,3和7的倍数有20089521⎡⎤=⎢⎥⎣⎦
个,5