a小学数学奥赛7 7 4 容斥原理之数论问题教师版

1、 容斥原理之数论问题7-7-4 教学目标 1. 了解容斥原理二量重叠和三量重叠的内容； 2. 掌握容斥原理的在组合计数等各个方面的应用 知识要点 一、两量重叠问题在一些计数问题中，经常遇到有关集合元素个数的计算求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，(其中符号“”读作“并”，相当于中文“和用式子可表示成：”或者“或”的意思；符号“”IBUAUB?A?B?AI读作“交”，相当于中文“且”的意思)则称这一公式为包含与排除原理，简称容斥原理图示如下:表示小圆A，即阴影面积图示如下:表示大圆与小圆的公共部分，

2、记为：表示小圆部分，表示大圆部分，BAICAB，即阴影面积 表示大圆部分，表示大圆与小圆的公共部分，记为：部分，BIACB1先包含 B?A重叠部分计算了次，多加了次； BAI122再排除 BI?AA?B把多加了次的重叠部分减去 BIA1 包含与排除原理告诉我们，要计算两个集合的并集的元素的个数，可分以下两步进行： BUAB、A第一步：分别计算集合的元素个数，然后加起来，即先求(意思是把的一切元素都“包含”进B、ABAB?A来，加在一起)； 第二步：从上面的和中减去交集的元素个数，即减去(意思是“排除”了重复计算的元素个数) B?AIC二、三量重叠问题 类、类与类元素个数的总和类元素的个数类元素

3、个数类元素个数既是类又是类?CC?BAAB?AB?的元素个数既是类又是类的元素个数既是类又是类的元素个数同时是类、类、类的元?CCCBAAB?素个数用符号表示为：图示如下： CI?AIBBB?IC?AICBAUBUC?A?C?AI 图中小圆表示的元素的个数，中圆表示的元素的个数，BA大圆表示的元素的个数 C1先包含： CB?A?重叠部分、重叠了次，多加了次 ACCBIAIBI122再排除： CAIB?IC?BA?C?AIB重叠部分重叠了次，但是在进行 CIBIA?C?B?3A计算时都被减掉了 CIA?BIC?AIB 3再包含： CIBIA?CIA?CIB?BIA?C?B?A (韦恩图)来帮助分

4、析思考在解答有关包含排除问题时，我们常常利用圆圈图 例题精讲 的倍数的数有多少个？的倍数也不是【例 1】 在的全部自然数中，不是511003BA 【题型】解答星 【考点】容斥原理之数论问题 【难度】2的倍中圆表示中的倍数，圆表示【解析】 如图，用长方形表示的全部自然数，51100110011003BA 数，长方形内两圆外的部分表示既不是的倍数也不是的倍数的数53个；个；由可知，中的倍数有由可知，中的倍数有5100?5?100?3?33L1201100110032033 既是的倍数又是的倍数的数有个由可知，63L1051100100?（3?5）?6的倍数的数有)从而不是的倍数也不是(由包含排除法

5、，或的倍数有：个56?4733533?20? 个)(53?100?47 【答案】53 中，能被或中任一个整除的数有多少个？【巩固】 在自然数531001 【题型】解答 【难度】2星 【考点】容斥原理之数论问题 中任一个整除的根据包含排除法，能被或，【解析】 ，5103?6?5?20L100?（3?5）100?3?33L1100 )数有(个47?6?33?20 【答案】47 或整除的数有多少个？【巩固】 在前个自然数中，能被31002 【题型】解答【难度】2星 【考点】容斥原理之数论问题 整个自然数中所有能被图所示，如圆内是前个自然数中所有能被整除的数，圆内是前【解析】 3100100BA2 整

6、除的数除的数，为前个自然数中既能被整除也能被3100C2个自然数中能被知，前整除的数有：(个)由前个自然数中能被100?133L50100?1003?100?22整除的数个自然数中既能被整除的数有：个由知，前整除也能被31002?3）?16L34100?（332 有个16，根据包含排除法得到，中有个数因为，都包含所以中有个数，中有个数，CC16BABA3350 个)整除的数有：能被或(67?33?163502 【答案】67 ? 除尽，又不能被7除尽的数有多少个在从1至1000的自然数中，既不能被5【例 2】 【题型】解答 【难度】2星 【考点】容斥原理之数论问题 10001000?的倍数，又是

7、7的倍数有1000 1之间，5的倍数有=142个，因为既是5=200个，【解析】?75?1000?=28个7的倍数的数一定是35的倍数，所以这样的数有 ?35?所以既不能被5除尽，又不能被7除尽的数有1000-200-142+-28=686个 【答案】 686 【巩固】 求在1至100的自然数中能被3或7整除的数的个数 【考点】容斥原理之数论问题 【难度】2星 【题型】解答 【解析】 记 A：1100中3的倍数，有33个； 13?33LL100B：1100中7的倍数，有14个； 2L14L100?7?：1100中3和7的公倍数，即21的倍数，有4个 BAI16?L4L100?21依据公式，11

8、00中3的倍数或7的倍数共有个，则能被3或7整除的数的个数为4343334?14?. 个 【答案】 43 【例 3】 以105为分母的最简真分数共有多少个？它们的和为多少？ 【考点】容斥原理之数论问题 【难度】4星 【题型】解答 【解析】 以105为分母的最简真分数的分子与105互质，105=357，所以也是求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

9、-n）与n互质，所以以105为分母的48个最简真分数可两个两个凑成1，所以它们的和为24. 【答案】个，和 4824 【巩固】 分母是385的最简真分数有多少个？并求这些真分数的和. 【考点】容斥原理之数论问题 【难度】4星 【题型】解答 【解析】 385=5711，不超过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也是最

10、简真分数，所以最简真分数可以每两个凑成整数1，所以这些真分数的和为120. 【答案】个，个 120240 【例 4】 在1至2008这2008个自然数中，恰好是3、5、7中两个数的倍数的数共有 个 【考点】容斥原理之数论问题 【难度】3星 【题型】填空 【关键词】西城实验 20082008?【解析】 1到2008这2008个自然数中，3和5的倍数有个，3和7的倍数有个，595?133? 1521?20082008?和7的倍数有个，3、5和7的倍数有个所以，恰好是3、5、7中两个数1957? 35105?的倍数的共有个 22819?95?1957?133?19?【答案】个 228 【例 5】 求

11、1到100内有_个数不能被2、3、7中的任何一个整除。 【考点】容斥原理之数论问题 【难度】3星 【题型】填空 【关键词】学而思杯，4年级，第12题 【解析】 被整除的有个，被整除的有个，被整除的有个 733350142同时被和整除的有个，同时被和整除的有个，同时被和整除的有个 7773316422?100?72?2816?7?4?2100?50?33?14?个 和同时被和整除的有个，7322【答案】28个。 【例 6】 在从1到1998的自然数中，能被2整除，但不能被3或7整除的数有多少个？ 【考点】容斥原理之数论问题 【难度】3星 【题型】解答 a7?与、 【解析】表示取商的整数部分例如，

12、要注意的是，符号、符号一样，也是3? 2b?一种运算，叫取整运算 本题中，先求出能被2整除的数有多少个，再分别求出能被2和3、能被2和7分别整除的数的个数，那么用能被2整除的数的个数减去能被2和3整除的数的个数，再减去能被2和7整除的 数的个数，所得的差是不是所求的得数呢？仔细想想你会发现不是的，因为它多减了能同时被2、3、7整除的数 故能被2整除的有：(个) 9991998?2?能被2和3同时整除的有：(个) 333?3）1998?（2?能被2和7同时整除的有： 142?7）?1998?（2能被2、3、7同时整除的有：(个) 47）?3?1998（2?7所以，能被2整除，但不能被3或7整除的

13、数有(个) 571?99933314247?【答案】 个571 依次报数；再让报，5049，2，3，【例 7】 50名同学面向老师站成一行老师先让大家从左至右按1的倍数的同学向后转问：现在面向老师的同学的倍数的同学向后转，接着又让报数是6数是4 ?还有多少名 【题型】解答 【难度】3星 【考点】容斥原理之数论问题 13题【关键词】华杯赛，初赛，第 在转过两次后，面向老师的同学分成两类：【解析】 6的倍数4的倍数，又不是6的倍数；第二类是标号既是4的倍数又是第一类是标号既不是5050?的倍数的数一定=,之间，即是的倍数有的倍数有=的倍数又是6412504618?64?50?人，人，第二类同学有-

14、+=于是，第一类同学有是-的倍数，所以有483412124450?12? 名同学面向老师所以现在共有+=38344 名【答案】38 ，然后，60，21，3，【例 8】 体育课上，60名学生面向老师站成一行，按老师口令，从左到右报数：的倍数的同学向后转，最后让5 所报的数是老师让所报的数是4的倍数的同学向后转，接着又让 人。的倍数的同学向后转，现在面向老师的学生有_所报的数是6 3【题型】填空【考点】容斥原理之数论问题【难度】星 415分【关键词】希望杯，六年级，二试，第题，个，35的倍数的有个，同时是4和15个，5的倍数有12个，6的倍数有10【解析】 可知其中4的倍数有16的倍数的数有4、5

15、、2个，同时是4和6的倍数的有5个，同时是6同时是5和的倍数的有人。转过两次的有：个，面向老师的学生有60-28=32个，现在背向老师的有15+12+10-3-2-5+1=28 39个。7。最后面向老师的学生数=32+71+21+513 39个【答案】 ，然后，20003，有2000盏亮着的电灯，各有一个拉线开关控制着，现按其顺序编号为1，2，【例 9】 的倍数的的倍数的灯线拉一下，最后将编号为52的倍数的灯线拉一下，再将编号为3将编号为 灯线拉一下，三次拉完后，亮着的灯有多少盏？DBA32GEFC5 【题型】解答 【难度】3星 【考点】容斥原理之数论问题130的倍数的数、10、15的倍数但不

16、是2 三次拉完后，亮着的灯包括不是、3、5的倍数的数以及是6【解析】的倍数有6400个，666个，5的倍数有这2000个正整数中，2的倍数有1000个，3的倍数有2000个，亮着的灯一共有的倍数有66的倍数有133个，30333个，10的倍数有200个，15 66=1002盏333+200+133）-42000-1000-666-400+2（ 【答案】盏1002 的2，2006。将编号为，2，3，006【巩固】 2盏亮着的电灯，各有一个拉线开关控制，按顺序编号为1的倍数的灯5倍数的灯的拉线各拉一下；再将编号为3的倍数的灯的拉线各拉一下，最后将编号为 ）盏。的拉线各拉一下。拉完后这着的灯数为（

17、【题型】填空【难度】3星 【考点】容斥原理之数论问题 11题【关键词】走美杯，五年级，第11题，六年级，第 因为灯在开始的时候是亮着的，所以拉了两次或者没拉的灯最后还是亮的这道题实际上是求【解析】 2中个数整除的数的总个数2、3、5521到2006中不能被、3、整除的数和只能同时被 ，(整除的数有盏)2我们可以求得被10032006?2? ，)盏668(，共整除的数有被32L668?3?2006 )，共被5整除的数有401(盏1401L2006?5? )；3整除的数有，共334(盏其中，同时被2、2L2006?(2?3)?334 )；5整除的有，共133(盏同时被3、11L2006?(3?5)

18、?133 )；5整除的数有，共200(盏同时被2、6L2006?(2?5)?20025中2、3、3、5整除的数有，共66(盏)，所以，只能同时被同时被2、26?66L2006?(2?3?5) 5整除的数的个数为2、3、个数整除的数的个数为(盏)，不能被469?66334?133?200?3?为共着的灯一)所以，最后亮(盏535?66?334?133?2006?2004011003?668? (盏)1004469?535? 盏【答案】1004 的倍数的灯拉一次开关，第二次3100编号的灯100盏，亮着排成一排，每一次把编号是【巩固】 写有1到 的倍数的灯拉一次开关，那么亮着的灯还有多少盏？把编号

19、是5 【题型】解答 【考点】容斥原理之数论问题 【难度】3星有灯没拉的后还是亮的拉，所以了两次或者没拉的灯最因【解析】 为灯在开始的时候是亮着的100100100100?，最后亮着的(盏)(盏)，拉两次的有653?6)?100?(?)?100?(33?20? 553?53?3? (盏)灯一共为59?53?6 【答案】盏59 ；1次全体同学向右转（转后所有的同学面朝西）名同学编为1至200号面向南站成一排第【例 10】 200次编号；第2003次编号为3的倍数的同学向右转；第2次编号为2 的倍数的同学向右转；第 名 200的倍数的同学向右转；这时，面向东的同学有 为 【题型】填空3星 【考点】容

20、斥原理之数论问题 【难度】 题10【关键词】迎春杯，五年级，初赛， 的数，最后面向东 只有约数个数被除余【解析】34222222 、个数、，共的数有约数个数为的数有个，约数个数为72142 个，约数个数为的数有144?23?151 一共有个满足条件的编号 8 【答案】名8 的同学向.第一次，编号是1、36号的36名学生按编号顺序面向里站成一圈 11【例】 下编号是1、2、336，第、5、6的同学向后转，后转，第二次，编号是2、3的同学向后转，第三次，编号是4. _名次，全体同学向后转.这时，面向里的同学还有 【题型】填空3星 【考点】容斥原理之数论问题 【难度】 题【

21、关键词】迎春杯，中年级，复试，10人次所有学生的朝向就会和原来一样，那72个过程中一共转了1+2+3+4+36=666人次，每转过【解析】 整 名同学面朝外。18名同学面朝里，18么66672=918，于是应该有 名【答案】18 100的奖券按奖券标签号发放奖品的规则如下：在游艺会上，有100名同学抽到了标签分别为1至 12【例】 2支铅笔；2（1）标签号为的倍数，奖 3支铅笔；（2）标签号为3的倍数，奖 的倍数可重复领奖；23）标签号既是的倍数，又是3（ 支铅笔（4）其他标签号均奖1? 那么游艺会为该项活动准备的奖品铅笔共有多少支 【题型】解答 【难度】4星 【考点】容斥原理之数论问题100

22、100?=33个，因为既是2的倍数，又是3的倍数的数一21001】解【析 ，的倍数有3=50，的倍数有?32? 100?=16个于是，既不是2的倍数，又不是3定是6的倍数的的倍数，所以标签为这样的数有?6?数在1100中有100-50-33+16=33所以，游艺会为该项活动准备的奖品铅笔共有：502+333+331=232支. 【答案】支 232 【例 13】 在一根长木棍上，有三种刻度线，第一种刻度线将木棍分成十等份；第二种将木棍分成十二等份；第三种将木棍分成十五等份；如果沿每条刻度线将木棍锯断，则木棍总共被锯成_段 【考点】容斥原理之数论问题 【难度】3星 【题型】填空 【解析】 假设木棍

23、长，则沿第一种刻度线锯成的木棍每段长，沿第二种刻度线锯成的木棍6cm?60?60cm10每段长，沿第三种刻度线锯成的木棍每段长 4cm?60?1460?12?5cm因为，沿三种刻度线可将木棍分别锯成10、12、15段；沿第一、二种重合的刻度线可将木棍锯成段，沿第一、三种重合的刻度线可将木棍锯成段，沿第二、三种重合的刻56,4?60?60?6,5?2度线可将木棍锯成段；沿三种刻度重合的刻度线可将木棍锯成段应该16,5,4?60?60?5,4?3减去重复计算的沿任意两种重合的刻度线锯成的段数，应加上多减去的沿三种刻度重合的刻度线锯成的段数所以，沿每条刻度线将木棍锯断，则木棍总共被锯成 段 28?3?115?2?5?10?12?【答案】段 28 【例 14】 一根101厘米长的木棒，从同一端开始，第一次每隔2厘米画一个刻度，第二次每隔3厘米画一个刻度，第三次每隔5厘米画一个刻度，如果按刻度把木棒截断，那么可以截出 段 【考点】容斥原理之数论问题 【难度】4星 【题型】填空 【关键词】101中学 【解析】 要求