六年级奥数第一册三单元.doc

雅博培训学校暑假五进六强化班数学讲义 第三单元 计数原理第一讲：枚举法（分类、树形图）一、内容概述1、枚举就是将要求计数的物体一一列举出来再进行总数的统计的方法。枚举无疑是最原始、最简单的计数方法，但是它同时也是计数最可靠的方法，也是发现规律、找到技巧的最佳方法。2、计数的关键在于既不重复、也不遗漏，枚举法也不例外。要做到这一点，关键是要在确定列举范围以后先按照一定的标准分类，再按一定的顺序进行列举。运用树形图帮助按顺序列举是解决这一问题的常用技巧。3、借用树形图列举是解决过程的方法，不是最终目的。因此，如果能够在列举过程中及时发现规律并加以应用和推广，将更有利于问题的尽快、尽简解决。二、枚举法的运用1、分类枚举例1 分子小于6而分母小于60的最简真分数共有多少个？解：最简真分数的条件（1）分子比分母小，（2）分子与分母互质。根据分类的原则，分的类别应该尽可能少，所以这里按分子进行分类枚举比较合理。当分子为1，有，共计59-2+1=58（个）；当分子为2，有，去掉可约分数共（个）；当分子为3，有，去掉可约分数共（个）；当分子为4，有，去掉可约分数共（个）；当分子为5，有，去掉可约分数共（个）； 用加法原理可得，共有最简真分数：58+29+38+28+44=197（个）例2 一个长方形被一条直线分为2个部分，那么8条直线最多可以将长方形分为多少个部分？如果是2002条呢？解：枚举观察，1条直线最多可以将长方形分为：1+1=2（个）部分；2条直线最多可以将长方形分为：1+1+2=4（个）部分；3条直线最多可以将长方形分为：1+1+2+3=7（个）部分；所以，8条直线最多可以将长方形分为：1+1+2+3+4+5+6+7+8=37（个）部分。2002条直线最多可以将长方形分为：1+1+2+3+2000+2001+2002=2005004（个）部分。2、树形图例3 某人在A、B、C三个城市游览，他今天在这个城市，明天就要到另一个城市。那么，他从A城出发，4天后仍然回到A城，共有多少种不同游览路线？解：这位游客的游览路线可以用如下的树形图来表示， 所以他共有6种不同的游览路线。例4 甲、乙两人进行象棋比赛，双方约定先胜四局者最终胜。现在三局过后，甲为二胜一负。那么要决出最后胜负为止，一共有多少种不同的可能情形？其中甲胜的不同情形共有多少种？（假设没有和局）解：比赛要决出最后胜负，至少还要赛2场，至多还要赛5场，按进行比赛的场数分类，再比赛2场可以决出胜负，两场都是甲胜利，1种；再比赛3场可以决出胜负，前两场甲一负一胜或一胜一负，2种；再比赛4场可以决出胜负，前三场甲两负一胜，3种；四场都是乙胜，1种；再比赛5场可以决出胜负，前四场甲三负一胜，4种；前四场乙三胜一负，4种； 一共有不同的可能情形：1+2+3+1+4+4=15（种）其中甲胜利的情形共有：1+2+3+4=10（种）3、标数枚举（求最短路径）例5 如图，要从A点走到B点，要求每一步都是向右、向上或者向斜上方，那么共有多少种不同走法？解：根据题意，每到一个节点就会有不同的路线，那么对每个节点的路线条数进行标数，则可得到节点B的路线条数，如图所示， 所以，共有12种不同的走法。例6 如下各图，由A点沿最短路线到达B点各有多少种不同走法？解：与例题5一样，对每个节点的路线进行标数，则可得到节点B的路线条数，如图所示，所以，图（1）中，到达B点有20种不同路线，图（2）中，到达B点有34种不同路线。 第二讲：加法、乘法原理（一）一、内容概述1、加法原理和乘法原理来源于枚举法中分类和有序枚举，是枚举中对于规律的一种概括。加法原理：完成一件事情，有k类不同的方法，而第一类方法中有m1种不同的做法，第二类方法中有m2种不同的做法，那么完成这一件事情的方法总数为：m1+m2+mk乘法原理：完成一件事情，有k个必经的步骤，而第一个步骤中有m1种不同的做法，第二个步骤中有m2种不同的做法，。那么完成这一件事情的方法总数为：m1m2mk2、可以用下图表示加法原理和乘法原理：二、加法原理的运用例1 长沙去广州，可乘火车，也可以乘汽车，还可以乘飞机。如果某天中，长沙去广州有5班火车、4班汽车和3班飞机，那么这一天中由长沙去广州可以有多少种不同的走法？分析与解：目的：长沙去广州；途径：乘坐三种不同的交通工具；结果：乘坐任何一种交通工具都可以到达目的地，整个事件结束。所以，利用加法原理，由长沙去广州可以有5+4+3=12（种）不同的走法。例2 有5分币，2分币，1分币各若干，现要组成1角钱，共有多少种不同的组合方式？分析与解：按币值较大的进行分类枚举，这样分的类别比较少，只有三种，5分币取两张，另两种币值的没得选择，1种组合方式；5分币取一张，再考虑2分币，可以取1张，2张，或者不取，3种组合方式；5分币不取，再考虑2分币，可以取1，2，3，4，5张，或者不取，6种组合方式。利用加法原理，共有1+3+6=10种不同的组合方式。例3 用10把钥匙开10把锁，但是不知道哪把钥匙开哪把锁，那么最多是多少次就能够将所有的钥匙和所有的锁一一配好？解：第一片钥匙要找到适合它的锁，至多要试9次；第二片钥匙要找到适合它的锁，至多要试8次；第三片钥匙要找到适合它的锁，至多要试7次；所以将所有的钥匙和所有的锁一一配好最多需要9+8+7+6+5+4+3+2+1=45（次）三、乘法原理的运用例4 书架上层放着6本不同的数学书，下层放有5本不同的语文书，从中任取数学书与语文书各一本。有多少种不同的取法？分析与解：目的：取数学书与语文书各一本 途径：上层取一本，下层取一本，分步进行。 所以，根据乘法原理，共有65=30种不同的取法。例5由数字0、1、3、5、7可以组成多少个没有重复数字的四位数？能被5整除的四位数（没有重复数字）有多少个？解：（1）没有重复数字的四位数，先考虑特殊位置，千位数字，只有1，3，5，7四种选择；百位数字，此时千位数字已经选定，五个数字已经用去1个，则百位数字只能在剩下的4个数字中选择；依次类推，十位数字有3种选择，个位数字有2种选择，根据乘法原理，这样没有重复数字的四位数有4432=96（个）（2）被5整除没有重复数字的四位数，此时个位数字更为特殊，它只能是0或者5，所以分类讨论，当个位数字是0时，千位有4种，百位有3种，十位有2种，共计1432=24（个）当个位数字是5时，千位有3种，百位有3种，十位有2种，共计1332=18（个）所以被5整除没有重复数字的四位数有24+18=42（个）例6在下图中共有16个方格，现在要将A、B、C、D四枚棋子放到方格中，而且要求每一行、每一列都只能出现一枚棋子，那么一共有多少种不同的放法？解：分步将A、B、C、D四枚棋子放到方格中，A放入方格中有44=16种不同的放法；B放入方格中有33=9种不同的放法；C放入方格中有22=4种不同的放法；D放入方格中有11=1种不同的放法。一共有不同的放法：16941=576（种）例7红日小学的乒乓球代表队由10名男队员和8名女队员组成：（1）在乡乒乓球对抗赛上，红日小学要从这些队员中挑选 1名男队员，1名女队员配成一组去参加男女混合双打比赛，问有多少种不同的搭配方式？（2）红日小学荣获乡乒乓球比赛团体总分第一，校领导要从男队员或女队员中任选一人去登台领奖，问有多少种不同的选法？解：分步选人，从男队员中选有10种不同选择；从女队员中选有8种不同选择。男女混合双打比赛，有不同的搭配方式108=80（种）利用加法原理可知，从男、女队员中任选一人，有不同的选法：10+8=18（种）第三讲：加法、乘法原理（二）一、知识要点：1、加法原理和乘法原理的区别在于是将所完成的“事情”进行分类还是分步。但是无论是进行分类还是分步，都必须做到几个类别或几个步骤相互独立，互不影响。2、生活中进行加法原理与乘法原理的实际应用时，常常应该先考虑分类，再考虑在每一类中进行分步。但要注意：有时并不能直接发现分类，而是在按照所分的步骤前进几步以后才发现某一步中有几类情形，这时要找到分类的标准重来先分类、再分步进行计数。二、加法与乘法原理的综合运用例1 如图是连接城市A、B、C的公路网，汽车从A点出发经过B到C选择不绕远路的不同路线共有多少种？解：利用标数枚举可知，从A到B有6种不同走法，从B到C也有6种不同走法，所以根据乘法原理，汽车从A点出发经过B到C选择不绕远路的不同路线共有66=36（种）例2 在1-500的自然数中，不含有数字“4”的数共有多少个？解：考虑0499，为了统一，把一位数、两位数都看作是三位数，如0看作三位数是000，12看作三位数是012，如此，这些三位数的个位数字有0，1，2，3，5，6，7，8，9共计9种选择；十位数字有0，1，2，3，5，6，7，8，9共计9种选择；百位数字有0，1，2，3共计4种选择；因此在0499中，不含有数字“4”的数共有499=324（个）在1-500的自然数中，不含有数字“4”的数共有324+1-1=324（个）例3 用4种颜色染下图中编号为1，2，3，4的4个矩形，使任二相邻的矩形所染的颜色都不相同的染色方法有多少种？解：2、3同色有：4313=36（种） 2、3不同色有：4322=48（种）染色方法有：36+48=84（种）例4 用红、黄、绿三面旗子挂在旗杆上，可以挂一面、两面、三面，不同的顺序，算不同的挂法。问有多少种不同的挂法？解：按挂旗子的面数进行分类枚举， 只挂一面旗子，有红、黄、绿三种不同的选择； 挂两面旗子，有32=6（种）不同的挂法； 挂三面旗子，有321=6（种）不同的挂法。 所以一共有3+6+6=15（种）不同的挂法。例5 有10级台阶，小明每步只能跨一级或者二级，那么小明要从底层上楼到第十层有多少种不同的走法？解：跨到第一级，只有1种走法； 跨到第二级，可以从底层跨上来，也可以从第一级跨上来，有1+1=2（种）不同走法；跨到第三级，可以从第一级上来，也可以从第二级上来，即有1+2=3（种）不同走法； 跨到第四级，可以从第二级上来，也可以从第三级上来，即有2+3=5（种）不同走法； 即跨到第几级，都可以从它前面的两级走一步上来，走法也就是前两级走法的叠加。所以跨到第十级，可以从第八级上来，也可以从第九级上来，有34+55=89（种）不同走法。例6 育才小学有语文、数学、音乐、图画、体育5个课外活动小组，每个学生必须参加且只能参加其中任何一个小组，冬冬和明明不在同一课外活动小组的情况有多少种？解：冬冬选课外活动小组有5种不同的选择，明明就只能在剩下的4个活动小组中选一个，根据乘法原理，冬冬和明明不在同一课外活动小组的情况有54=20（种）例7 如下图，从A处穿过房间到达B处，如果要求只能够从小号房间走向大号房间，而且相邻的房间都有门相通，那么一共有多少种不同走法？解：此题类似于例题5，首先，到1号房间，只能从A进来，1种走法；到2号房间，可以从1号房间过来，也可以直接从A进来，1+1=2（种）走法；之后每到其中的一个房间，都是前面两个房间走法的叠加，如到第3号房间，就有1+2=3（种）走法；到第4号房间，就有2+3=5（种）走法；到达B处，共有21+34=55（种）不同走法。阅读专题：容斥原理一、内容概述1、容斥原理（又称包含与排除）是计数中的一个基本原理，也是一个常用的计数方法：在计数过程中，常常先将所计数的对象分为几个部分，在对所有的部分分别计数后再进行相加，然后减去重复计数的那些部分。2、应用容斥原理进行实际计数时，为了能够清楚直观地看到计数的各个部分以及所有重复的那些部分，常常通过作出“韦恩图”相交的圆圈集合覆盖图予以展示。（如下图）从图示可以看出：要计数第一、二、三部分一起覆盖面的大小，一方面可以将图分为7个互不相交的部分直接相加；另一方面也可以先将一、二、三部分相加，再减去重复的部分。想一想：怎样减去？3、容斥原理特别适用于分类不独立的计数。二、容斥原理一的运用，这一公式可计算出两个集合圈的有关问题。例1 四一班的全体同学都参加了音乐、美术这样两个课外活动小组。其中参加音乐组的有29人，参加美术组的有32人，而两个组都参加的同学有12人。那么四一班一共有多少名同学？解：在两个圆的韦恩图中，音乐组的那个圆有29人，美术组的那个圆有32人， 两个组都参加的同学的两圆所重叠的部分有12人， 四一班一共有学生：29+3212=49（人）例2 在1-50的自然数中，是6的倍数或者9的倍数的数一共有多少个？解：在1-50的自然数中是6的倍数的数有506=8（个）， 是9的倍数的数有509=5（个），是18的倍数的数有5018=2（个） 是6的倍数或者9的倍数的数一共有：8+52=11（人）三、容斥原理二的运用，这一公式可计算出三个集合圈的有关问题。例3 六年级的160名学生参加期末考试，其中：数学得满分的有58人，语文得满分的有53人，外语得满分的有59人；而语文、数学都得满分的有17人，数学、外语都得满分的有22人，语文、外语都得满分的有20人；语文、数学、外语都得满分的有10人。那么六年级学生中语、数、外一门满分都没得的有多少人？解：首先根据容斥原理二，求出至少有一门得满分的人数， 58+53+59-17-22-20+10=121（人）那么在全年级中，剩下的人数便是没有一门的满分的人数： 160-121=39（人）例4 在1-500的自然数中，既不能被2整除、又不能被3整除、且不能被5整除的数一共有多少个？解：在1-500的自然数中，能被2整除的有5002=250（个）；能被3整除的有5003=166（个）；能被5整除的有5005=100（个）； 能被2、3最小公倍数6整除的有5006=83（个）； 能被2、5最小公倍数10整除的有50010=50（个）；能被3、5最小公倍数15整除的有50015=33（个）；能被2、3、5最小公倍数30整除的有50030=16（个）；在1-500的自然数中，能被2或3或5整除的数有：250+166+100-83-50-33+16=366（个）所以既不能被2整除、又不能被3整除、且不能被5整除的数一共有500-366=134（个）四、图像法不是利用容斥原理的公式计算，而是根据题意画图，并借助图形帮助分析，逐个地计算出各个部分，从而解答问题。例5 某班有学生48人，其中21人参加数学竞赛，13人参加作文竞赛，有7人既参