初一数学竞赛讲座⑽计数的方法与原理
上传者:方春|上传时间:2015-05-11|密次下载
初一数学竞赛讲座⑽计数的方法与原理
初一数学竞赛讲座
第10讲 计数的方法与原理
计数方法与原理是组合数学的主要课题之一,本讲介绍一些计数的基本方法及计数的基本原理。
一、枚举法
一位旅客要从武汉乘火车去北京,他要了解所有可供乘坐的车次共有多少,一个最易行的办法是找一张全国列车运行时刻表,将所有从武汉到北京的车次逐一挑出来,共有多少次车也就数出来了,这种计数方法就是枚举法。所谓枚举法,就是把所要求计数的所有对象一一列举出来,最后计算总数的方法。运用枚举法进行列举时,必须注意无一重复,也无一遗漏。
例1 四个学生每人做了一张贺年片,放在桌子上,然后每人去拿一张,但不能拿自己做的一张。问:一共有多少种不同的方法?
解:设四个学生分别是A,B,C,D,他们做的贺年片分别是a,b,c,d。 先考虑A拿B做的贺年片b的情况(如下表),一共有3种方法。
内容需要下载文档才能查看
同样,A拿C或D做的贺年片也有3种方法。
一共有3+3+3=9(种)不同的方法。
例2 甲、乙二人打乒乓球,谁先连胜两局谁赢,若没有人连胜头两局,则谁先胜三局谁赢,打到决出输赢为止。问:一共有多少种可能的情况? 解:如下图,我们先考虑甲胜第一局的情况:
内容需要下载文档才能查看
图中打√的为胜者,一共有7种可能的情况。同理,乙胜第一局也有 7种可能的情况。一共有 7+7=14(种)可能的情况。
二、加法原理
如果完成一件事情有n类方法,而每一类方法中分别有m1,m2,?,mn种方法,而不论采用这些方法中的任何一种,都能单独地完成这件事情,那么要完成这件事情共有:N=m1+m2+?mn种方法。
这是我们所熟知的加法原理,也是利用分类法计数的依据。
1
例3 一个自然数,如果它顺着数和倒着数都是一样的,则称这个数为“回文数”。例如1331,7,202都是回文数,而220则不是回文数。问:1到6位的回文数一共有多少个?按从小到大排,第2000个回文数是多少?
解:一位回文数有:1,2,?,9,共9个;
二位回文数有:11,22,?,99,共9个;
三位回文数有:101,111,?,999,共90个;
四位回文数有:1001,1111,?,9999,共90个;
五位回文数有:10001,10101,?,99999,共900个;
六位回文数有:100001,101101,?,999999,共900个。
到六位数为止,回文数共有
9+9+90+90+900+900=1998(个)。
第1999个回文数是1000001,第2000个回文数是1001001。
例4 设有长度为1,2,?,9的线段各一条,现在要从这9条线段中选取若干条组成一个正方形,共有多少种不同的取法?这里规定当用2条或多条线段接成一条边时,除端点外,不许重叠。
解法1:因为
内容需要下载文档才能查看
所以正方形的边长不大于11。
下面按正方形的边长分类枚举:
(1)边长为11:9+2=8+3=7+4=6+5,可得1种选法;
(2)边长为10:9+1=8+2=7+3=6+4,可得1种选法;
(3)边长为 9:9=8+1=7+2=6+3=5+4,可得5种选法;
(4)边长为8:8=7+1=6+2=5+3,可得1种选法;
(5)边长为7:7=6+1=5+2=4+3,可得1种选法;
(6)边长≤6时,无法选择。
综上计算,不同的取法共有
1+1+5+1+1=9(种)。
解法2:由于这些线段互不等长,故至少要用7条线段才能组成一个正方形。当恰取7条线段组成正方形时,正方形的3条边各用2条线相接,另一条边只用一条线段;当恰用8条线段时,只能每边各用2条线段相接(容易看出,其他情况不可能发生)。因为 1+2+?+9=45, 45不能被4整除,所以用9条线段,不可能组成正方形。由解法一知,拼出的正方形边长至多为11,又易知正方形的边长不可能为1,2,3,4,5,6。有了以上分析就容易计数了。
(1)取出7条线段,有以下7种:
7=1+6=2+5=3+4;
8=1+7=2+6=3+5;
9=1+8=2+7=3+6=4+5
(这个式子有5种);
(2)取出8条线段,有以下2种:
1+9=2+8=3+7=4+6;
2+9=3+8=4+7=5+6。
综上所述,不同的取法共有7+2=9(种)。
三、乘法原理
2
如果完成一件事必须分n个步骤,而每一个步骤分别有m1,m2,?,mn种方法,那么完成这件事共有:N=m1×m2×?×mn种方法。
这就是乘法原理,它是分步法的依据。乘法原理和加法原理被称为是计数的基本原理。我们应注意它们的区别,也要注意二者的联合使用。
例5 一台晚会上有6个演唱节目和4个舞蹈节目。求:
(1)当4个舞蹈节目要排在一起时,有多少不同的安排节目的顺序?
(2)当要求每2个舞蹈节目之间至少安排1个演唱节目时,一共有多少不同的安排节目的顺序?
解:(1)先将4个舞蹈节目看成1个节目,与6个演唱节目一起排,有 7!=7×6×5×4×3×2×1=5404(种)方法。
第二步再排4个舞蹈节目,有4!=4×3×2×1=24(种)方法。
根据乘法原理,一共有 5040×24=120960(种)方法。
(2)首先将6个演唱节目排成一列(如下图中的“□”),一共有6!=6×5×4×3×2 ×1=720(种)方法。
×□×□×□×□×□×□×
第二步,再将4个舞蹈节目排在一头一尾或2个演唱节目之间(即上图中“×”的位置),这相当于从7个“×”中选4个来排,一共有7×6×5×4=840(种)方法。
根据乘法原理,一共有720×840=604800(种)方法。
例6 有8个队参加比赛,如果采用下面的淘汰制,那么在赛前抽签时,实际上可以得到多少种不同的安排表?
内容需要下载文档才能查看
解:8个队要经过3轮比赛才能确定冠亚军。将第1轮的4组,自左至右记为1,2,3,4组,其中第1,2组为甲区,3,4组为乙区。8个队抽签即是在上图的8个位置排列,共有
8!=8×7×6×5×4×3×2×1=40320(种)
不同的方法。
但是,两种不同的排列不一定是实际上不同比赛的安排表。事实上,8队中的某4队都分在甲区或乙区,实际上是一样的;同区的4队中某2队在某一组或另一组,实际上也是一样的;同组中的2队,编号谁是奇数谁是偶数实际也是一样的。
由乘法原理知,在40320种排法中,与某一种排法实质上相同的排法有 2×22×24=27=128(种),故按实际不同比赛安排表的种数是
内容需要下载文档才能查看
四、对应法
小孩子数苹果,往往掰着手指头,一个一个地掰,掰完左手掰右手,这种数苹果的方法就是对应法。小孩子把苹果与自己的手指头一对一,他掰了几个指头,也就数出了几个苹果。一般地,如果两类对象彼此有一对一的关系,那么我们可以通过对一类较易计数的对象计数,而得出具有相同数目的另一类难于计数的对象的个数。
3
例7 在8×8的方格棋盘中,取出一个由 3个小方格组成的“L”形(如图
1),一共有多少种不同的方法?
内容需要下载文档才能查看
解:每一种取法,有一个点与之对应,这就是图1中的A点,它是棋盘上横线与竖线的交点,且不在棋盘边上。
从图2可以看出,棋盘内的每一个点对应着4个不同的取法(“L”形的“角”在2×2正方形的不同“角”上)。
由于在 8×8的棋盘上,内部有7×7=49(个)交叉点,故不同的取法共有 49×4=196(种)。
例8 数3可以用4种方法表示为1个或几个正整数的和,如3,1+2,2+1,1+1+1。问:1999表示为1个或几个正整数的和的方法有多少种?
分析与解:我们将1999个1写成一行,它们之间留有1998个空隙,在这些空隙处,或者什么都不填,或者填上“+”号。例如对于数3,上述4种和的表达方法对应:
111,11+1,1+11,1+1+1。
显然,将1999表示成和的形式与填写1998个空隙处的方式之间一对一,而每一个空隙处都有填“+”号和不填“+”号2种可能,因此1999可以表示为正整数之和的不同方法有
内容需要下载文档才能查看
五、容斥原理
在应用加法原理时,关键在于把所要计数的对象分为若干个不重不漏的类,使得每类便于计数。但是具体问题往往是复杂的,常常扭成一团,难以分为不重不漏的类,而要把条理分清楚就得用加法原理的推广——容斥原理。
为了表达方便,我们用A表示A类元素的个数,用B表示B类元素的个数,用 A∪B表示是 A类或是 B类元素的个数,用A∩B表示既是A类又是B类元素的个数。A∪B∩C,A∪B∩C的意义类似。
容斥原理1 如果被计数的事物有两类,那么A∪B=A+B-A∩B。
容斥原理2 如果被计数的事物有三类,那么A∪B∪C=A+B+C-A∩B-B∩C-A∩C+A∩B∩B。
容斥原理的实质在于包含与排除,或形象地称之为“多退少补”。容斥原理若用韦恩图进行分析和记忆,十分方便,留给读者研究。
例9 在100名学生中,有10人既不会骑自行车又不会游泳,有65人会骑自行车,有73人会游泳,既会骑自行车又会游泳的有多少人?
解:从100名总人数中减去既不会骑自行车又不会游泳的10人,就是会骑自行车或会游泳的人数
100-10=90(人)。
既会骑自行车又会游泳的有(65+73)-90=48(人)。
例10 在1至100的自然数中,不能被2整除,又不能被3整除,还不能被5整除的数,占这100个自然数的百分之几?
4
解:由容斥原理2知,1至100的自然数中,或能被2整除,或能被3整除,或能被5整除的自然数的个数是
内容需要下载文档才能查看
=50+33+20-16-6+3=74。
所以,在1至100的自然数中,不能被2整除,又不能被3整除,还不能被5整除的自然数有100-74=26(个),占这100个自然数的26%。
六、归纳法
对于比较复杂的问题,可以先观察其简单情况,归纳出其中带规律性的东西,然后再来解决较复杂的问题。
例11 10个三角形最多将平面分成几个部分?
解。设n个三角形最多将平面分成an个部分。
n=1时,a1=2;
n=2时,第二个三角形的每一条边与第一个三角形最多有2个交点,三条边与第一个三角形最多有2×3=6(个)交点。这6个交点将第二个三角形的周边分成了6段,这6段中的每一段都将原来的每一个部分分成2个部分,从而平面也增加了6个部分,即a2=2+2×3。
n=3时,第三个三角形与前面两个三角形最多有4×3=12(个)交点,从而平面也增加了12个部分,即:
a3=2+2×3+4×3。
??
一般地,第n个三角形与前面(n-1)个三角形最多有2(n-1)×3个交点,从而平面也增加2(n-1)×3个部分,故
an=2+2×3+4×3+?+2(n-1)×3
=2+[2+4+?+2(n-1)]×3
=2+3n(n-1)=3n2-3n+2。
特别地,当n=10时,a10=3×102+3×10+2=272,即10个三角形最多把平面分成272个部分。
七、整体法
解答数学题,有时要“化整为零”,使问题变得简单;有时反而要从整体上来考虑,从全局、从整体来研究问题。
例12 正方形ABCD的内部有1999个点,以正方形的4个顶点和内部的1999个点为顶点,将它剪成一些三角形。问:一共可以剪成多少个三角形?共需剪多少刀?
解:我们从整体来考虑,先计算所有三角形的内角和。汇聚在正方形内一点的诸角之和是360°,而正方形内角和也是360°,共有 360°×1999+360°,从而三角形的个数是
内容需要下载文档才能查看
由于每个三角形有三条边,而正方形纸原来的4条边当然不用剪;其余的边,由于是两个三角形的公共边,剪一刀出两条边,所以共剪的刀数是
内容需要下载文档才能查看
5
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- 2.13:湖南省中小学教师系列专业技术职称(职务)评审表
- 我的大学理财
- 看拼音写汉字(一)
- 第十一章 联立方程组模型Word
- 信息共享有关表格样式
- 汉字笔画名称Word
- 期中试卷分析答案
- 汉语拼音__幼小衔接Word
- 我的学习我做主:个人研修计划
- 集体备课计划安排表
- JLPT日本语能力考N2词汇(名词)整理归纳
- 2015年高中历史 7.20“百花齐放”“百家争鸣”课件 新人教版必修3Word
- 地形地势特征Word
- 钢结构识图Word
- 工程计量Word
- 半导体二极管及其应用习题解答(修改)答案
- 政治经济学导论Word
- 雁鸣湖镇童星午托部食品安全突发事件应急处置 领导组
- 化美启智 立德树人
- 英语演讲Word(低碳生活)
- 浙江大学毕业论文答辩Word动态模板
- 2015年高中历史 3.8古代中国的发明和发现课件 新人教版必修3Word
- 2.1:湖南省中小学教师系列专业技术职称(职务)申报人员诚信承诺书
- 人教版五年级数学上册第四单元第一课时《用字母表示数》Word课件
- 10群体心理Word
- 质量管理体系与措施
- 三字经
- 看拼音写汉字(三)
- 看拼音写汉字(四)
- 广州市同宝路8号、10号地块工程可行性研究报告-广州中撰咨询
网友关注视频
- 飞翔英语—冀教版(三起)英语三年级下册Lesson 2 Cats and Dogs
- 3月2日小学二年级数学下册(数一数)
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T3751175
- 人教版历史八年级下册第一课《中华人民共和国成立》
- 苏科版数学 八年级下册 第八章第二节 可能性的大小
- 沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
- 每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
- 外研版英语三起5年级下册(14版)Module3 Unit2
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
- 北师大版小学数学四年级下册第15课小数乘小数一
- 精品·同步课程 历史 八年级 上册 第15集 近代科学技术与思想文化
- 七年级英语下册 上海牛津版 Unit5
- 沪教版八年级下次数学练习册21.4(2)无理方程P19
- 冀教版小学数学二年级下册第二单元《余数和除数的关系》
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,辽宁省
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 4
- 冀教版小学数学二年级下册1
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
- 冀教版小学数学二年级下册第二单元《有余数除法的简单应用》
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T3763925
- 沪教版牛津小学英语(深圳用)五年级下册 Unit 1
- 外研版英语七年级下册module3 unit2第一课时
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 8
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126
- 三年级英语单词记忆下册(沪教版)第一二单元复习
- 8 随形想象_第一课时(二等奖)(沪教版二年级上册)_T3786594
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
- 人教版二年级下册数学
- 苏科版数学八年级下册9.2《中心对称和中心对称图形》
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理