7-7-4 容斥原理之数论问题.学生版.doc

发布时间：2023-11-21 发布人：admin 分类：养殖资料大小：0.84M 资料格式：doc 举报版权申诉

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

文本预览

7-7-4 容斥原理之数论问题教学目标 1. 了解容斥原理二量重叠和三量重叠的内容； 2. 掌握容斥原理的在组合计数等各个方面的应用．知识要点一、两量重叠问题在一些计数问题中，经常遇到有关集合元素个数的计算．求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，  (其中符号“  ”读作“并”，相当于中文“和”或者“或”的意思；符号“  ” 用式子可表示成： A B A B A B 读作“交”，相当于中文“且”的意思．)则称这一公式为包含与排除原理，简称容斥原理．图示如下: A 表示小圆部分， B 表示大圆部分， C 表示大圆与小圆的公共部分，记为： A B ，即阴影面积．图示如下: A 表示小圆部分， B 表示大圆部分， C 表示大圆与小圆的公共部分，记为： A B ，即阴影面积．     1．先包含—— A B 重叠部分 A B 计算了 2 次，多加了1次； 2．再排除—— A B A B    把多加了1次的重叠部分 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   ．图示如下：             A B 图中小圆表示 A 的元素的个数，中圆表示 B 的元素的个数，大圆表示 C 的元素的个数． C A B C 1．先包含： A B C   A B C 重叠部分 A B 、B C 、C A 重叠了 2 次，多加了1次．    2．再排除： A B C A B B C A C     重叠了 3 次，但是在进行 A B C 重叠部分 A B C A B B C A C  计算时都被减掉了．   3．再包含： A B C A B B C A C A B C              ．       7-7-4.容斥原理之数论问题.题库教师版 page 1 of 6

在解答有关包含排除问题时，我们常常利用圆圈图(韦恩图)来帮助分析思考．例题精讲【例 1】在1 ~ 100 的全部自然数中，不是 3 的倍数也不是 5 的倍数的数有多少个？ A B 【考点】容斥原理之数论问题【难度】2 星【题型】解答【解析】如图，用长方形表示1 ~ 100 的全部自然数， A 圆表示1 ~ 100 中 3 的倍数， B 圆表示1 ~ 100 中 5 的倍【解析】    可知，1 ~ 100 中 3 的倍数有 33 个；由100 5 20 3 5   （）数，长方形内两圆外的部分表示既不是 3 的倍数也不是 5 的倍数的数．由100 3 33 1 由100 由包含排除法， 3 或 5 的倍数有： 33 20 6 100 47 53 可知，1 ~ 100 既是 3 的倍数又是 5 的倍数的数有 6 个． (个)． 6 10     47      可知，1 ~ 100 中 5 的倍数有 20 个； (个)．从而不是 3 的倍数也不是 5 的倍数的数有【答案】 53 【巩固】在自然数1 100~ 中，能被 3 或 5 中任一个整除的数有多少个？【考点】容斥原理之数论问题【难度】2 星【题型】解答【解析】 100 3 33 1 数有 33 20 6   ，100 (个)．    ，100 5 20 3 5   （） 6 10     47  【答案】 47 ．根据包含排除法，能被 3 或 5 中任一个整除的【巩固】在前100 个自然数中，能被 2 或 3 整除的数有多少个？【考点】容斥原理之数论问题【难度】2 星【题型】解答【解析】如图所示，A 圆内是前100 个自然数中所有能被 2 整除的数，B 圆内是前100 个自然数中所有能被 3 整除的数， C 为前100 个自然数中既能被 2 整除也能被 3 整除的数．前100 个自然数中能被 2 整除的数有：100 2 50 3 整除的数有： 33 个．由100 有16 个．所以 A 中有 50 个数， B 中有 33 个数，C 中有16 个数．因为 A ， B 都包含 C ，根据包含排除法得到，能被 2 或 3 整除的数有： 50 33 16 67    知，前100 个自然数中能被知，前100 个自然数中既能被 2 整除也能被 3 整除的数 (个)．由100 3 33 1  （） 16   (个)．   2 3  4    【答案】 67          【例 2】在从 1 至 1000 的自然数中，既不能被 5 除尽，又不能被 7 除尽的数有多少个? 【考点】容斥原理之数论问题【难度】2 星【题型】解答【解析】1～1000 之间，5 的倍数有 1000 5 =200 个，7 的倍数有 1000 7       =142 个，因为既是 5 的倍数，又是 7 的倍数的数一定是 35 的倍数，所以这样的数有 1000 35    =28 个．所以既不能被 5 除尽，又不能被 7 除尽的数有 1000-200-142+-28=686 个．【答案】 686 【巩固】求在 1 至 100 的自然数中能被 3 或 7 整除的数的个数．【考点】容斥原理之数论问题【难度】2 星【题型】解答【解析】记 A：1～100 中 3 的倍数，100 3 33 B：1～100 中 7 的倍数，100 7 14    ，有 33 个；    ，有 14 个； 1 2 A B ：1～100 中 3 和 7 的公倍数，即 21 的倍数，100 21 4  依据公式，1～100 中 3 的倍数或 7 的倍数共有 33 14 4   ，有 4 个． 43   个，则能被 3 或 7 整除的数的个数为 43 16  7-7-4.容斥原理之数论问题.题库教师版 page 2 of 6

个. 【答案】 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 的倍数有 2008 15        个，3、5 和 7 的倍数有 2008 105  和 7 的倍数有 2008 35 的倍数的共有133 19 95 19 57 19   个．         133 228 19 57          个，3 和 7 的倍数有 2008 21    个．     95 个，5 个．所以，恰好是 3、5、7 中两个数【答案】 228 个【例 5】求 1 到 100 内有____个数不能被 2、3、7 中的任何一个整除。【考点】容斥原理之数论问题【难度】3 星【题型】填空【关键词】学而思杯，4 年级，第 12 题【解析】被 2 整除的有 50 个，被 3 整除的有 33 个，被 7 整除的有14 个同时被 2 和 3 整除的有16 个，同时被 2 和 7 整除的有 7 个，同时被 3 和 7 整除的有 4 个同时被 2 和 3 和 7 整除的有 2 个， 50 33 14 16 7 4 2 100 72     个 100 28         【答案】28 个。 3        表示取商的整数部分．例如， 7   2  ．要注意的是，符号  与  、  、 、  符号一样，也是【例 6】在从 1 到 1998 的自然数中，能被 2 整除，但不能被 3 或 7 整除的数有多少个？【考点】容斥原理之数论问题【难度】3 星【题型】解答【解析】 a   b  一种运算，叫取整运算．本题中，先求出能被 2 整除的数有多少个，再分别求出能被 2 和 3、能被 2 和 7 分别整除的数的个数，那么用能被 2 整除的数的个数减去能被 2 和 3 整除的数的个数，再减去能被 2 和 7 整除的数的个数，所得的差是不是所求的得数呢？仔细想想你会发现不是的，因为它多减了能同时被 2、3、 7 整除的数．故能被 2 整除的有：1998 2 999 (个)．能被 2 和 3 同时整除的有：[1998 (个)． 2 3 ] 333    （）能被 2 和 7 同时整除的有：[1998 2 7 ] 142    ．（）能被 2、3、7 同时整除的有：[1998 2 3 7 ] 47     （） (个)．   7-7-4.容斥原理之数论问题.题库教师版 page 3 of 6

所以，能被 2 整除，但不能被 3 或 7 整除的数有 999 333 142 47 571   (个)．【答案】 571个   【例 7】 50 名同学面向老师站成一行．老师先让大家从左至右按 1，2，3，…，49，50 依次报数；再让报数是 4 的倍数的同学向后转，接着又让报数是 6 的倍数的同学向后转．问：现在面向老师的同学还有多少名? 【考点】容斥原理之数论问题【难度】3 星【题型】解答【关键词】华杯赛，初赛，第 13 题【解析】在转过两次后，面向老师的同学分成两类：第一类是标号既不是 4 的倍数，又不是 6 的倍数；第二类是标号既是 4 的倍数又是 6 的倍数． 1～50 之间，4 的倍数有 50   4   =4．于是，第一类同学有 50-12-8+4=34 人，第二类同学有 4 人，      是 12 的倍数，所以有 50 12 =8，即是 4 的倍数又是 6 的倍数的数一定    =12,6 的倍数有 50 6       所以现在共有 34+4=38 名同学面向老师．【答案】 38 名【例 8】体育课上，60 名学生面向老师站成一行，按老师口令，从左到右报数：1，2，3，…，60，然后，老师让所报的数是 4 的倍数的同学向后转，接着又让所报的数是 5 的倍数的同学向后转，最后让所报的数是 6 的倍数的同学向后转，现在面向老师的学生有________人。【考点】容斥原理之数论问题【难度】3 星【题型】填空【关键词】希望杯，六年级，二试，第 15 题，4 分【解析】可知其中 4 的倍数有 15 个，5 的倍数有 12 个，6 的倍数有 10 个，同时是 4 和 5 的倍数的有 3 个，同时是 5 和 6 的倍数的有 2 个，同时是 4 和 6 的倍数的有 5 个，同时是 4、5、6 的倍数的数有 1 个，现在背向老师的有 15+12+10-3-2-5+1=28 个，面向老师的学生有 60-28=32 人。转过两次的有： 3－1+2－1+5－1＝7。最后面向老师的学生数=32+7＝39 个。【答案】 39 个【例 9】有 2000 盏亮着的电灯，各有一个拉线开关控制着，现按其顺序编号为 1，2，3，…，2000，然后将编号为 2 的倍数的灯线拉一下，再将编号为 3 的倍数的灯线拉一下，最后将编号为 5 的倍数的灯线拉一下，三次拉完后，亮着的灯有多少盏？【考点】容斥原理之数论问题【难度】3 星【题型】解答【解析】三次拉完后，亮着的灯包括不是 2、3、5 的倍数的数以及是 6、10、15 的倍数但不是 30 的倍数的数．1～ 2000 这 2000 个正整数中，2 的倍数有 1000 个，3 的倍数有 666 个，5 的倍数有 400 个，6 的倍数有 333 个， 10 的倍数有 200 个， 15 的倍数有 133 个， 30 的倍数有 66 个，亮着的灯一共有 2000-1000-666-400+2×（333+200+133）-4×66=1002 盏．【答案】1002 盏【巩固】2006 盏亮着的电灯，各有一个拉线开关控制，按顺序编号为 1，2，3，……，2006。将编号为 2 的倍数的灯的拉线各拉一下；再将编号为 3 的倍数的灯的拉线各拉一下，最后将编号为 5 的倍数的灯的拉线各拉一下。拉完后这着的灯数为（）盏。【考点】容斥原理之数论问题【难度】3 星【题型】填空【关键词】走美杯，五年级，第 11 题，六年级，第 11 题【解析】因为灯在开始的时候是亮着的，所以拉了两次或者没拉的灯最后还是亮的．这道题实际上是求 1 到 2006 中不能被 2、3、5 整除的数和只能同时被 2、3、5 中 2 个数整除的数的总个数． 7-7-4.容斥原理之数论问题.题库教师版 page 4 of 6

  (盏)，我们可以求得被 2 整除的数有 2006 2 1003 被 3 整除的数有 2006 3 668    ，共 668(盏)， 2 被 5 整除的数有 2006 5 401 1    ，共 401(盏)．其中，同时被 2、3 整除的数有 2006 (2 3) 334 同时被 3、5 整除的有 2006 (3 5) 133 11 同时被 2、5 整除的数有 2006 (2 5)   ，共 200(盏)； 200 同时被 2、3、5 整除的数有 2006 (2 3 5)   个数整除的数的个数为 334 133 200 3 66       ，共 133(盏)；   334 133 200  1003 668 401    2006   535 66               ，共 334(盏)； 2 6   ，共 66(盏)，所以，只能同时被 2、3、5 中 2 66 469  26 (盏)，不能被 2、3、5 整除的数的个数为    ( 盏 ) ．所以，最后亮着的灯一共为 469 535 1004   (盏)．【答案】1004 盏【巩固】写有 1 到 100 编号的灯 100 盏，亮着排成一排，每一次把编号是 3 的倍数的灯拉一次开关，第二次把编号是 5 的倍数的灯拉一次开关，那么亮着的灯还有多少盏？【考点】容斥原理之数论问题【难度】3 星【题型】解答【解析】因为灯在开始的时候是亮着的，所以拉了两次或者没拉的灯最后还是亮的．没拉的灯有【解析】    100 (  100 3    灯一共为 53 6 59 100 5          【答案】 59 盏 100   3 5      (盏) ) 100 (33 20 6) 53      (盏)，拉两次的有 100      3 5  6 (盏)，最后亮着的【例 10】200 名同学编为 1 至 200 号面向南站成一排．第 1 次全体同学向右转（转后所有的同学面朝西）；第 2 次编号为 2 的倍数的同学向右转；第 3 次编号为 3 的倍数的同学向右转；……；第 200 次编号为 200 的倍数的同学向右转；这时，面向东的同学有【考点】容斥原理之数论问题【难度】3 星【题型】填空【关键词】迎春杯，五年级，初赛，10 题【解析】只有约数个数被 4 除余 3 的数，最后面向东．【解析】名．约数个数为 3 的数有 22 、 23 、 25 、 27 、 211 、 213 ，共 8 个数．约数个数为 7 的数有 62 ，1个，约数个数为15 的数有 2 144  ，1个一共有 8 个满足条件的编号． 3 2  4 【答案】 8 名【例 11】下编号是 1、2、3、……36 号的 36 名学生按编号顺序面向里站成一圈.第一次，编号是 1 的同学向后转，第二次，编号是 2、3 的同学向后转，第三次，编号是 4、5、6 的同学向后转，……，第 36 次，全体同学向后转.这时，面向里的同学还有________名. 【考点】容斥原理之数论问题【难度】3 星【题型】填空【关键词】迎春杯，中年级，复试，10 题【解析】整个过程中一共转了 1+2+3+4…+36=666 人次，每转过 72 人次所有学生的朝向就会和原来一样，那【解析】么 666÷72=9…18，于是应该有 18 名同学面朝里，18 名同学面朝外。【答案】18 名【例 12】在游艺会上，有 100 名同学抽到了标签分别为 1 至 100 的奖券．按奖券标签号发放奖品的规则如下：（1）标签号为 2 的倍数，奖 2 支铅笔；（2）标签号为 3 的倍数，奖 3 支铅笔；（3）标签号既是 2 的倍数，又是 3 的倍数可重复领奖；（4）其他标签号均奖 1 支铅笔．那么游艺会为该项活动准备的奖品铅笔共有多少支? 【考点】容斥原理之数论问题【难度】4 星【题型】解答 7-7-4.容斥原理之数论问题.题库教师版 page 5 of 6

【解析】1～100，2 的倍数有 100 【解析】 2    定是 6 的倍数，所以标签为这样的数有 100 6 =50，3 的倍数有 100 3 =16 个．于是，既不是 2 的倍数，又不是 3 的倍数的 =33 个，因为既是 2 的倍数，又是 3 的倍数的数一                数在 1 ～ 100 中有 100-50-33+16=33 ．所以，游艺会为该项活动准备的奖品铅笔共有： 50×2+33×3+33×1=232 支. 【答案】 232 支【例 13】在一根长木棍上，有三种刻度线，第一种刻度线将木棍分成十等份；第二种将木棍分成十二等份；第三种将木棍分成十五等份；如果沿每条刻度线将木棍锯断，则木棍总共被锯成________段．【考点】容斥原理之数论问题【难度】3 星【题型】填空【解析】假设木棍长 60cm ，则沿第一种刻度线锯成的木棍每段长 60 10 6cm 【解析】 4cm  ，沿第三种刻度线锯成的木棍每段长 60 14        段，沿第一、三种重合的刻度线可将木棍锯成 60 [6,4] 5 每段长 60 12 5cm 因为，沿三种刻度线可将木棍分别锯成 10、12、15 段；沿第一、二种重合的刻度线可将木棍锯成 60 [6,5] 2  段，沿第二、三种重合的刻度线可将木棍锯成 60 [5,4] 3  段．应该减去重复计算的沿任意两种重合的刻度线锯成的段数，应加上多减去的沿三种刻度重合的刻度线锯成的段数．所以，沿每条刻度线将木棍锯断，则木棍总共被锯成 10 12 15 2 5 3 1 28  段；沿三种刻度重合的刻度线可将木棍锯成 60 [6,5,4] 1      段．     ，沿第二种刻度线锯成的木棍．  【答案】 28 段【例 14】一根 101 厘米长的木棒，从同一端开始，第一次每隔 2 厘米画一个刻度，第二次每隔 3 厘米画一个刻度，第三次每隔 5 厘米画一个刻度，如果按刻度把木棒截断，那么可以截出段．【考点】容斥原理之数论问题【难度】4 星【题型】填空【关键词】101 中学【解析】要求出截出的段数，应当先求出木棒上的刻度数，而木棒上的刻度数，相当于 1、2、3、…、100、 101 这 101 个自然数中 2 或 3 或 5 的倍数的个数，为： 101 101 101     2 3 5 2 3     出 75 段． 101 2 5  101 2 3  101 3 5  101 5                                        【答案】 75 段  74 ，故木棒上共有 74 个刻度，可以截    【巩固】一根1.8 米长的木棍，从左端开始每隔 2 厘米画一个刻度，涂完后再从左端开始每隔 3 厘米画一个刻【巩固】度，再从左端每隔 5 厘米画一个刻度，再从左端每隔 7 厘米画一个刻度，涂过按刻度把木棍截断，一共可以截成多少段小木棍？【考点】容斥原理之数论问题【难度】4 星【题型】解答【解析】 1.8 米长的木棍，按 2 厘米一段画出刻度，那么也就是说所有的偶数点都已经划过了，即 2、4、6、 8、10……共 89 个点，那么再画 3 的时候所有的偶数点都已经划过，那么会多出 30 个点，即 3、9、 15……，再画 5 的时候会多出来的点是 5、25、35、55、65、85、95、115、125、145、155、175，共 12 个，最后画间隔 7 厘米的时候，会多出 7、49、77、91、119、133、161 共 7 个点，那么所有的刻度总和应该是 89 30 12 7 138   个，那么截断之后应该会有 139 段小木棍．   【答案】139 段【例 15】在循环小数中类似于 1 7   0.142857  ， 1 13   0.076923  等，循环节是从小数点右边的第一位（即十分位）就开始的小数，叫做纯循环小数，包括 7 和13 在内，共有节恰好为六位的纯循环小数。个正整数，其倒数是循环【考点】容斥原理之数论问题【难度】5 星【题型】填空【关键词】学而思杯，6 年级，1 试，第 4 题【解析】根据容斥原理，999999 的约数有 64 个，999 的约数有 8 个，99 的约数有 6 个，9 的约数有 3 个，所求的 n 的个数为 64 (8 6 3) 53    （个）。  【答案】 53 个 7-7-4.容斥原理之数论问题.题库教师版 page 6 of 6

分享到：

赞收藏

资料库

7-7-4 容斥原理之数论问题.学生版.doc

相关推荐

小学奥数

热门标签

最新资料