容斥原理之数论问题.教师版.pdf
《容斥原理之数论问题.教师版.pdf》由会员分享,可在线阅读,更多相关《容斥原理之数论问题.教师版.pdf(7页珍藏版)》请在三一文库上搜索。
1、专业文档 珍贵文档 1. 了解容斥原理二量重叠和三量重叠的内容; 2. 掌握容斥原理的在组合计数等各个方面的应用 一、两量重叠问题 在一些计数问题中,经常遇到有关集合元素个数的计算求两个集合并集的元素的个数,不能简单地把 两个集合的元素个数相加,而要从两个集合个数之和中减去重复计算的元素个数,即减去交集的元素个数, 用式子可表示成:ABABAB(其中符号 “ ” 读作 “ 并” ,相当于中文 “ 和” 或者 “ 或” 的意思;符号“ ” 读作 “ 交 ” ,相当于中文 “ 且 ” 的意思 )则称这一公式为包含与排除原理,简称容斥原理图示如下:A表示小圆 部分, B表示大圆部分,C 表示大圆与小
2、圆的公共部分,记为:AB,即阴影面积图示如下 :A表示小圆 部分,B表示大圆部分,C 表示大圆与小圆的公共部分,记为:AB,即阴影面积 包含与排除原理告诉我们,要计算两个集合AB、的并集 AB 的元素的个数,可分以下两步进行: 第一步:分别计算集合AB、的元素个数,然后加起来,即先求AB(意思是把AB、的一切元素都“ 包含 ” 进 来,加在一起); 第二步:从上面的和中减去交集的元素个数,即减去CAB (意思是 “ 排除 ” 了重复计算的元素个数) 二、三量重叠问题 A类、B类与 C 类元素个数的总和A类元素的个数B类元素个数C 类元素个数既是A类又是B类 的元素个数既是B类又是 C 类的元素
3、个数既是A类又是 C 类的元素个数同时是A类、B类、 C 类的元 素个数用符号表示为:ABCABCABBCACABC 图示如下: 教学目标 知识要点 1先包含AB 重叠部分AB计算了 2次,多加了1次; 2再排除ABAB 把多加了1次的重叠部分AB 减去 图中小圆表示A的元素的个数,中圆表示B的元素的个数, 大圆表示 C 的元素的个数 1先包含:ABC 重叠部分AB 、BC 、CA重叠了2次,多加了1次 2再排除:ABCABBCAC 重叠部分ABC 重叠了 3次,但是在进行ABC ABBCAC 计算时都被减掉了 3再包含:ABCABBCACABC 7-7-4 容斥原理之数论问题 专业文档 珍贵
4、文档 在解答有关包含排除问题时,我们常常利用圆圈图(韦恩图 )来帮助分析思考 【例1】在 1 100的全部自然数中,不是3的倍数也不是5 的倍数的数有多少个? A B 【考点】容斥原理之数论问题【难度】 2 星【题型】解答 【解析】如图,用长方形表示1100的全部自然数,A圆表示 1 100中 3的倍数,B圆表示 1100 中 5 的倍 数,长方形内两圆外的部分表示既不是3的倍数也不是5 的倍数的数 由 1003331可知, 1 100中 3的倍数有 33 个;由 100520可知, 1 100中 5 的倍数有 20个; 由 10035610()可知, 1100既是 3的倍数又是5 的倍数的数
5、有6 个 由包含排除法,3或 5 的倍数有:3320647 (个 )从而不是3的倍数也不是5 的倍数的数有 1004753 (个) 【答案】 53 【巩固】 在自然数 1 100中,能被 3或 5中任一个整除的数有多少个? 【考点】容斥原理之数论问题【难度】 2 星【题型】解答 【解析】 1003331, 100520 , 10035610()根据包含排除法,能被3或 5 中任一个整除的 数有 3320647(个) 【答案】 47 【巩固】在前 100个自然数中,能被2或 3整除的数有多少个? 【考点】容斥原理之数论问题【难度】 2 星【题型】解答 【解析】 如图所示,A圆内是前 100个自然
6、数中所有能被2整除的数,B圆内是前 100个自然数中所有能被3整 除的数, C 为前 100个自然数中既能被2整除也能被 3整除的数 前 100个自然数中能被2整除的数有: 100250(个)由 100 3331知,前 100个自然数中能被 3整除的数有:33 个由 100 23164()知,前 100个自然数中既能被 2整除也能被 3整除的数 有16 个 所以A中有 50 个数,B中有 33 个数, C 中有 16 个数因为A,B都包含 C ,根据包含排除法得到, 能被2或 3整除的数有:50331667 (个) 【答案】 67 【例2】在从 1 至 1000 的自然数中,既不能被5 除尽,
7、又不能被7 除尽的数有多少个? 【考点】容斥原理之数论问题【难度】 2 星【题型】解答 【解析】 11000 之间, 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:1100 中 3 的倍数, 1003331
8、,有 33 个; B:1100 中 7 的倍数, 1007142 ,有 14 个; AB :1 100 中 3 和 7 的公倍数,即21 的倍数, 10021416 ,有 4 个 例题精讲 专业文档 珍贵文档 依据公式, 1100 中 3 的倍数或7 的倍数共有3314443 个,则能被 3 或 7 整除的数的个数为43 个. 【答案】 43 【例3】以 105 为分母的最简真分数共有多少个?它们的和为多少? 【考点】容斥原理之数论问题【难度】 4 星【题型】解答 【解析】 以 105 为分母的最简真分数的分子与105 互质, 105=3 5 7,所以也是求1 到 105 不是 3、5、7 倍
9、 数的数有多少个,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
10、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 中两个数的倍数
11、的数共有个 【考点】容斥原理之数论问题【难度】 3 星【题型】填空 【关键词】西城实验 【解析】 1 到 2008 这 2008 个自然数中,3 和 5 的倍数有 2008 133 15 个, 3 和 7 的倍数有 2008 95 21 个, 5 和 7 的倍数有 2008 57 35 个, 3、 5 和 7 的倍数有 2008 19 105 个所以,恰好是3、 5、7 中两个数 的倍数的共有1331995195719228 个 【答案】 228个 【例5】求 1 到 100 内有 _个数不能被2、3、7 中的任何一个整除。 【考点】容斥原理之数论问题【难度】 3 星【题型】填空 【关键词】学
12、而思杯,4 年级,第12 题 【解析】 被2整除的有 50 个,被 3整除的有 33 个,被 7整除的有 14个 同时被2和 3整除的有 16 个,同时被2和 7整除的有 7 个,同时被3和 7 整除的有4个 同时被 2和 3和 7 整除的有2个, 100 503314167421007228 个 【答案】 28 个。 【例6】在从 1 到 1998 的自然数中,能被2 整除,但不能被3 或 7 整除的数有多少个? 【考点】容斥原理之数论问题【难度】 3 星【题型】解答 【解析】 a b 表示取商的整数部分例如, 7 3 2 要注意的是,符号与、符号一样,也是 一种运算,叫取整运算 本题中,先
13、求出能被2 整除的数有多少个,再分别求出能被2 和 3、能被 2 和 7 分别整除的数的个 数,那么用能被2 整除的数的个数减去能被2 和 3整除的数的个数,再减去能被2 和 7 整除的 数的个数, 所得的差是不是所求的得数呢?仔细想想你会发现不是的,因为它多减了能同时被2、3、 7 整除的数 故能被 2 整除的有: 19982999(个) 能被 2 和 3 同时整除的有:199823 333()(个) 能被 2 和 7 同时整除的有:199827 142() 专业文档 珍贵文档 能被 2、 3、7 同时整除的有:1998237 47()(个) 所以,能被2 整除,但不能被3 或 7 整除的数
14、有99933314247571 (个) 【答案】 571个 【例7】50 名同学面向老师站成一行老师先让大家从左至右按1,2,3, ,49,50 依次报数;再让报 数是 4 的倍数的同学向后转,接着又让报数是6 的倍数的同学向后转问:现在面向老师的同学 还有多少名 ? 【考点】容斥原理之数论问题【难度】 3 星【题型】解答 【关键词】华杯赛,初赛,第13 题 【解析】 在转过两次后,面向老师的同学分成两类: 第一类是标号既不是4 的倍数,又不是6 的倍数;第二类是标号既是4 的倍数又是6 的倍数 150之间,4的倍数有 50 4 =12,6的倍数有 50 6 =8,即是4的倍数又是6的倍数的数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 原理 数论 问题 教师版
链接地址:https://www.31doc.com/p-4509894.html