小学奥数训练专题 容斥原理之数论问题.学生版.doc

7-7-4容斥原理之数论问题教学目标1.了解容斥原理二量重叠和三量重叠的内容；2.掌握容斥原理的在组合计数等各个方面的应用．知识要点一、两量重叠问题在一些计数问题中，经常遇到有关集合元素个数的计算．求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，用式子可表示成：A B=A+B-A B(其中符号“”读作“并”，相当于中文“和”或者“或”的意思；符号“”读作“交”，相当于中文“且”的意思．)则称这一公式为包含与排除原理，简称容斥原理．图示如下:A表示小圆部分，B表示大圆部分，C表示大圆与小圆的公共部分，记为：A B，即B，阴影面积．图示如下:A表示小圆部分，B表示大圆部分，C表示大圆与小圆的公共部分，记为：A即阴影面积．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．图示如下：1÷ = ÷ = ÷ =图中小圆表示 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 重叠了 3 次，但是在进行 A + B + C - A B - B C - A C 计算时都被减掉了．3．再包含： A + B + C - A B - B C - A C + A B C ．在解答有关包含排除问题时，我们常常利用圆圈图(韦恩图)来帮助分析思考．例题精讲【例 1】 在 1~100 的全部自然数中，不是 3 的倍数也不是 5 的倍数的数有多少个？A B【考点】容斥原理之数论问题 【难度】2 星 【题型】解答【解析】如图，用长方形表示1~100 的全部自然数，A 圆表示1~100 中 3 的倍数，B 圆表示1~100 中 5的倍数，长方形内两圆外的部分表示既不是3 的倍数也不是 5 的倍数的数．由 100 ÷ 3 = 33 1 可知， 1~100 中 3 的倍数有 33 个；由 100 ÷ 5 = 20 可知， 1~100 中 5 的倍数有 20 个； 由 100 （3 ⨯ 5） 6 10 可知，1~100 既是 3 的倍数又是 5 的倍数的数有 6 个．由包含排除法， 3 或 5 的倍数有： 33 + 20 - 6 = 47( 个 ) ．从而不是 3 的倍数也不是 5 的倍数的数有 100 - 47 = 53 (个)． 【答案】 53【巩固】 在自然数1~100 中，能被 3 或 5 中任一个整除的数有多少个？ 【考点】容斥原理之数论问题 【难度】2 星 【题型】解答 【解析】 100 ÷ 3 = 33 1 ， 100 ÷ 5 = 20 ， 100 （3 ⨯ 5） 6 10 ．根据包含排除法，能被 3 或 5 中任一个整除的数有 33 + 20 - 6 = 47 (个)．【答案】 47【巩固】 在前 100 个自然数中，能被 2 或 3 整除的数有多少个？ 【考点】容斥原理之数论问题 【难度】2 星 【题型】解答【解析】如图所示， A 圆内是前100 个自然数中所有能被 2 整除的数， B 圆内是前100 个自然数中所有能被 3 整除的数， C 为前100 个自然数中既能被 2 整除也能被 3 整除的数．前 100 个自然数中能被 2 整除的数有：100 ÷ 2 = 50 (个)．由100 ÷3 = 33 1 知，前100 个自然数中能被 3 整除的数有：33 个．由100 （2 ⨯ 3） 16 4 知，前100 个自然数中既能被 2 整除也能被 3 整除的数有16 个．所以 A 中有 50 个数， B 中有 33 个数， C 中有16 个数．因为 A ， B 都包含 C ，根据包含排除法得到， 能被 2 或 3 整除的数有： 50 + 33 - 16 = 67 (个)． 【答案】 672⎣ ⎣ 【解析】1 到 2008 这 2008 个自然数中，3 和 5 的倍数有 ⎢ = 133 个，3 和 7 的倍数有 ⎢ ⎦⎦个，5 和 7 的倍数有 ⎢ = 57 个，3、5 和 7 的倍数有 ⎢ ⎥ = 19 个．所以，恰好是 3、5、 ⎣ 35 ⎦⎣ 105 ⎦【例 2】 在从 1 至 1000 的自然数中，既不能被 5 除尽，又不能被 7 除尽的数有多少个? 【考点】容斥原理之数论问题 【难度】2 星 【题型】解答【解析】1～1000 之间，5 的倍数有 ⎡1000 ⎤ =200 个，7 的倍数有 ⎡1000 ⎤ =142 个，因为既是 5 的倍数，⎢5 ⎥⎦ ⎢7 ⎥⎦又是 7 的倍数的数一定是 35 的倍数，所以这样的数有 ⎡1000 ⎤ =28 个．⎢⎣ 35 ⎥⎦所以既不能被 5 除尽，又不能被 7 除尽的数有 1000-200-142+-28=686 个．【答案】 686【巩固】 求在 1 至 100 的自然数中能被 3 或 7 整除的数的个数． 【考点】容斥原理之数论问题 【难度】2 星 【题型】解答 【解析】记 A ：1～100 中 3 的倍数，100 ÷ 3 = 33 1 ，有 33 个；B ：1～100 中 7 的倍数，100 ÷ 7 = 14 2 ，有 14 个；A B ：1～100 中 3 和 7 的公倍数，即 21 的倍数，100 ÷ 21 = 4 16 ，有 4 个．依据公式，1～100 中 3 的倍数或 7 的倍数共有 33 + 14 - 4 = 43 个，则能被 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 星 【题型】填空 【关键词】西城实验⎡ 2008 ⎤ ⎡ 2008 ⎤ ⎣ 15 ⎥ ⎣ 21 ⎥= 95⎡ 2008 ⎤ ⎡ 2008 ⎤ ⎥ 7 中两个数的倍数的共有133 - 19 + 95 - 19 + 57 - 19 = 228 个．【答案】 228 个【例 5】 求 1 到 100 内有____个数不能被 2、3、7 中的任何一个整除。

3【解析】 ⎢ ⎥ 表示取商的整数部分．例如，⎢ ⎥ = 3 ．要注意的是，符号 [ ]与 + 、- 、⨯ 、÷ 符号一样，÷ ] ÷ ] ÷ ] ⎣ ⎣【考点】容斥原理之数论问题 【难度】3 星 【题型】填空 【关键词】学而思杯，4 年级，第 12 题【解析】被 2 整除的有 50 个，被 3 整除的有 33 个，被 7 整除的有14 个同时被 2 和 3 整除的有16 个，同时被 2 和 7 整除的有 7 个，同时被 3 和 7 整除的有 4 个 同时被 2 和 3 和 7 整除的有 2 个，100 - (50 + 33 + 14 - 16 - 7 - 4 + 2 ) = 100 - 72 = 28 个【答案】28 个。

【例 6】 在从 1 到 1998 的自然数中，能被 2 整除，但不能被 3 或 7 整除的数有多少个？ 【考点】容斥原理之数论问题 【难度】3 星 【题型】解答⎡ a ⎤ ⎡ 7 ⎤ ⎣ b ⎦ ⎣ 2 ⎦ 也是一种运算，叫取整运算．本题中，先求出能被 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 (个)．所以，能被 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 ⎤ =12,6 的倍数有 ⎡ 50 ⎤ =8，即是 4 的倍数又是 6 的倍数的数一定是⎢ 4 ⎥⎦ ⎢ 6 ⎥⎦ 12 的倍数，所以有 ⎡ 50 ⎤ =4．于是，第一类同学有 50-12-8+4=34 人，第二类同学有 4 人，所以⎢⎣ 12 ⎥⎦现在共有 34+4=38 名同学面向老师． 【答案】 38 名【例 8】 体育课上，60 名学生面向老师站成一行，按老师口令，从左到右报数：1，2，3， (60)然后，老师让所报的数是 4 的倍数的同学向后转，接着又让 所报的数是 5 的倍数的同学向 后转，最后让所报的数是 6 的倍数的同学向后转，现在面向老师的学生有________人。