名校真题精讲(共7讲)_第06讲_计数与组合专题-学生版(13页).doc

-名校真题精讲(共7讲)_第06讲_计数与组合专题-学生版-第 13 页第6讲 计数与组合专题一、 计数问题1、枚举法枚举法就是把所有可能得情况一一列举出来，然后数一下总共有几种情况2、加乘原理（1）加法原理分类如果完成一件事有几类方式，在每一类方式中又有不同的方法，那么把每类的方法数相加就得到所有的方法数（2）乘法原理分步如果完成一件事有几个步骤，在每一个步骤中又有不同的方法，那么把每步的方法数相乘就得到所有的方法数3、排列组合（1）排列从m个不同元素中取出n个（），并按照一定的顺序排成一列，其方法数叫做从m个不同元素中取出n个的排列数，记作.其计算方法为：即从m开始递减地连乘n个数(2)组合从m个不同元素中取出n个（）组成一组（不计顺序），其方法数叫做从m个不同元素中取出n个不同的组合数，记作.其计算方法为：4、分类法与排除法（1）分类法：分来法解决问题的基本思想是通过分类拆解把一个复杂问题转化成几个相对简单的小问题来解决（2）排除法：当题目中满足要求的情况较多，分类法不好解决时，可以尝试用排除法，把不符合要求的情况去掉，剩下的就是符合的5、容斥原理（1）理解简单容斥原理（两个之间的重叠）与复杂容斥原理（三个之间的重叠）（2）用文氏图帮助解题6、递推方法（1）上楼梯模型（2）传球法列表写出每一步中具体的方法数（3）几何图形分平面增量分析7、插板法用于求解“把m个相同的球放到n个不同的盒子中”这类问题（1）注意：球必须是相同的，盒子必须是不同的（2）如果要求每个盒子至少一个球，那么方法数为（把n-1个板插到m-1个空隙中）（3）如果要求每个盒子可以为空，那么方法数为（先借n个球，然后按照每个盒子至少1个去放，最后从每个盒子中拿出1个还回去）（4）方程的正整数解共组（把n个球放到3个盒子中，每个盒子至少1个）（5）方程的自然数解共组（把n个球放到3个盒子中，每个盒子可以为空）8、与旋转、翻转相关的计数这类问题要想清楚是否有重复，重复了多少一般求解时，要先固定一些对象，使其不能旋转或翻转二、 统筹规划1、安排工序问题2、最短路线或最短时间问题3、排队等候问题4、集合问题5、货物调度问题三、 游戏对策（1）必胜策略往往是考虑“如何让对方输”，即必胜方行动时如何进行一次适当操作，把必输状态留给对方（2）游戏对策中往往会利用对称性来解决问题，如桌子上放硬币问题（轮流在圆桌上放硬币，到谁放的时候放不下了他就输了先手方把第一个硬币用来占领圆桌中心点即可，之后后手方再怎么放，先手方都能在桌上找到一个对称的空位点可以放置硬币）四、 逻辑推理解答推理问题常用的方法有：排除法、假设法、反证法一般可以从以下几方面考虑：1. 选准突破口，分析时综合几个条件进行判断；2. 根据题中条件，在推理过程中，不断排除不可能的情况，从而得出要求的结论；3. 对可能出现的情况作出假设，然后再根据条件推理，如果得到的结论和条件不矛盾，说明假设正确；4. 遇到比较复杂的推理问题，可以借助图表进行分析常见题型：去伪存真题：有人说真话有人说假话，有人说真话；或每人说的一部分对，一部分错注意适当选择假设等方法帮助解题条件分析题：用列表或作图的方法，对条件进行归纳整理体育比赛类问题：要注意搞清比赛规则，特别是积分规则，对阵方式若是画对阵关系图，注意箭头表胜负，虚线表示平局例如：若是2分赛制，则获胜队2分，平局各1分，失败不得分，那么总得分为“”；而3分赛制时，获胜队得3分，平局各得1分，失败不得分那么此时总分为“”五、 抽屉原理1、最不利原则2、抽屉原理六、 最值问题常用结论：（1）两数和一定，差越小，积越大（2）当几个数和一定是，越接近乘积越大（3）两点之间线段最短（4）在周长一定的封闭图形中，圆的面积最大；在面积一定的封闭图形中，圆的周长最小七、 构造论证1、构造往往用于说明“能”，即给出可能情况；论证往往用于说明“否”，即为什么不行2、常见题型：（1）构造或论证：这类题目中通常会以“能否”等词汇发问解答时，如果是“能”，就要构造出可行情况；如果是答“不能”，要论证为什么（2）构造与论证：常见于求最值的问题，以求最大值问题，得出最大值后要先论证不能得更大的值了，然后构造最大值对应的可行情况，说明这个最大值可以达到一、枚举法例1. 在所有三位数中，各位数字之和不超过4的共有_个二、加乘原理与排列组合例2. 将1、2、3、4、5这五个数字填入下面的五个方格中，使得阴影方格中填入的数大于相邻方格中的数，共有_种填法例3. 用0、1、2、3、4这五个数字能组成_个没有重复数字的四位偶数例4. 从19选出7个数字分别填入图中7个圆圈中，使得每条线段两端点处所填的数，上面比下面的大，那么符合要求的共_种三、容斥原理例5. 如图，数一数，图中共有多少个长方体？四、概率初步例6. 某军官参加射击比赛，他的射击命中率是80%那么他连打3枪，恰好有2枪命中的概率是_例7. 甲、乙两人玩掷硬币，出现正面甲得1分，反面乙得1分先得10分者为胜比赛进行一段时间后，甲得9分，乙得6分，那么甲获胜概率是_五、递推计数例8. 在一个平面上画3个三角形、1个圆、1条直线，最多可以把平面分成_个部分例9. 在世界杯的一场小组赛中，巴西队以7:5击败南非队，如果巴西队在比赛中从未落后过，那么这场比赛共有_种不同的进球顺序六、对应计数例10. （1）中关村一小六年级A班的30名同学投票选举优秀少先队员，投票采用不记名方式，每人只能投1票且不能投弃权票（谁都不选）如果候选人共3人，那么投票共_种不同的可能（2）如果这30名学生可以投弃权票，那么投票结果共_种不同的可能七、与翻转、旋转有关的计数问题例11. 用7种颜色为一个正方体的6个面染色，要求每个面只能用1种颜色，且6个面的颜色互不相同那么共有_种不同的染色方式八、统筹规划例12. 北京、上海、杭州三地同时研制成了大型电子计算机若干台，除本地应用外，北京可以支援外地10台，上海可以支援外地4台，杭州可以支援外地6台现在决定给武汉6台，重庆8台，深圳6台若每台计算机的运费如下表，表中运费单位是“百元”上海、北京和杭州制造的机器完全相同，应该怎样调运，才能使总的运费最省？最省的运费是_万元终点起 点 武汉重庆深圳北京7912上海879杭州6108九、游戏对策例13. 2010根火柴，甲、乙轮流取，规定每次只可以取1、3、4根如果以取完火柴的人为胜，甲先取，那么谁有必胜策略？策略是什么？十、逻辑推理例14. 老师在3个盒子里各放了一个彩色球，让小明、小亮、小强、小佳四人猜一下各个盒子里放的是什么颜色的球小明说：“1号盒里的是黄球，2号盒里的是黑球，3号盒里的是红球”小亮说：“1号盒里的是橙球，2号盒里的是黑球，3号盒里的是绿球”小强说：“1号盒里的是紫球，2号盒里的是黄球，3号盒里的是蓝球”小佳说：“1号盒里的是橙球，2号盒里的是绿球，3号盒里的是紫球”老师说：“你们中有一人恰好猜对了两个，其余三人每人猜对一个”那么第三个箱子中放的是_球例15. 在一列国际列车上，有A、B、C、D四位不同国籍的旅客，他们分别穿蓝、黑、灰、褐色的大衣，每边两个人面对面地坐在同一张桌子上已知：（1）英国人坐B先生左侧；（2）A先生穿褐色大衣；（3）穿黑色大衣的坐在德国人右侧；（4）D先生的对面坐着美国旅客；（5）俄国旅客穿着灰色大衣那么A、B、C、D分别是哪国人？分别穿什么颜色的衣服？例16. 5支球队进行单循环比赛，每两队之间比一场，获胜者得3分，负者0分，平手各得1分最后5支球队积分各不相同，第三名得了7分，并且和第一名打平请问：这5支球队的得分从高到低依次是多少？十一、抽屉原理例17. 有一个不透明的魔法口袋，里面装有大小、形状完全相同的小球，分为红、黄、蓝、白、黑五种颜色，每种颜色的小球都有足够多个n个人在口袋里取球，每人随意取3个，无论怎么取，都一定有5个人取到的球种类完全相同，那么n至少是_十二、最值问题例18. 将1、2、3、4、5、6分别填在正方体的6个表面上，计算具有公共棱的两个面上的数的乘积，这样的乘积共有12个，这12个乘积的和最大是_十三、构造论证例19. 把图中的圆圈任意涂上红色或蓝色问：能否使得每一条直线上的红圈个数都是奇数？ 例20. 有3堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子，或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆开始时，第一堆有1989块石子，第二堆有989块石子，第三堆有89块石子问能否做到：(1)某2堆石子全部取光？(2)3堆中的所有石子都被取走？作业1. 在所有的三位数中，能够被9整除，而且三个数字恰好能构成等差数列（可以改变顺序，如567、756）的共有_个作业2. 在40007000内有_个没有重复数字的5的倍数作业3. 有甲、乙、丙、丁四人过河，河上有一条小船，每次只能坐两个人，这样每次就必须有一人把船划回来接剩下的人那么四人过河有_方式作业4. 如图，图中只含一个的长方形有_个？作业5. 一次吃自助餐，有10道菜，每人有4个盘子可以选菜，要求每个盘子只能装1种菜，但是可以重复选菜（比如某道菜很好吃，我可以把2个盘子都装这1种菜），那么共有_种选菜方案作业6. （第六届高思杯 六年级，参加了高思杯但是当时没做出来的同学，看看自己现在是否会做了）正方体的八个顶点分别标记为A、B、C、D、E、F、G、H现在用四种颜色给顶点染色，要求有棱相连的两个顶点的颜色不同，一共有_不同的染色方法（旋转或翻转后相同算不同的染法）作业7. 把23表示成若干个互不相同的自然数之和，那么这些自然数的乘积最大是_作业8. ：一个新建的5层楼房的一个单元 每层有东西两套房；各层房号如图所示，现已有赵、钱、孙、李、周五个人入住一天他们在社区花园里聊天：赵说：“我家是第3个入住的，第1个入住的就住我对门”钱说：“只有我一家住在最高层”孙说：“我家入住时，我家的同侧的上一层和下一层都已经有人入住了”李说：“我家是五家中最后一个入住的，我家楼下那层全空着”周说：“我家住在106号，104号空着，108号也空着”他们说的就是真话，设第1、2、3、4、5家入住的房号的个位数字依次为A、B、C、D、E，那么五位数_ 作业9. 六个足球队进行单循环比赛，每两队都要赛一场如果踢平，每队各得1分，否则胜队得3分，负队得0分现在比赛已进行了四轮(每队都已与4个队比赛过)，各队4场得分之和互不相同已知总得分居第三位的队共得7分，并且有4场球赛踢成平局，那么总得分居第五位的队最多可得 分，最少可得 分作业10. 在黑板上写上、，按下列规定进行“操怍”：每次擦去其中的任意两个数和，然后写上它们的差(大数减小数)，直到黑板上剩下一个数为止问黑板上剩下的数是奇数还是偶数？为什么？