高中数学竞赛教案讲义(18)组合
- 格式:doc
- 大小:85.00 KB
- 文档页数:3
高中数学组合的教案
目标:学生能够掌握组合的基本概念,能够解决与组合相关的问题。
教学重点:组合的定义、组合的计算公式、应用组合解决问题。
教学难点:组合问题的实际应用。
教学过程:
一、导入(5分钟)
引导学生回顾排列的概念,并让他们思考排列和组合之间的区别。
二、讲解(15分钟)
1. 讲解组合的定义和性质;
2. 讲解组合的计算公式,如C(n, k) = n! / (k!(n-k)!).
三、练习(20分钟)
1. 让学生完成几道简单的组合计算题;
2. 让学生分组讨论并解决一些应用组合的问题,如赛马比赛中的排名问题。
四、拓展(10分钟)
让学生尝试解决一些较复杂的组合问题,如鸽巢原理等。
五、总结(5分钟)
对本节课的内容进行总结,强调组合在数学中的重要性和应用。
六、作业(5分钟)
布置作业:完成指定的练习题,并思考如何应用组合解决实际问题。
教学反思:在教学过程中要引导学生主动思考,注重实际问题的应用,帮助学生更好地理解组合的概念和方法。
1.2.2组合课标要求:知识与技能:理解组合的意义,能写出一些简单问题的所有组合。
明确组合与排列的联系与区别,能判断一个问题是排列问题还是组合问题。
过程与方法:了解组合数的意义,理解排列数m n A 与组合数之间的联系,掌握组合数公式,能运用组合数公式进行计算。
情感、态度与价值观:能运用组合要领分析简单的实际问题,提高分析问题的能力。
教学重点:组合的概念和组合数公式教学难点:组合的概念和组合数公式授课类型:新授课课时安排:2课时教 具:多媒体、实物投影仪内容分析:排列与组合都是研究从一些不同元素中任取元素,或排成一排或并成一组,并求有多少种不同方法的问题.排列与组合的区别在于问题是否与顺序有关.与顺序有关的是排列问题,与顺序无关是组合问题,顺序对排列、组合问题的求解特别重要.排列与组合的区别,从定义上来说是简单的,但在具体求解过程中学生往往感到困惑,分不清到底与顺序有无关系.指导学生根据生活经验和问题的内涵领悟其中体现出来的顺序.教的秘诀在于度,学的真谛在于悟,只有学生真正理解了,才能举一反三、融会贯通.能列举出某种方法时,让学生通过交换元素位置的办法加以鉴别.学生易于辨别组合、全排列问题,而排列问题就是先组合后全排列.在求解排列、组合问题时,可引导学生找出两定义的关系后,按以下两步思考:首先要考虑如何选出符合题意要求的元素来,选出元素后再去考虑是否要对元素进行排队,即第一步仅从组合的角度考虑,第二步则考虑元素是否需全排列,如果不需要,是组合问题;否则是排列问题.排列、组合问题大都来源于同学们生活和学习中所熟悉的情景,解题思路通常是依据具体做事的过程,用数学的原理和语言加以表述.也可以说解排列、组合题就是从生活经验、知识经验、具体情景的出发,正确领会问题的实质,抽象出“按部就班”的处理问题的过程.据笔者观察,有些同学之所以学习中感到抽象,不知如何思考,并不是因为数学知识跟不上,而是因为平时做事、考虑问题就缺乏条理性,或解题思路是自己主观想象的做法(很可能是有悖于常理或常规的做法).要解决这个问题,需要师生一道在分析问题时要根据实际情况,怎么做事就怎么分析,若能借助适当的工具,模拟做事的过程,则更能说明问题.久而久之,学生的逻辑思维能力将会大大提高.教学过程:一、复习引入:1分类加法计数原理:做一件事情,完成它可以有n 类办法,在第一类办法中有1m 种不同的方法,在第二类办法中有2m 种不同的方法,……,在第n 类办法中有n m 种不同的方法那么完成这件事共有 12n N m m m =+++ 种不同的方法2.分步乘法计数原理:做一件事情,完成它需要分成n 个步骤,做第一步有1m 种不同m n C的方法,做第二步有2m 种不同的方法,……,做第n 步有n m 种不同的方法,那么完成这件事有12n N m m m =⨯⨯⨯ 种不同的方法3.排列的概念:从n 个不同元素中,任取m (m n ≤)个元素(这里的被取元素各不相同)按照一定的顺序.....排成一列,叫做从n 个不同元素中取出m 个元素的一个排列....4.排列数的定义:从n 个不同元素中,任取m (m n ≤)个元素的所有排列的个数叫做从n 个元素中取出m 元素的排列数,用符号m n A 表示5.排列数公式:(1)(2)(1)m n A n n n n m =---+ (,,m n N m n *∈≤)6阶乘:!n 表示正整数1到n 的连乘积,叫做n 的阶乘规定0!1=.7.排列数的另一个计算公式:m n A =!()!n n m - 8.提出问题:示例1:从甲、乙、丙3名同学中选出2名去参加某天的一项活动,其中1名同学参加上午的活动,1名同学参加下午的活动,有多少种不同的选法?示例2:从甲、乙、丙3名同学中选出2名去参加一项活动,有多少种不同的选法? 引导观察:示例1中不但要求选出2名同学,而且还要按照一定的顺序“排列”,而示例2只要求选出2名同学,是与顺序无关的引出课题:组合... 二、讲解新课:1组合的概念:一般地,从n 个不同元素中取出m ()m n ≤个元素并成一组,叫做从n 个不同元素中取出m 个元素的一个组合说明:⑴不同元素;⑵“只取不排”——无序性;⑶相同组合:元素相同例1.判断下列问题是组合还是排列(1)在北京、上海、广州三个民航站之间的直达航线上,有多少种不同的飞机票?有多少种不同的飞机票价?(2)高中部11个班进行篮球单循环比赛,需要进行多少场比赛?(3)从全班23人中选出3人分别担任班长、副班长、学习委员三个职务,有多少种不同的选法?选出三人参加某项劳动,有多少种不同的选法?(4)10个人互相通信一次,共写了多少封信?(5)10个人互通电话一次,共多少个电话?问题:(1)1、2、3和3、1、2是相同的组合吗?(2)什么样的两个组合就叫相同的组合 2.组合数的概念:从n 个不同元素中取出m ()m n ≤个元素的所有组合的个数,叫做从n 个不同元素中取出m 个元素的组合数....用符号mn C 表示. 3.组合数公式的推导:(1)从4个不同元素,,,a b c d 中取出3个元素的组合数34C 是多少呢?启发:由于排列是先组合再排列.........,而从4个不同元素中取出3个元素的排列数34A 可以求得,故我们可以考察一下34C 和34A 的关系,如下:组 合 排列dcbcdb bdc dbc cbd bcd bcd dca cda adc dac cad acd acd dba bda adb dab bad abd abd cba bca acb cab bac abc abc ,,,,,,,,,,,,,,,,,,,,→→→→ 由此可知,每一个组合都对应着6个不同的排列,因此,求从4个不同元素中取出3个元素的排列数34A ,可以分如下两步:① 考虑从4个不同元素中取出3个元素的组合,共有34C 个;② 对每一个组合的3个不同元素进行全排列,各有33A 种方法.由分步计数原理得:34A =⋅34C 33A ,所以,333434A A C =. (2)推广:一般地,求从n 个不同元素中取出m 个元素的排列数m n A ,可以分如下两步:① 先求从n 个不同元素中取出m 个元素的组合数m n C ;② 求每一个组合中m 个元素全排列数m m A ,根据分步计数原理得:m n A =m n C m mA ⋅. (3)组合数的公式:(1)(2)(1)!m mn nm m A n n n n m C A m ---+== 或)!(!!m n m n C m n -=,,(n m N m n ≤∈*且 规定: 01n C =.三、讲解范例:例2.用计算器计算710C .解:由计算器可得例3.计算:(1)47C ; (2)710C ; (1)解: 4776544!C ⨯⨯⨯==35; (2)解法1:710109876547!C ⨯⨯⨯⨯⨯⨯==120.解法2:71010!10987!3!3!C ⨯⨯===120. 例4.求证:11+⋅-+=m n m n C m n m C . 证明:∵)!(!!m n m n C m n -= 111!(1)!(1)!m n m m n C n m n m m n m +++⋅=⋅--+-- =1!(1)!()(1)!m n m n m n m +⋅+--- =!!()!n m n m - ∴11+⋅-+=m n m n C mn m C 例5.设,+∈N x 求321132-+--+x x x x C C 的值解:由题意可得:⎩⎨⎧-≥+-≥-321132x x x x ,解得24x ≤≤, ∵x N +∈, ∴2x =或3x =或4x =,当2x =时原式值为7;当3x =时原式值为7;当4x =时原式值为11.∴所求值为4或7或11.例6. 一位教练的足球队共有 17 名初级学员,他们中以前没有一人参加过比赛.按照足球比赛规则,比赛时一个足球队的上场队员是11人.问:(l)这位教练从这 17 名学员中可以形成多少种学员上场方案?(2)如果在选出11名上场队员时,还要确定其中的守门员,那么教练员有多少种方式做这件事情?分析:对于(1),根据题意,17名学员没有角色差异,地位完全一样,因此这是一个从 17 个不同元素中选出11个元素的组合问题;对于( 2 ) ,守门员的位置是特殊的,其余上场学员的地位没有差异,因此这是一个分步完成的组合问题.解: (1)由于上场学员没有角色差异,所以可以形成的学员上场方案有 C }手= 12 376 (种) .(2)教练员可以分两步完成这件事情:第1步,从17名学员中选出 n 人组成上场小组,共有1117C 种选法;第2步,从选出的 n 人中选出 1 名守门员,共有111C 种选法.所以教练员做这件事情的方法数有1111711C C ⨯=136136(种).例7.(1)平面内有10 个点,以其中每2 个点为端点的线段共有多少条?(2)平面内有 10 个点,以其中每 2 个点为端点的有向线段共有多少条?解:(1)以平面内 10 个点中每 2 个点为端点的线段的条数,就是从10个不同的元素中取出2个元素的组合数,即线段共有 2101094512C ⨯==⨯(条). (2)由于有向线段的两个端点中一个是起点、另一个是终点,以平面内10个点中每 2 个点为端点的有向线段的条数,就是从10个不同元素中取出2个元素的排列数,即有向线段共有21010990A =⨯=(条).例8.在 100 件产品中,有 98 件合格品,2 件次品.从这 100 件产品中任意抽出 3 件 .(1)有多少种不同的抽法?(2)抽出的 3 件中恰好有 1 件是次品的抽法有多少种?(3)抽出的 3 件中至少有 1 件是次品的抽法有多少种?解:(1)所求的不同抽法的种数,就是从100件产品中取出3件的组合数,所以共有 31001009998123C ⨯⨯=⨯⨯= 161700 (种). (2)从2 件次品中抽出 1 件次品的抽法有12C 种,从 98 件合格品中抽出 2 件合格品的抽法有298C 种,因此抽出的 3 件中恰好有 1 件次品的抽法有12298C C ⋅=9506(种). (3)解法 1 从 100 件产品抽出的 3 件中至少有 1 件是次品,包括有1件次品和有 2件次品两种情况.在第(2)小题中已求得其中1件是次品的抽法有12298C C ⋅种,因此根据分类加法计数原理,抽出的3 件中至少有一件是次品的抽法有12298C C ⋅+21298C C ⋅=9 604 (种) .解法2 抽出的3 件产品中至少有 1 件是次品的抽法的种数,也就是从100件中抽出3 件的抽法种数减去3 件中都是合格品的抽法的种数,即3310098C C -=161 700-152 096 = 9 604 (种). 说明:“至少”“至多”的问题,通常用分类法或间接法求解。
高二数学竞赛班二试第六讲 组合问题班级 姓名一、知识要点:组合数学是一个既古老又年轻的离散数学分支,竞赛中的组合问题主要包括组合计数问题、组合极值问题、存在性问题、操作变换问题、组合几何问题以及图论中的问题,求解竞赛中的组合问题并不是需要复杂的数学知识,然而在趣味性命题的陈述下包含了高超的解题技巧,无论是从智力训练的角度,还是从竞赛准备的角度考虑,理解和钻研这些问题都是十分有意义的.在解决组合问题时,有时会用到以下几个原理.1、极端原理原理 1 设M 是自然数集的一个非空子集,则M 中必有最小数.原理 2 设M 是实数集的一个有限的非空子集,则M 中必有最小数.2、抽屉原理把5个苹果放到4个抽屉中,必然有一个抽屉中至少有2个苹果,这是抽屉原理的通俗解释。
一般地,我们将它表述为:把(mn +1)个物体放入n 个抽屉,其中必有一个抽屉中至少有(m +1)个物体。
使用抽屉原理解题,关键是构造抽屉。
一般说来,数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等,都可作为构造抽屉的依据。
第一抽屉原理 若将m 个小球放入n 个抽屉中,则必有一个抽屉 内至少有11+⎥⎦⎤⎢⎣⎡-n m 个小球.第二抽屉原理 若将m 个小球放入n 个抽屉中,则必有一个抽屉内至多有⎥⎦⎤⎢⎣⎡n m 个小球. 3、算两次原理所谓算两次原理(又称富比尼原理)就是对同一个量,如果用两种不同的方法去计算,所得的结果应相等. 二、经典例题例 1.(2008年山西省预赛试题)设M ={1,2,…,2008}是前2008个正整数组成的集合,A ={1a ,2a ,…30a }是M 的一个30元子集,已知A 中的元素两两互质,证明A 中至少一半元素是质数.分析 考查集合A 中的合数a ,设p 是a 的最小质因数,则p ≤a .又a ≤2008,于是p ≤45,再由A 中的元素两两互质,可以证明A 中16个元素中必有一个是质数,进而可以导出结论.证明 先证明:A 中16个元素中必有一个是质数.为此,任取16个元素,不妨设为1a ,2a ,…,16a ,若其中没有质数,则它们中至多一个为1,其余15个皆为合数.设1a ,2a ,…,15a 都是合数,则每个数皆可分解成至少两个质因数的乘积,若i p 是i a 的最小质因数,则i p ≤i a (i =1,2,…,15).由于A 中的数两两互质,则1p ,2p ,…,15p 互不相同,而将全体质数自小到大排列,第15个质数是47,所以,若1p 是1p ,2p ,…,15p 中的最大数,即有1p ≥47,于是1a ≥21p ≥247>2008,即1a ∉M ,矛盾!因此,1a ,2a ,…,15a 中必有质数,不妨设1a 为质数,今从集合A 中去掉1a ,在剩下的29个元素中,再次进行同样的讨论,可知其中的16个元素中也必有一个是质数,设为2a .如此下去,可以连续进行15次,每次都可从A 中取到一个新的质数, 因此A 中至少有15个质数.说明 本题利用极端原理,通过对合数的最小质因数的考查,获取集合A 中元素的 性质,进而完成了证明,这种方法也是数论中研究合数的一种重要策略.例 2.已知A 与B 是集合{1,2,3,…,100}的两个子集,满足:A 与B 的元素个数相同,且A ∩B 为空集,若n ∈A 时总有2n+2∈B ,则集合A ∪B 的元素个数最多为多少?分析 该问题是组合构造,由条件“A 与B 的元素个数相同且若n ∈A 时总有2n +2∈B ”知|A |=|B |,且2n +2≤100,从而可知A 中的元素不超过49个,为此需要进行分类考虑.解 首先证明|A ∪B |≤66,只需要证明|A |≤33,由分析知需要证明:若A 是{1,2,3,…,49}的任何一个34元子集,则必存在n ∈A ,使得2n+2∈A.证明如下:将{1,2,3,…,49}分成如下33个集合:{1,4},{3,8},{5,12},…,{23,48},共12个;{2,6},{10,22},{14,30},{18,38},共4个;{25},{27},{29},…,{49},共13个;{26},{34},{42},{46},共4个.若A 是{1,2,3,…,49}的任何一个34元的子集,则由抽屉原理可知上述33个集合中至少有一个2元集合中的两个数均属于A ,即存在n ∈A ,2n +2∈A .所以|A |≤33.事实上,如取A ={1,3,5,…,23,2,10,14,18,25,27,29,…,49,26,34,42,46},B ={2n +2|n ∈A },则A ,B 满足题中要求,且|A ∪B |=66.所以集合A ∪B 的元素个数最多为66.说明 将集合中的元素进行适当分会组,并结合抽屉原理使问题得以解决,这是解决类问题的常用手段.例 3. (2007年浙江省预赛试题)设M ={1,2,…,65},A M 为子集,若|A|=33,且存在x ,y ∈A ,x <y ,x | y ,则称A 为“好集”,求最大的a ∈M ,使含a 的任意33元子集为好集.分析 首先要准确理解“好集”的含义,搞清楚“好集”中元素的构成规律,再来分析a 的可能的取值.解 令P ={21 + i | i =1,2,…,44}— {2(21 + i )| i = 1,2,…,11},| p | = 33.显然对任意1≤i <j ≤44,不存在n ≥3,使得21+j = n (21 +i )成立,故P 是非好集. 因此a ≤21,下面证明:包含21的任意一个33元子集A 一定为好集.设A ={1a ,2a ,…,32a ,21}.若1,3,7,42,63中之一为集合A 的元素,显然A 为好集现考虑1,3,7,42,63都不属于集合A .构造集合:1A ={2,4,8,16,32,64},2A ={5,10,20,40},3A ={6,12,24,48},4A ={9,18,36},5A ={11,22,44},6A ={13,26,52},7A ={14,28,56},8A ={15,30,60},9A ={17,34},10A ={19,38},11A ={23,36},12A ={25,50},13A ={27,54},14A ={29,58},15A ={31,62},'A ={33,35,37,…,61,65},由上可见,1A ,2A ,…,15A 每个集合中两个元素都是倍数关系,考虑最不利的情况,即'A A ,也即'A 中16个元素全部选作A 的元素,A 中剩下16个元素必须从1A ,2A ,…,15A 这15个集合中选取,根据抽屉原理,至少有一个集合有两个元素被选,即集合A 中至少有两个元素存在倍数关系.综上所述,包含21的任意一个33 元子集A 一定为好集,即a 的最大值为21.说明 对于这一类型的集合问题,一般都需要通过适当的方式构造出符合某种要求的集合,抽屉原理是解决集合构造问题的常用工具.例4.(2008年甘肃省预赛试题)一个20行若干列的0、1数阵满足:各列互不相同且任意两列同一行都取1的行数不超过2.求当列数最多时,数阵中1的个数的最小值.分析 由题设,对于数阵中1的个数超过3的列,保留其中任意3个1,而将其余的都变成0,得到的新数阵仍然满足要求,于是可知当列数最多时,数阵中至多包含1的个数不超过3的所有的列.这样可得列数最大值,进而求得此时数阵中1的个数的最小值.解 对于满足条件的列数最大的一个数阵,如果这个数阵中某一列1的个数超过3个,那么就保留其中任意3个1,其余的都改变成0,这样就会得到一个列数相同并有仍然满足要求的一个新数阵,如果这个新数阵中还有1的个数超过3的列,则重复上述过程,最后可以得到一个列数最多,且每列中1的个数最多为3的满足要求的数列,它的列数最多为1+120C +220C +320C .另一方面,构造一个满足要求的数阵如下:它包括没有1的列以及所有互不相同的只有一个1的列,2个1的列和3个1的列,由上所说,可知这个数阵的列数是最多的,同时在满足要求的列数最多的所有数阵中所有数阵中,该数阵中的1是最少的,此数阵的列数为1+120C +220C +320C ,此数列中1的个数是120C +2202C +3203C =20+380+3420=3820说明 本题中求数阵的列数的最大值的方法叫做局部整法,它是解决最值问题的一种行之有效的方法,尤其是离散变量最值问题常常需要用到这种方法.例 5.(2008年浙江省预赛试题)将3k (k 为正整数)个石子分成五堆,如果通过每次从其中3堆中各取走一个石子,而最后取完,则称这样的分法是“和谐的”,试给出和谐分法的充分必要条件,并加以证明.分析从整体上看,就是从3k个石子中每次取3个,恰好k次取完,于是和谐的分法就是要求每堆石子的个数不超过k,再用数学归纳法证明,最多一堆石子的个数不超过k的分法是和谐的.解分析是和谐的充分必要条件是最多一堆石子的个数不超过k.下面设五堆石子的个数分别为a、b、c、d、e(其中a≥b≥c≥d≥e).“必要性”的证明:若分法是和谐的,则把a所对应的石子取完至少要取a次,这a次每次都要取走3个石子,如果a>k,则3a>3k,即把a所对应的一堆取完时,需取走的石子多于五堆石子的总数,矛盾,因此最多一堆石子的个数不能超过k.“充分性”的证明:(数学归纳法)(1)当k=1时,满足a≤k的分法只能是1、1、1、0、0.显然这样的分法是和谐的.(2)假设k≤n时,若a≤k的分法是和谐的.当k=n+1时,若a≤n+1,且分法a、b、c、d、e是不和谐的,则分法a-1、b-1、c-1、d、e也是不和谐的.由(2)及必要性的证明,可知max{a-1,b-1,c-1,d,e}>n.因为a≥b≥c≥d≥e,所以max{a-1,b-1,c-1,d,e}=max{a-1,d}>n.若a-1≥d,则有a-1>n.这与a≤n+1矛盾.若a-1<d,则有n<d≤c≤b≤a≤n+1,从而有a =b=c=d=n+1,于是有3(n+1)=a + b + c + d + e= 4 (n+1) + e,这是不可能的.因此,当a≤n+1时,分法a、b、c、d、e是和谐的说明本题充分性的证明采用的是数学归纳法,这是一种归纳构造,它是利用构造思想解决存在性问题的一种重要手段例 6.(1988年全国联赛试题)在坐标平面上是否存在一个含有无穷多条直线1l ,2l ,…,n l ,…的直线族,满足条件:(1)点(1,1)∈n l ,n =1,2,3,…;(2)1+n k = n a -n b ,其1+n k 中是1+n l 的斜率,n a 和n b 分别是n l 在x 轴和y 轴上的截距,1k 是1l 的斜率,n = 1,2,3,…;(3)1+n n k k ≥0,n = 1,2,3,…并证明你的结论分析 假设这样的直线族存在,先利用直线n l 的方程求出n a 与n b ,即可得到{n k }的递推关系,再结合条件(3)求解解 题中给出的是以点(1,1)为公共点的中心直线族,若这样的直线族存在,则n l 的方程为y -1 = ()1-x k n当y = 0 时,-1=()1-n n a k ,n a = 1-nk 1 当x = 0 时,n b -1= -n k ,n b = 1-n k因为n l 存在,所以n a 和n b 都存在,从而n k ≠0,n = 1,2,3,…,利用条件(2) 有1+n k = n a -n b = n k -nk 1 继续有 n k = 1-n k -11-n k …… 2k = 1k -11k 以上诸式相加得到1+n k = 1k -(11k + 21k + … + nk 1) ① 由n k ≠0及条件(3)得1+n n k k >0,故所有的i k (i = 1,2,3,…)同号,不妨设i k>0,则1+n k =n k - n k 1<n k ,即数列{n k }是正项递减数列,从而11+n k >n k 1,于是11k + 21k + … + n k 1>1k n 这样,由①式得1+n k <1k -1k n = 121k n k - ② 当n >21k 时,由②式推出1+n k <0.由假设n k >0,得1+n n k k <0,与己知矛盾同理可证,当n k <0 时,也导致矛盾所以,同时满足条件(1),(2),(3)的直线族不存在说明 本题是探索性质的存在性问题,解决问题时,常常需要先作出判断,明确解题方法,再求解,这对学生的能力提出了更高的要求例7.(2007年吉林省预赛试题)一个空间中的点组成的集合S满足性质:S中任意两点之间的距离互不相同,假设S中的点的坐标(x ,y ,z )都是整数,并且1≤ x ,y ,z ≤ n ,证明:集合S 的元素个数小于min {(n +2)·3n ,6n } 证明 记 | S | = t ,则对任意(,1,1,1z y x ),(,2,2,2z y x )∈S ,都有()221x x -+()221y y -+()221z z -≤3()21-n (因为满足1≤x ,y ,z ≤n 的整点之间的距离不超过(1,1,1)与(n ,n ,n )之间的距离)并且依题意,S 中任意两点之间的距离互不相同,故2t C ≤3()21-n , 得2t -t ≤ 6()21-n ,于是 t≤21+21()21241-+n <6n(最后一个不等式价于1+24()21-n <()2162-n ,展开后移项即可得到) 另一方面,对S 中的任意两点(,,,i i i z y x )、(,,,i i i z y x ),考虑集合{a ,b ,c }(允许出现重复元素),这里a = | j i x x -|,b =|j i y y -|,c = |j i z z -|,依题意,所得的{a ,b ,c }两两不同,且0 ≤ a ,b ,c ≤n -1,a 、b 、c 不全为0,于是,我们有2t C ≤12123-++n n n C C C ①故2t C <1232n n n C C C ++解得t <()()21314121++++n n n . 当n ≥3时,有t <()32n n +. 这只需证明 ()()21314121++++n n n ≤()32n n +, 等价于 ()()213141+++n n n ≤()22132⎥⎦⎤⎢⎣⎡-+n n , 展开后移项即可知此不等式在n ≥3时成立).于是,当n ≥3时,总有t ≤()⎭⎬⎫⎩⎨⎧+6,32min n n n ②而当n =1时,t =1;当n =2时,由①知t ≤3,这时②都成立,命题获证.说明:本题从两个不同的角度,分别得到了2t C 的上界,从而完成了证明.这种思想的实质是算两次原理.它是研究跟计算有关的组合问题的一种重要策略.例8.(2009年山西省预赛试题)有七种颜色的珍珠,共计14颗,其中每种颜色的珍珠各两颗;今把这珍珠分装于七个珠盒中,使得每个珠盒中各有一对不同颜色的珍珠.(1)证明:不论各盒中的珍珠怎样搭配,总可以将这七个珠盒分别放置于一个正七边形的七个顶点之上,使得七边形的任两个相邻顶点处所放置的盒中的四颗珍珠互不同色.(2)如将以上条件与待证结论中的“七”一律改为“五”,“14”改为“10”,则情况如何? 分析:本题的文字叙述难以找出一般规律,把文字语言首先转化为图论语言,再借助图的性质找出问题的解决思路.解:(1)用点v 1,v 2,…,v 7分别表示这七种颜色,如果一个i v 色的珍珠和一个j v 色的珍珠装在同一盒中(i ≠j ),则在点i v 与j v 间连一条边,这样就得到一个图G (点i v 与j v 之间有可能连出两条边),由于同一色的珍珠有两颗,每颗珍珠都需与一颗其他颜色的珍珠共盒,则图G的每点恰好发出两条边;从G的任一点A出发,沿一条边走到点B,再由B沿另一条边走到C,…,如此下去,最后必定回到出发点A(这是由于,途中经过的每个点P 都有两条边,若参沿一条边进入点P,则必沿另一条边可离开点P,而由点P不能再加到途中已经过的点,因为这种点所发出的两条边都已走过,因此只能到达新点或回到出发点,而新点终将逐渐耗尽,最后必定回到出发点A),这样就得到一个圈.去掉这个圈,若剩下还有点,依上述方法,又将得到新的圈,若称两点的的圈为“两边形”,则图G的结构只有如下四种情况:1°一个七边形2°一个五边形和一个两边形3°一个四边形和一个三角形4°一个三角形和两个两边形对于每种情况,我们都对相应的边作出适当编号,并将这些边所对应的珠盒放置于七边形的顶点之上,如图5所示.因此所证结论成立.(2)当14颗七以珍珠改为10颗五色珍珠后,结论不成立.例如,对于五色54321,,,,v v v v v ,我们若将10颗珍珠这样装盒:()211,v v e =,()322,v v e =,()133,v v e =,()544,v v e =,()545,v v e =,则无论怎样摆放于正五边形的顶点上,都不能满足条件(因为1e 、2e 、3e 中,任两盒都有同色的珠,无论怎样摆放于正五边形的顶点上,必有两盒相邻).第13讲 抽屉原理例1 从1,2,3,…,100这100个数中任意挑出51个数来,证明在这51个数中,一定:(1)有2个数互质;(2)有2个数的差为50;(3)有8个数,它们的最大公约数大于1。
2019-2020年高考数学竞赛组合教案讲义(18)一、方法与例题1.抽屉原理。
例1 设整数n≥4,a1,a2,…,a n是区间(0,2n)内n个不同的整数,证明:存在集合{a1,a2,…,a n}的一个子集,它的所有元素之和能被2n整除。
[证明] (1)若n{a1,a2,…,a n},则n个不同的数属于n-1个集合{1,2n-1},{2,2n-2},…,{n-1,n+1}。
由抽屉原理知其中必存在两个数a i,a j(i≠j)属于同一集合,从而a i+a j=2n被2n整除;(2)若n∈{a1,a2,…,a n},不妨设a n=n,从a1,a2,…,a n-1(n-1≥3)中任意取3个数a i, a j, a k(a i,<a j< a k),则a j-a i与a k-a i中至少有一个不被n整除,否则a k-a i=(a k-a j)+(a j-a i)≥2n,这与a k∈(0,2n)矛盾,故a1,a2,…,a n-1中必有两个数之差不被n整除;不妨设a1与a2之差(a2-a1>0)不被n整除,考虑n个数a1,a2,a1+a2,a1+a2+a3,…,a1+a2+…+a n-1。
ⅰ)若这n个数中有一个被n整除,设此数等于k n,若k为偶数,则结论成立;若k为奇数,则加上a n=n知结论成立。
ⅱ)若这n个数中没有一个被n整除,则它们除以n的余数只能取1,2,…,n-1这n-1个值,由抽屉原理知其中必有两个数除以n的余数相同,它们之差被n整除,而a2-a1不被n整除,故这个差必为a i, a j, a k-1中若干个数之和,同ⅰ)可知结论成立。
2 极端原理。
例2 在n×n的方格表的每个小方格内写有一个非负整数,并且在某一行和某一列的交叉点处如果写有0,那么该行与该列所填的所有数之和不小于n。
证明:表中所有数之和不小于。
[证明] 计算各行的和、各列的和,这2n个和中必有最小的,不妨设第m行的和最小,记和为k,则该行中至少有n-k个0,这n-k个0所在的各列的和都不小于n-k,从而这n-k 列的数的总和不小于(n-k)2,其余各列的数的总和不小于k2,从而表中所有数的总和不小于(n-k)2+k2≥3.不变量原理。
高中数学球体组合问题教案
课时安排:1课时
教学目标:
1. 熟练掌握球体组合问题的解题方法;
2. 能够灵活运用组合数学知识解决现实生活中的问题;
3. 培养学生分析和解决问题的能力。
教学内容:
球体组合问题的解题方法
教学步骤:
1. 引入新知识(5分钟)
通过展示一道球体组合问题,引导学生思考如何解决这个问题。
2. 理解概念(15分钟)
解释组合数学中的球体组合问题是指在一组球体中选择出若干个球体的组合方式。
讲解组合数学的基本概念和公式。
3. 练习与讨论(20分钟)
让学生通过练习题目,掌握球体组合问题的解题方法,并引导他们讨论解题思路。
4. 实践运用(15分钟)
给学生提供一些现实生活中的球体组合问题,让他们运用所学知识解决问题。
5. 总结与拓展(5分钟)
总结本节课所学的知识,并拓展到其他类型的组合问题。
教学工具:
投影仪、黑板、练习题目
作业布置:
布置相关练习题目作为课后作业,加深对球体组合问题的理解。
教学反思:
在教学中要注重引导学生思考问题的方法和逻辑,培养他们的解决问题的能力,并且要和现实生活结合起来,让学生感受到数学知识的实际应用。
高中数学竞赛教案讲义主题:高中数学竞赛备考一、课程目标:1. 提高学生数学逻辑思维能力和解题能力;2. 增强学生对数学知识的理解和应用能力;3. 培养学生团队合作意识和竞赛意识;4. 培养学生学习数学的兴趣和信心。
二、教学内容:1. 数论知识与解题方法;2. 代数知识与解题方法;3. 几何知识与解题方法;4. 概率与统计知识与解题方法。
三、教学重点:1. 突出数学问题解题的逻辑思维;2. 突出数学知识运用的方法;3. 突出解题过程中的技巧与技法。
四、课堂教学安排:第一节课:数论知识与解题方法1. 介绍数论基础知识;2. 讲解数论解题方法;3. 练习数论题目。
第二节课:代数知识与解题方法1. 复习代数基础知识;2. 讲解代数解题方法;3. 练习代数题目。
第三节课:几何知识与解题方法1. 复习几何基础知识;2. 讲解几何解题方法;3. 练习几何题目。
第四节课:概率与统计知识与解题方法1. 介绍概率与统计基础知识;2. 讲解概率与统计解题方法;3. 练习概率与统计题目。
五、课后作业:1. 每节课的课后习题;2. 复习本节课的知识点;3. 复习前几节课的知识点;4. 组织小组讨论解题方法。
六、教学评估:1. 每节课的课堂练习成绩;2. 期中考试成绩;3. 期末考试成绩;4. 学生综合表现与进步情况。
七、教学心得与总结:数学竞赛备考是一个长期的过程,需要坚持不懈和不断努力。
教师要引导学生找到解题的方法,培养学生的数学思维和解题能力。
同时,学生也要积极主动,多加练习,不断提高自己的数学水平。
希望通过我们的共同努力,可以在数学竞赛中获得好的成绩。
高中数学竞赛同步讲义——组合数学基础一、基础知识梳理1、集合覆盖、分类、拆分2、分类原理3、容斥原理4、加法原理5、极端原理6、抽屉原理7、平均量重叠原则8、面积的重叠原理一、基础题型例析1、抽屉原理在数学问题中有一类与“存在性”有关的问题,例如:(1)13个人中至少有两个人出生在相同月份;(2)某校400名学生中,一定存在两名学生,他们在同一天过生日;(3)2003个人任意分成200个小组,一定存在一组,其成员数不少于11;(4)把[0,1]内的全部有理数放到100个集合中,一定存在一个集合,它里面有无限多个有理数. 这类存在性问题中,“存在”的含义是“至少有一个”。
在解决这类问题时,只要求指明存在,一般并不需要指出哪一个,也不需要确定通过什么方式把这个存在的东西找出来。
这类问题相对来说涉及到的运算较少,依据的理论也不复杂,我们把这些理论称之为“抽屉原理”抽屉原理”最先是由19世纪的德国数学家迪里赫莱(Dirichlet)运用于解决数学问题的,所以又称“迪里赫莱原理”,也称“鸽巢原理”(一)抽屉原理的基本形式定理1、如果把n+1个元素分成n个集合,那么不管怎么分,都存在一个集合,其中至少有两个元素。
例1.(1978年广东省数学竞赛题)已知在边长为1的等边三角形内(包括边界)有任意五个点(图1)。
证明:至少有两个点之间的距离不大于1/2.例2 (第14届1M0试题)一个集合含有10个互不相同的两位数,试证明:这两个集合必有两个无公共元素的子集合,此两子集的各元素之和相等.例3.从1-100的自然数中,任意取出51个数,证明其中一定有两个数,它们中的一个是另一个的整数倍。
例4.从前25个自然数中任意取出7个数,证明:取出的数中一定有两个数,这两个数中大数不超过小数的1.5倍。
例4说明:(2)如果我们按照(1)中的递推方法依次造“抽屉”,则第7个抽屉为{26,27,28,29,30,31,32,33,34,35,36,37,38,39};第8个抽屉为:{40,41,42,…,60};第9个抽屉为:{61,62,63,…,90,91};……那么我们可以将例3改造为如下一系列题目:(1)从前16个自然数中任取6个自然数;……(2)从前39个自然数中任取8个自然数;……(3)从前60个自然数中任取9个自然数;……(4)从前91个自然数中任取10个自然数;……上述第(4)个命题,就是前苏联基辅第49届数学竞赛试题。
第十八章 组合1.抽屉原理。
例1 设整数n ≥4,a 1,a 2,…,a n 是区间(0,2n)内n 个不同的整数,证明:存在集合{a 1,a 2,…,a n }的一个子集,它的所有元素之和能被2n 整除。
[证明] (1)若n ∉{a 1,a 2,…,a n },则n 个不同的数属于n-1个集合{1,2n-1},{2,2n-2},…,{n-1,n+1}。
由抽屉原理知其中必存在两个数a i ,a j (i ≠j)属于同一集合,从而a i +a j =2n 被2n 整除;(2)若n ∈{a 1,a 2,…,a n },不妨设a n =n ,从a 1,a 2,…,a n -1(n-1≥3)中任意取3个数a i , a j , a k (a i ,<a j < a k ),则a j -a i 与a k -a i 中至少有一个不被n 整除,否则a k -a i =(a k -a j )+(a j -a i )≥2n ,这与a k ∈(0,2n)矛盾,故a 1,a 2,…,a n-1中必有两个数之差不被n 整除;不妨设a 1与a 2之差(a 2-a 1>0)不被n 整除,考虑n 个数a 1,a 2,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a n-1。
ⅰ)若这n 个数中有一个被n 整除,设此数等于k n ,若k 为偶数,则结论成立;若k 为奇数,则加上a n =n 知结论成立。
ⅱ)若这n 个数中没有一个被n 整除,则它们除以n 的余数只能取1,2,…,n-1这n-1个值,由抽屉原理知其中必有两个数除以n 的余数相同,它们之差被n 整除,而a 2-a 1不被n 整除,故这个差必为a i , a j , a k-1中若干个数之和,同ⅰ)可知结论成立。
2.极端原理。
例2 在n ×n 的方格表的每个小方格内写有一个非负整数,并且在某一行和某一列的交叉点处如果写有0,那么该行与该列所填的所有数之和不小于n 。
高中数学竞赛讲义(免费)编辑整理:尊敬的读者朋友们:这里是精品文档编辑中心,本文档内容是由我和我的同事精心编辑整理后发布的,发布之前我们对文中内容进行仔细校对,但是难免会有疏漏的地方,但是任然希望(高中数学竞赛讲义(免费))的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈,这将是我们进步的源泉,前进的动力。
本文可编辑可修改,如果觉得对您有帮助请收藏以便随时查阅,最后祝您生活愉快业绩进步,以下为高中数学竞赛讲义(免费)的全部内容。
高中数学竞赛资料一、高中数学竞赛大纲全国高中数学联赛全国高中数学联赛(一试)所涉及的知识范围不超出教育部2000年《全日制普通高级中学数学教学大纲》中所规定的教学要求和内容,但在方法的要求上有所提高。
全国高中数学联赛加试全国高中数学联赛加试(二试)与国际数学奥林匹克接轨,在知识方面有所扩展;适当增加一些教学大纲之外的内容,所增加的内容是:1。
平面几何几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、西姆松定理。
三角形中的几个特殊点:旁心、费马点,欧拉线。
几何不等式。
几何极值问题.几何中的变换:对称、平移、旋转。
圆的幂和根轴.面积方法,复数方法,向量方法,解析几何方法。
2。
代数周期函数,带绝对值的函数。
三角公式,三角恒等式,三角方程,三角不等式,反三角函数。
递归,递归数列及其性质,一阶、二阶线性常系数递归数列的通项公式。
第二数学归纳法。
平均值不等式,柯西不等式,排序不等式,切比雪夫不等式,一元凸函数。
复数及其指数形式、三角形式,欧拉公式,棣莫弗定理,单位根。
多项式的除法定理、因式分解定理,多项式的相等,整系数多项式的有理根*,多项式的插值公式*。
n次多项式根的个数,根与系数的关系,实系数多项式虚根成对定理。
函数迭代,简单的函数方程*3。
初等数论同余,欧几里得除法,裴蜀定理,完全剩余类,二次剩余,不定方程和方程组,高斯函数[x],费马小定理,格点及其性质,无穷递降法,欧拉定理*,孙子定理*.4.组合问题圆排列,有重复元素的排列与组合,组合恒等式。
第十八章 组合一、方法与例题1.抽屉原理。
例1 设整数n ≥4,a 1,a 2,…,a n 是区间(0,2n)内n 个不同的整数,证明:存在集合{a 1,a 2,…,a n }的一个子集,它的所有元素之和能被2n 整除。
[证明] (1)若n ∉{a 1,a 2,…,a n },则n 个不同的数属于n-1个集合{1,2n-1},{2,2n-2},…,{n-1,n+1}。
由抽屉原理知其中必存在两个数a i ,a j (i ≠j)属于同一集合,从而a i +a j =2n 被2n 整除;(2)若n ∈{a 1,a 2,…,a n },不妨设a n =n ,从a 1,a 2,…,a n-1(n-1≥3)中任意取3个数a i , a j , a k (a i ,<a j < a k ),则a j -a i 与a k -a i 中至少有一个不被n 整除,否则a k -a i =(a k -a j )+(a j -a i )≥2n ,这与a k ∈(0,2n)矛盾,故a 1,a 2,…,a n-1中必有两个数之差不被n 整除;不妨设a 1与a 2之差(a 2-a 1>0)不被n 整除,考虑n 个数a 1,a 2,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a n-1。
ⅰ)若这n 个数中有一个被n 整除,设此数等于k n ,若k 为偶数,则结论成立;若k 为奇数,则加上a n =n 知结论成立。
ⅱ)若这n 个数中没有一个被n 整除,则它们除以n 的余数只能取1,2,…,n-1这n-1个值,由抽屉原理知其中必有两个数除以n 的余数相同,它们之差被n 整除,而a 2-a 1不被n 整除,故这个差必为a i , a j , a k-1中若干个数之和,同ⅰ)可知结论成立。
2 极端原理。
例2 在n ×n 的方格表的每个小方格内写有一个非负整数,并且在某一行和某一列的交叉点处如果写有0,那么该行与该列所填的所有数之和不小于n 。
数学学科竞赛教案高中版
主题:高中数学竞赛备考
目标:通过本课的学习,学生能够掌握高中数学竞赛常见题型的解题技巧,提升自己的数学竞赛能力。
一、教学内容:
1. 数列与级数
2. 不等式与方程
3. 函数与极限
4. 解析几何
5. 数学归纳法
二、教学步骤:
1. 导入:通过介绍数学竞赛的重要性和意义,激发学生学习数学竞赛的兴趣。
2. 概念讲解:逐个介绍竞赛常见的数学概念和题型,帮助学生理解和掌握知识点。
3. 解题技巧:针对每种题型,讲解解题的方法和技巧,帮助学生提高解题效率。
4. 练习:提供一定数量的练习题,让学生在课堂上尝试解题,巩固所学知识。
5. 反馈:逐个讲解练习题的解法,指出学生容易犯的错误,并纠正。
6. 拓展:引导学生拓展思维,探讨数学竞赛中更深层次的问题,并提供相关资料让学生在课后继续学习。
三、教学评估:
1. 学生在课堂练习中的表现。
2. 学生对于解题技巧的掌握程度。
3. 学生在课后练习中的成绩提升情况。
四、教学反思:
根据学生的反馈和表现,及时调整教学方法和内容,不断提升教学质量,帮助学生在数学竞赛中取得更好的成绩。
高中数学趣味数字组合教案
【教学内容】:数学趣味数字组合
【教学目标】:
1. 训练学生观察、分析、计算和推理能力;
2. 激发学生对数学的兴趣;
3. 提高学生的团队合作精神。
【教学准备】:
1. 准备一些数字卡片,每张卡片写有0-9的数字;
2. 分组准备,每组4-5人。
【教学过程】:
1. 准备阶段(5分钟):
- 将数字卡片洗匀后随机摆放在桌上;
- 将学生按小组分组。
2. 活动一:数字组合游戏(15分钟):
- 按照顺序,每组派一名学生前往桌上抽取一张数字卡片;
- 每组共抽取5张数字卡片,然后组合成一个5位数;
- 每组展示自己的数字组合,最大的数字组合获胜。
3. 活动二:数字拼图比赛(15分钟):
- 每组给出一个数字,然后将数字拼成一个大数字;
- 要求每组拼出的数字最接近给定的数值,且不能重复使用数字。
4. 活动三:数字推理游戏(15分钟):
- 给出一组数字,要求学生根据规定条件组合成不同的数字;
- 规定条件可以是奇偶性、大小关系、倍数关系等。
5. 结束阶段(5分钟):
- 对学生的表现进行评价和总结;
- 鼓励学生表现出色的小组,给予奖励。
【课后作业】:
1. 回家整理本次活动中学到的数学规律和技巧;
2. 尝试组织朋友一起进行数字组合活动。
通过这样的数学趣味数字组合活动,不仅可以激发学生对数学的兴趣,还可以锻炼他们的观察、分析、计算和推理能力,同时也可以培养学生的团队合作精神,是一种既有趣又富有教育意义的数学教学方法。
【教案完毕】。
§16排列,组合1.排列组合题的求解策略(1)排除:对有限条件的问题,先从总体考虑,再把不符合条件的所有情况排除,这是解决排列组合题的常用策略.(2)分类与分步有些问题的处理可分成若干类,用加法原理,要注意每两类的交集为空集,所有各类的并集是全集;有些问题的处理分成几个步骤,把各个步骤的方法数相乘,即得总的方法数,这是乘法原理.(3)对称思想:两类情形出现的机会均等,可用总数取半得每种情形的方法数.(4)插空:某些元素不能相邻或某些元素在特殊位置时可采用插空法.即先安排好没有限制条件的元素,然后将有限制条件的元素按要求插入到排好的元素之间.(5)捆绑:把相邻的若干特殊元素“捆绑”为一个“大元素”,然后与其它“普通元素”全排列,然后再“松绑”,将这些特殊元素在这些位置上全排列.(6)隔板模型:对于将不可辨的球装入可辨的盒子中,求装的方法数,常用隔板模型.如将12个完全相同的球排成一列,在它们之间形成的11个缝隙中任意插入3块隔板,把球分成4堆,分别装入4个不同的盒子中的方法数应为311C ,这也就是方程12=+++d c b a 的正整数解的个数.2.圆排列(1)由},,,,{321n a a a a A =的n 个元素中,每次取出r 个元素排在一个圆环上,叫做一个圆排列(或叫环状排列).(2)圆排列有三个特点:(i )无头无尾;(ii )按照同一方向转换后仍是同一排列;(iii )两个圆排列只有在元素不同或者元素虽然相同,但元素之间的顺序不同,才是不同的圆排列.(3)定理:在},,,,{321n a a a a A =的n 个元素中,每次取出r 个不同的元素进行圆排列,圆排列数为rP r n . 3.可重排列允许元素重复出现的排列,叫做有重复的排列.在m 个不同的元素中,每次取出n 个元素,元素可以重复出现,按照一定的顺序那么第一、第二、…、第n 位是的选取元素的方法都是m 种,所以从m 个不同的元素中,每次取出n 个元素的可重复的排列数为n m .4.不尽相异元素的全排列如果n 个元素中,有1p 个元素相同,又有2p 个元素相同,…,又有s p 个元素相同(n p p p s ≤+++ 21),这n 个元素全部取的排列叫做不尽相异的n 个元素的全排列,它的排列数是!!!!21s p p p n ⋅⋅⋅ 5.可重组合(1)从n 个元素,每次取出p 个元素,允许所取的元素重复出现p ,,2,1 次的组合叫从n 个元素取出p 个有重复的组合.(2)定理:从n 个元素每次取出p 个元素有重复的组合数为:r p n p n C H )1(-+=.例题讲解1.数1447,1005,1231有某些共同点,即每个数都是首位为1的四位数,且每个四位数中恰有两个数字相同,这样的四位数共有多少个?2.有多少个能被3整除而又含有数字6的五位数?3.有n 2个人参加收发电报培训,每两人结为一对互发互收,有多少种不同的结对方式?4.将1+n 个不同的小球放入n 个不同的盒子中,要使每个盒子都不空,共有多少种放法?5.在正方体的8个顶点,12条棱的中点,6个面的中心及正方体的中心共27个点中,共线的三点组的个数是多少个?6.用8个数字1,1,7,7,8,8,9,9可以组成不同的四位数有多少个?7.用E D C B A ,,,,五种颜色给正方体的各个面涂色,并使相邻面必须涂不同的颜色,共有多少种不同的涂色方式?8.某种产品有4只次品和6只正品(每只产品可区分),每次取一只测试,直到4只次品全部测出为止.求最后一只次品在第五次测试时被发现的不同情形有多少种?9.在平面上给出5个点,连结这些点的直线互不平行,互不重合,也互不垂直,过每点向其余四点的连线作垂线,求这此垂线的交点最多能有多少个?10.位政治家举行圆桌会议,两位互为政敌的政治家不愿相邻,其入坐方法有多少种?11.某城市有6条南北走向的街道,5条东西走向的街道.如果有人从城南北角(图A 点)走到东南角中B 点最短的走法有多少种?12.用4个1号球,3个2号球,2个3号球摇出一个9位的奖号,共有多少种可能的号码?13.将r 个相同的小球,放入n 个不同的盒子(n r ).(1)有多少种不同的放法?(2)如果不允许空盒应有多少种不同的放法?14.8个女孩和25个男孩围成一圈,任意两个女孩之间至少站着两个男孩.(只要把圆旋转一下就重合的排列认为是相同的)课后练习1.8次射击,命中3次,其中愉有2次连续命中的情形共有( )种(A )15 (B )30 (C )48 (D )602.在某次乒乓球单打比赛中,原计划每两名选手恰比赛一场,但有3名选手各比赛了2场之后就退出了,这样,全部比赛只进行了50场。
高中高三数学上册《组合》教案教案:《组合》教材:高中数学上册班级:高三班教学目标:1. 掌握组合的基本概念和计算方法。
2. 熟练运用组合的思想解决实际问题。
3. 培养学生的逻辑思维和分析问题的能力。
教学重点:1. 理解组合的意义和基本性质。
2. 掌握计算组合数的方法。
3. 学会运用组合的思想解决实际问题。
教学难点:1. 运用组合的思想解决实际问题。
2. 灵活运用计算组合数的方法。
教学准备:1. 教材课本。
2. 笔记本和笔。
教学过程:Step 1:概念讲解1. 明确组合的概念:从n个不同元素中取出m(m≤n)个元素进行排列,不考虑元素的顺序,称为一个组合。
2. 引导学生理解组合的意义和计算方法,通过具体的例子进行讲解。
Step 2:计算方法1. 讲解计算组合数的方法:C(n,m)=n!/(m!(n-m)!)。
2. 给学生讲解具体计算步骤,并进行实例演练。
Step 3:实际问题解决1. 给学生提供一些实际问题,让他们运用组合的思想解决问题。
2. 引导学生分析问题,确定解题思路,并进行解题训练。
Step 4:课堂练习1. 回顾和巩固所学内容,让学生进行一些练习题的答题训练。
2. 共同讨论解法,解决遇到的问题。
Step 5:小结和作业布置1. 小结本节课的内容和要点。
2. 布置课后作业,巩固所学内容。
教学反思:1. 教师应该注意对组合概念的讲解,引导学生理解组合的意义和计算方法。
2. 通过实际问题的解决,培养学生的逻辑思维和分析问题的能力。
3. 通过课堂练习巩固所学内容,及时发现和解决学生的问题。
数学竞赛讲义:排列与组合【赛点直击】一、两个基本原理加法原理 设A 为完成一件事情的所有方法的集合,它可以划分为n 个互不相交的非空子集A 1,A 2,…,A n ,|A i |=m i (i=1,2,…,n),那么完成这件事情的总方法数为:N=|A|=m 1+m 2+…+m n ;使用加法原理的关键在于对所计数的对象进行完全分类.乘法原理 设A 为完成一件事情的所有方法的集合,且完成这件事情需要几个步骤,实现第i(i=1,2,…,n)个步骤的方法的集合为A i ,|A i |=m i ,那么完成这件事情的总方法数为N=|A|=m 1×m 2×…×m n ;使用乘法原理的关键在于对所计数的对象进行完全分步. 二、相异元素的排列与组合(1)从n 个不同元素中,任取m 个不同元素的排列数是!(1)(1)()!mn n A n n n m n m =⋅-⋅⋅-+=-;(2)从n 个不同元素中,任取m 个不同元素的组合数是!()!m n n C n m =-;三、圆排列定义 从n 元集中任取r 个不同元素,仅按元素之间的相对位置而不分首尾排成一个圆圈,这种排列称为n 个不同元素的r-圆排列,其排列数记为rn H .由定义,不难求得:r n H 与组合数r n C 和排列数r n A 的关系为:rA r C H rnr nr n =-=)!1(.事实上设已将某r 个不同元素在圆周上排好,并从某个元素开始将它们依次记为r A A A ,,,21 ,现在保持这个顺序不变,让1A 去任意选择圆周上的r 个位置之一,有r 种不同的选择,这r 种选择所对应的排列形式不同实则相同由于r 个元素的全排列数为!r ,故r 个元素的圆排列数为)!1(-r ,故n 个元素的圆排列数为)!1(-r C rn .四、重复排列定义 从n 元集中允许重复地任取r 个元素排成一列,称为n 个不同元素的r-可重排列.利用乘法原理易证明,n 个不同元素的r-可重排列数为r n ,这类问题一般可直接用乘法原理求解. 五、不全相异元素的全排列定义 设n 个元素可分为k 组,每一组中的元素是相同的,不同组间的元素是不同的,其中第i 组的元素个数为i n ),...,2,1(k i =,n n n n k =+++...21,则这n 个元素的全排列称为不全相异元素的全排列.n 个元素的不全相异元素的全排列个数为!!...!!21k n n n n ,证明如下:先把每组中的元素看作是不相同的,则n 个不同元素的全排列数为!n ,然后分别将每个组的元素还其本来面目——每个组的元素是相同的,则在这!n 个全排列中,每个排列都重复出现了12!!...!k n n n 次,所以不全相异元素的全排列数为!!...!!21k n n n n .六、多组组合定义 将n 个不同的元素分成k 组的组合称为n 个不同元素的k -组合.对于一个n 个不同元素的k -组合,若第i 组有i n 个元素,(k i ,...,2,1=),则不难证明不同的分组方法数为!!...!!21,...,,21k n n n n n n n n C k=事实上,我们把分组的过程安排成相继的k 个步骤:第一步,从n 个不同元素中选1n 个,有1n n C 种方法;第二步,从1n n -个元素中选2n 个有21nn n C -种方法,……,第k 步,从121...-----k n n n n 个元素选k n 个元素,有k k nn n n n C )...(121-+++-种方法,再由乘法原理得证.七、重复组合定义 从n 个不同的元素中任取r 个允许重复出现的组合称为n 个不同元素的r —可重组合.不难证明,n 个不同元素的r —可重组合的个数为rr n C 1-+.事实上,设(r a a a ,...,,21)是取自{1,2,…,n}中的任一r-可重复组合,并设r a a a ≤≤≤...21,令)1(1r i i a b i i ≤≤-+=,从而11a b =,122+=a b ,233+=a b ,…,1-+=r a b r r ,显然下面两组数是一对一的:r a a a ≤≤≤...21,11...211321-+≤-+<<+<+<≤r n r a a a a r设=A {}r i r a a a n a a a a ≤≤≤∈...},,...,2,1{|),...,,(2121,=B{}r i r b b b r n b b b b <<<-+∈...},1,...,2,1{|),...,,(2121,则由A 、B 之间存在一一对应,可知r r n C B A 1||||-+==,得证.在上述证明中,设r-可重复组合r a a a ,...,,21中含有1x 个1,2x 个2,…,n x 个n ,则r x x x n =+++...21,且显然有(r a a a ,...,,21)与(n x x x ,...,,21)一一对应,因此我们立即可得:定理1 不定方程r x x x n =+++...21的非负整数解的个数为rr n C 1-+.定理2 不定方程r x x x n =+++...21的正整数解的个数为11--n r C .证明:令1-=i i x y ,其中1≥i x ,(n x x x ,...,,21)是已知方程的正整数解,则n r y y y n -=+++...21 (*),由定理1知,方程(*)有1111)(-------+==n r nr r nr r n n C C C 个正整数解.【赛题解析】例1.在由n 2个小方格组成的正方形中,有多少个由整数个小方格组成的大小或位置不同的正方形?解:由整数个小方格组成的大小位置不同的正方形可分成n 类,第k 类为k ×k 的正方形,共有2)1(+-k n 个(k=1,2,…,n),于是由加法原理得所求正方形的总个数为)12)(1(61)1(12++=+-=∑=n n n k n N nk . 说明:此题将问题进行分类,直接用加法及乘法原理进行求解,两个原理是解决排列组合问题最基本的工具. 例2.设整数a,b,c 为三角形三边,a+b=n ∈N,1≤c ≤n-1,求这样的整边三角形的个数 解:不妨设b ≥a ,有1≤a ≤[2n],这样的整边三角形可分为两类. 第一类:c 为最大边,令i a =,则i n b -=,n-i ≤c ≤n-1,这样的三角形有i i n n =+---1)()1(个;第二类:c 不为最大边,则b a c c b >+>,,故i n c i n a b -<<-=-2,故112--≤≤+-i n c i n ,这样的三角形有11)12()1(-=++----i i n i n .由加法原理,使a+b=n 的整边三角形的个数为∑=-+=]2[1)1()(ni i i n f 2]2[⎪⎭⎫⎝⎛=n .例3.有多少个能被3整除而又含有数字6的五位数?解:易知,在由10000~99999这90000个五位数中,共有30000个可被3整除,下面先求其中不含数字6的有多少个.这件事情可分步来完成:在最高位,不能为0和6,因此有8种可能的情况,在千、百、十位上,不能为6,各有9种可能的情况,在个位上,不能为6,且应使整个五位数能被3整除,因此所出现的数应与前4位数字之和被3除的余数有关:当该余数为2时,个位上可为1,4,7中的一个;当该余数为1时,个位上可为2,5,8中的一个;当该余数为0时,个位上可为0,3,9中的一个,总之,不论前4位数如何,个位数字都有3种可能情况.所以这类五位数的个数为8×9×9×9×3=17496,因此,含数字6而又可被3整除的五位数的个数为30000-17496=12504种可能.例4.从1,2,3,4,……,49中取出六个不同的数字,其中至少有两个是相邻的取法种数是多少? 解:设126,,,a a a 是取自1,2,3,4,……,49中的六个不同的数,不妨设126a a a <<<,显然12345612345a a a a a a ≤-≤-≤-≤-≤-,且123456,1,2,3,4,5a a a a a a -----互不相同的充要条件是:126,,,a a a 中不含相邻的数.作六元数组126(,,,)a a a 对应于123456(,1,2,3,4,5)a a a a a a -----,则在取自1至49之间的六个不同且没有相邻的数构成的六元组集合与所有取自1至44之间的六个不同的数构成的六元组集合之间建立了一一对应,因此这两个集合中六元组的个数都为644C ,而1至49之间的六个不同的数构成的六元组的个数为649C ,于是,其中有相邻数的六元组的个数为664944C C -.说明:本题通过对应的方法将数相邻的问题转化为元素互异的问题,从而得到求解,对应的方法是解决排列组合问题的一种常用方法.例5.如图ABCDEF为六边形,一只青蛙开始在顶点A处,它每次可随意跳到相邻两个顶点之一.(1)若在5次内跳到D点,则停止跳动;若5次内不能跳到D点,跳完5次也停止跳动.问这只青蛙从开始到停止,可能出现的不同跳法有几种?(2)若青蛙共跳12次,最终跳回到A点的不同跳法有几种?解:(1)由条件,青蛙的跳法只可能出现两种情况:①跳3次到达D点,有2种跳法.②跳5次停止(前3次不到D点),注意到前3次的32种跳法中,有2种到达D点,故前3次有3226-=种跳法,而后2次有22种跳法,因此有26224⨯=种跳法.由①、②可知,共有2+24=26种不同的跳法.(2)设青蛙每逆时针跳一步记为+1,每顺时针跳一步记为-1,共跳12次,将所有这些数相加,若其和为6的倍数,则青蛙跳回A处,若其和不为6的倍数,则青蛙不可能跳回原处,若其和为0,则必为6个+1和6个-1相加,共有612C种可能;若其和为6,则必为9个+1和3个-1相加,共312C种;若其和为-6,则必为3个+1和9个-1相加,共312C种;若其和为12,则有1种可能,若其和为-12,也有一种可能,因此满足要求的不同跳法总数为63121222C C++种.例6.将一个四棱锥S-ABCD的每个顶点染上一种颜条棱的两端点异色,如果只有5种颜色可供使用,那么不同的染色方法的总数是多少?解法一:由题设,四棱锥S-ABCD的顶点S、A、B所染的颜色互不相同,它们共35A种染色方法.当S、A、B已染好时,不妨设其颜色分别为1、2、3,若C染颜色2,则D可染颜色3、4、5之一,有3种染法;若C染颜色4,则D 可染颜色3或5,有2种染法;若C染颜色5,则D可染颜色3或4,也有2种染法,由此可见,当S、A、B已染好时,C与D还有7种染法,从而总的染色方法数为7×35A=420种.解法二:满足题设条件的染色至少要用三种颜色.(1)若恰用三种颜色,可先从5种颜色中任选一种染顶点S,再从余下的四种颜色中任选两种染A、B、C、D四点,此时只能A与C、B与D分别同色,故有60122415=⋅CCC种方法;(2)若恰用四种颜色染色,可以先从5种颜色中任选一种染顶点S,再从余下的四种颜色中任选两种染A与B,由于A与B颜色可以交换,故有24A种染法,再从余下的两种颜色中任选一种染D或C,而D与C中另一个只需染与其相对顶点同色即可,故有24012122415=CCAC种方法;(3)若恰用5种颜色染色,易知有12055=A种染法.综上所知,满足题意的总染色方法数为60+240+120=420种.类题:(2003年高考江苏第15题)某城市在中心广场建造一个花囿,花囿分为6个部分(如图),现要栽种4种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法有______________种(以数字作答).解法一:1、2、3两两相邻,颜色应互不相同,故有34A种不同种法;1、2、3种好后,用树图方法不难得到4、5、6共有5种种法,由乘法原理得共有34A×5=120种种法.解法二:先种1,有4种颜色可选取,2、3、4、5、6形成一个圆环,要求用3种颜色涂上,且相邻的颜色不同即可转化为如下问题:将一个圆分成5个扇形,将三种颜色涂入其中,相邻的扇形涂不同的颜色.先涂1S,有三种涂法,再涂2S,有两种涂法,再涂3、4各有两种涂法,再涂5,如果只要求它与4颜色不同,则仍有两种涂法,这样共有3×2×2×2×2=48种涂法,但这48种涂法中有两类:一类5与1颜色不同,这种涂法符合题意,其数设为5a一类5与1颜色相同,这种涂法不合题意,如果把5与1合并看成一个扇形,这类涂法就相当于把圆分成4个扇形,按题设要求,其数为4a,即5a+4a=48,同理,34aa+=24,而6333==Aa,∴5a=30,故最后的结果为:30×4=120种.此问题可一般化为:把一个圆分成)2(≥nn个扇形,依次记为,,,,21nSSS 每个扇形都可用红、白、蓝三种不同颜色之任一种涂色,且三种颜色均至少用一次,要求相邻的扇形颜色互不相同,问有多少种涂色法?略解:同上可得: ,6,5,4,2311=⨯=+--n a a n n n ,63=a .若没有条件“颜色均至少用一次”,结果为 ,6,5,4,2311=⨯=+--n a a n n n ,62=a .更一般的情形是:把一个圆分成)2(≥n n 个扇形,依次记为,,,,21n S S S 每个扇形都可用r 种不同颜色之任一种涂色,要求相邻的扇形颜色互不相同,问有多少种涂色法? 有11(1),4,5,6,n n n a a r r n --+=⨯-=,可得n n n r r a )1()1)(1(-+--=说明:当我们用集合划分的方法对问题进行分类计数时,有时不可能一次性获得成功,这就需要通过建立递推关系来求解,我们把这种计数方法称为递推方法.例7.设集合A={1,2,3,…,366},如果A 的一个二元子集B={a ,b }满足17|a +b ,则称B 具有性质P . (1) 求A 的具有性质P 的所有二元子集的个数;(2) 求A 的两两不相交且具有性质P 的所有二元子集的个数.解:(1)a +b ≡0(mod17),即a ≡k (mod17)且b ≡17-k (mod17),k =0,1,2,…,16, 将1,2,3,…,366按模17可分为17类[0],[1],…[16];因366=17×21+9,故|[1]|=|[2]|=…=|[9]|=22,|[10]|=|[11]|=…=|[16]|=|[0]|=21, 欲17|a +b ,当且仅当a ,b ∈[0]或a ∈[k ],b ∈[17-k ],当a ,b ∈[0]时,具有性质P 的二元子集的个数为221C 个;当a ∈[k ],b ∈[17-k ],k =1,2,…,7时,具有性质P 的二元子集有1211227C C 个; 当a ∈[8],b ∈[9]时,具有性质P 的二元子集有121121C C 个; 所以A 的具有性质P 的二元子集总个数为39287121121121122221=++C C C C C 个. 说明:如果把子集换成数对(a ,b ),则共有2×3928个. (2)为使二元子集两两不交,可作如下搭配: a ,b ∈[0]时,共有10个子集;a ∈[k ],b ∈[17-k ],k=1,2,…,7,有21个子集; 当a ∈[8],b ∈[9]时,有22个子集.故A 的具有性质P 的两两不交的二元子集共有10+7×21=179个.例8.8个女孩和25个男孩围成一圈,任何两个女孩之间至少站两个男孩,问共有多少种不同的排列方法(只要把圈旋转一下就重合的排法认为是相同的).解:以1个女孩和2个男孩为一组,且使女孩恰好站在两个男孩中间,余下的9个男孩和这8个组被看成是17个元素,显然这17个元素任意的圆排列数为1616A 种再次,分在8个组内的16个男孩在16个位置上的排列是1616A ,所以总的排列方法数为:16161616925A A C .说明:此题为圆排列问题.例9.试求从集合{}n A ,...,2,1=到集合{}m B ,...,2,1=的映射的个数. 解:由映射的定义知,每一个到B 的映射对应着m 个不同元素的n -可重排列,故从A 到B 的映射的个数为nm .例10.一段楼梯共有12级台阶,某人上楼时,有时一步迈一台阶,有时一步迈两台阶,问此人共有多少种上楼的方法?解:现将“一步迈两级台阶”这一动作记为a ,因为楼梯共有12级台阶,故动作a 至多只能做6次;再记“一步迈一级台阶”的动作为b ,则上楼的整个过程由k 个a 及12-2k 个b 组成,这里k 可取0,1,2,3,4,5,6,对于某个k ,其全排列数为:)!212(!]!212([k k k k --+)!212(!)!12(k k k --=,因此,上楼的方法共有:∑=--60)!212(!)!12(k k k k =233种. 解法2:以k =4为例,即4个两级,4个一级,相当于共8步,其中有四步为两级,即相当于从8步中选4步跨两级,其余跨一级,故结果应为48C ;一般地上楼的整个过程由k 个a 及12-2k 个b 组成,相当于共跨k +(12-2k )=12-k 步,其中有k 步为a ,故结果为kk C -12,这里k 可取0,1,2,3,4,5,6,故最终结果为∑=-612k k kC.解法3:设走n 次台阶的方法总数为n a ,对每种走法可划分为两类第一类:第一步走1级,有1-n a 种走法;第二类:第一步走2级,有2-n a 种走法,故21--+=n n n a a a ,且2,121==a a ,故易得23312=a .因Fibonacci 数列}{n F 满足2,1321===F F F ,故1+=n n F a ,由上面的一些方法还可知:∑=--=]2[01n k kk n n CF .若将所跨的每一级台阶,此人均用红、白两种颜色做上记号,则标有不同颜色的路线共有∑=---=⋅]2[02132ni i n i in n C种,其递推关系式为5,2,22121==-=--a a a a a n n n .例11.把n 个不同的球,分别装入m 个盒子中,使其中1m 个盒子中每个都有1p 个球,2m 个盒子中每个都有2p 个球,…,k m 个盒子中每个都有k p 个球,这里,k k k m p m p m p n m m m m +++=+++=...,...221121,求下列情况下,各有多少种不同放法:(1)盒子均不相同;(2)装有相同数目的球的盒子相同.解:(1)这是一个将n 个不同元素分为m 组的多组组合,故不同的放法数有k m k m m p p p n f )!...()!()!(!2121=; (2)因为相同数目的球的盒子相同(不加区别),故所求放法数为!!...!21k m m m f.例12.电视台在n 天内共播出r 次商业广告,问若每天至少播p 次广告(r np ≤),就每天播出广告的次数而言,共有几种播出方法? 解:设第i 天播出广告i x 次,由题设知:r x x x n =+++...21,),...,2,1(n i p x i =≥,令p x y i i -=,则0...21≥-=+++np r y y y n ,故问题转化为求上述不定方程的非负整数解的个数,从而知广告播放的方法数为npr n np r C --+-1)(.巩 固 练 习1.n 名同学(n ≥3)站成一圈,其中A 、B 两人不能相邻的站法有多少种? 解:n 名同学站成一圈有(n-1)!种站法,其中使A 、B 相邻的站法有2×(n-2)!种,从而A 、B 不相邻的站法为(n -1)!-2×(n-2)!=(n-3)(n-2)!种站法.2.设集合A 、B 的并集为一个n 元集,A ≠B .(1) 若(A ,B )与(B ,A )视为不同的对,则这样的A 、B 共有多少个? (2) 若(A ,B )与(B ,A )视为相同的对,则这样的A 、B 共有多少个?解:(1)设集合A 中有k 个元素,则集合B 中必含有A 中没有的n-k 个元素,再加上A 的k 个元素中取0个、1个、…k 个,故共有kk n C 2个,故总数为∑=nk k knC2=n 3个,除去A 与B 相同(均为全集)的1个,共n 3-1个;(2)由题意,(A ,B )与(B ,A )一一对应,故结果为)13(21-n个. 3.在一个正六边形的六个区域栽种观赏植物,如图,要求同一块中种同一植物,相邻的两块种不同的植物,现有4种不同的植物可供选择,则有多少种不同的栽种方案.解:考虑A 、C 、E 种同一种植物,此时共有4×3×3×3=108种;考虑A 、C 、E 种两种植物,此时共有3×4×3×3×2×2=432种方法;考虑A 、C 、E 种三种植物,此时共有34C ×2×2×2=192种方法;故总计有108+432+192=732种方案.4.如图,矩形ABCD 的边在网格线上,并且AB 是AD 的k 倍(k 为正整数),考虑沿网格的边从A 到C 所有可能的最短路径.证明:在这些路径中,含AB 1的条数是含AD 1的条数的k 倍.横向的m-1节,纵向的n 节,因此共有1nm n C +-条,解:含AB 1的最短路径,除AB 1外,还应含同理,含AD 1的最短路径有1mm n C+-条,而11!(1)!!(1)!n m n mm n C m n m k C n m n+-+--===-,因此命题得证. 5.马路上有编号为1,2,3,…,2005的2005只路灯,为节约用电,现要求把其中的200只灯关掉,但不能同时关掉相邻的两只或三只,也不能关掉两端的路灯,求满足条件的关灯方法共有多少种?解:任意一种关灯的方法,都对应着一种满足题设条件的亮灯与暗灯的排列,于是总是转化为1805只亮灯中插入200只暗灯,且任何两只暗灯不相邻,而且不在两端,也就是在1805只亮灯所形成的1804个间隙中选200个插入暗灯,其方法有2001804C 种.6.把2005个不加区别的小球分别放在10个不同的盒子里,使得第i 个盒子中至少有i 个球)10,...,2,1(=i ,问不同放法的总数是多少? 解:先在第i 个盒子里放入i 个球,这时共放了1+2+…+10=55个球,还余下2005-55=1950个球,故问题转化为把1950个球任意放入10个盒子(允许有的盒子不放球),相当于一个不定方程的非负整数解的个数问题,共有195019509101950119591959C C C +-==种.7.n 个人)3(≥n 站成一圈,其中某指定的两人A 、B 肯定不相邻的站法有多少种? 答案:)!2(2)!1(---n n .8.甲、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛,双方先由一号队员比赛,负者被淘汰,胜者再与负方2号队员比赛,……,直到一方队员全部淘汰为止,另一方获得胜利,形成一种比赛过程,那么所有可能出现的比赛过程的种数是多少?解:不妨先设甲方胜出,则问题等价于求方程7...721=+++x x x 的非负整数解的个数,有6137177C C =-+种,同理,乙方胜的比赛过程也有6137177C C =-+种,故可能出现的比赛过程有6132C 种.9.有男生m n +人,女生m 人(1,≥n m ),(1)这m n 2+个人排成一列,女生不相邻,首尾都是男生,有多少种排法? (2))这m n 2+个人围成一圈,女生不相邻,有多少种排法?解:(1)m m n A m n 1)!(-++;(2)先作男生圆排列,然后插入,共mm n A m n +-+)!1(.10.方程3...210321=++++x x x x 的非负整数解共有多少个? 解:由题意,1,01=x ,故分情况讨论如下:若01=x ,则3...1032=+++x x x ,非负整数解的个数为:1653139=-+C ; 若11=x ,则1...1032=+++x x x ,非负整数解的个数为:91119=-+C .综上,非负整数解的个数为:165+9=174个.11.一个盒子里有7个分别标有号码1,2,…,7的球,每次取出一个,记下它的号码后再放回盒子,共取(放)4次,求4次中最大标号恰是5的取法数?解:最大标号为5,相当于从1,2,…,5中取,共取(放)4次,共有45种取法;从中剔除四次中最大标号均不是5的种数,结果为4544-=369.12.已知集合{}2,,,|12≥∈∈==-n N n C z z z z A n ,在复平面上,以A 中的复数的对应点为顶点可构成多少个直角三角形? 解:易求得{}122,,,1,0-=n A εεε ,其中nieπε=(n ≥2)设各复数在复平面上对应点依次为O 、A 0、A 1、A 2、…、A 2n-1,则A 0A 1A 2…A 2n-1为正2n 边形,易知在j i A OA ∆中以j i A A ,为顶点的内角均为锐角,所以,由O 、A 0、A 1、A 2、…、A 2n-1为顶点的直角三角形可分为两类: 第一类:以O 为直角顶点的直角三角形,不失一般性,可设︒=∠900K OA A ,则nk ππ=2,所以)(2N k k n ∈=,这说明这类直角三角形存在当且仅当n 为偶数时,这时,这样的直角三角形有2n 个;第二类:不以O 为直角顶点的直角三角形这样的直角三角形的顶点均匀分布在单位圆周上,即由A 0、A 1、A 2、…、A 2n-1构成,这些点可确定n 条直径,于是可构成)22(-n n 个直角三角形综上所述,由加法原理,所求直角三角形的总个数为⎩⎨⎧-=+-=为奇数为偶数n n n n n n n n n f ),1(2,22)22()(2.。
高中数学排列组合教案(6篇)高中数学排列组合教案(精选篇1)教学主题:主要涉及到简洁排列组合问题,相同元素和不同元素排列组合问题。
捆绑法插空法特别元素法特别位置法定序法分组安排教学内容及分析:排列组合问题是高中数学学问的一个重要组成部分,在高考中也是必考内容,难度一般在中等偏上,只要把握的排列组合的几种典型方法,就能快速理解题型题意,快速找到突破口,对症下药,事半功倍,关键是要把握住什么题型用什么方法,通过题型对比分析相同点和不同点,区分易错的,难点。
另外,排列组合在适应新高考有着自然出题优势,由于排列组合更贴近显示生活,可以把我们课本上的抽象概念和数学公式和实际生活联系起来,数学学问走进生活,学问来与是但高于生活,最终回归于生活,才是我们学习学问,专研学问的立足点。
本文就对数学中概率统计中的一小点内容——排列组合,做一个简洁的对比分析。
教学对象及特点:排列组合在高中数学选修2—3。
人教版教材,高二的同学在日常生活中,有许多需要用排列组合来解决的学问。
作为二班级的同学,已有了肯定的生活阅历及解决问题的力量。
因此,在设计中,我通过创设一个完整的、好玩的生活情境来进行教学,力求使同学在经受日常生活最简洁的事例中体验到重要的数学思想方法,从而也感受到数学思想也是依托于生活,来源于生活,是有生命活力的。
教学目标:基于对教材的理解,我把本节课的教学重点定为:在经受简洁事物排列与组合规律的过程中体会排列与组合的数学思想。
教学难点定为:培育同学全面有序的思索问题的意识。
通过观看、猜想、比较、试验等活动,培育同学学习初步的观看、分析力量和有序、全面地思索问题的意识。
培育同学大胆猜想、乐观思维的学习方法,使同学感受学习数学的欢乐,进一步激发同学学习数学的爱好。
教学过程:一、排列问题例1:有4个男生,5个女生站队,在下列条件下,有多少种状况?(1)9个人全部站成一排;(2)9个人站成两排,前排站4人,后排站5人;(3)9个人全部站一排,全部女生站在一起;(捆绑法)(4)9个人全部站一排,全部男生都不相邻;(插空法)(5)9个人全部站一排,甲乙相邻,丙丁不相邻;(6)9个人全部站一排,甲不在两端;(特别元素法,特别位置法)(7)9个人全部站一排,甲不在最左边,乙不在最右边;(8)9个人全部站一排,甲在乙的左边,可以不相邻;(定序)(9)9个人全部站一排,甲在乙的前面,乙在丙的前面,可以不相邻;(10)9个人全部站一排,甲在乙和丙的中间,可以不相邻;二、组合问题例2:有25件产品,其中5件次品,从中任取3件,在下列条件下,有多少种状况?(1)次品甲在内;(2)次品甲不在内;(3)恰有1件次品;(4)至少1件次品;(5)至少2件次品;三、分组安排问题(不同元素)例3:有6名同学安排到三个班级,在下列条件下,有多少种状况?(1)随机安排;(2)每个班表达对一名同学的争取意愿,6名同学实力相当;(3)安排到三个班的人数分别为1、2、3人;(4)安排到三个班的人数分别为1、1、4人;(5)安排到三个班的人数分别为2、2、2人;四、分组安排问题(相同元素)例4:9个相同的乒乓球分给3个不同的人,在下列条件下,有多少种状况?(1)3个人分别分到2个乒乓球,3个乒乓球,4个乒乓球;(2)3个人分别分到2个乒乓球,2个乒乓球,5个乒乓球;(3)3个人平均分,每人得到3个乒乓球;(4)3个人每人至少分到1个乒乓球;(5)3个人每个人至少分到2个乒乓球;(6)3个人随机安排这9个乒乓球;五、分组安排问题(部分元素相同)例5:有外形大小相同,颜色不全相同的乒乓球,其中红色乒乓球,黄色乒乓球,黑色乒乓球分别有5个,从中取出四个乒乓球排一排,在下列条件下,有多少种状况?(1)取3个红色乒乓球,1个黄色乒乓球;(2)取2个红色乒乓球,2个黄色乒乓球;(3)取2个红色乒乓球,1个黑色乒乓球,1个黄色乒乓球;(4)取出的4个乒乓球中刚好3个乒乓球颜色相同;(5)取出的4个乒乓球中刚好2个乒乓球颜色相同,其他两个乒乓球颜色也相同;取出的4个乒乓球中刚好2个乒乓球颜色相同,其他两个乒乓球颜色不同;所选技术以及技术使用的目的:选取的技术是PPT演示文稿,电子文档,交互式电子白板,目的是能和同学共享资源,实时授课,不用边抄题目边讲课,节省时间,集中精力。
数学竞赛讲义:排列与组合【赛点直击】一、两个基本原理加法原理 设A 为完成一件事情的所有方法的集合,它可以划分为n 个互不相交的非空子集A 1,A 2,…,A n ,|A i |=m i (i=1,2,…,n),那么完成这件事情的总方法数为: N=|A|=m 1+m 2+…+m n ;使用加法原理的关键在于对所计数的对象进行完全分类.乘法原理 设A 为完成一件事情的所有方法的集合,且完成这件事情需要几个步骤,实现第i(i=1,2,…,n)个步骤的方法的集合为A i ,|A i |=m i ,那么完成这件事情的总方法数为 N=|A|=m 1×m 2×…×m n ;使用乘法原理的关键在于对所计数的对象进行完全分步. 二、相异元素的排列与组合(1)从n 个不同元素中,任取m 个不同元素的排列数是!(1)(1)()!mn n A n n n m n m =⋅-⋅⋅-+=- ;(2)从n 个不同元素中,任取m 个不同元素的组合数是!()!m n n C n m =-;三、圆排列定义 从n 元集中任取r 个不同元素,仅按元素之间的相对位置而不分首尾排成一个圆圈,这种排列称为n 个不同元素的r-圆排列,其排列数记为r nH . 由定义,不难求得:rn H 与组合数和r n C 排列数的关r n A 系为:rA r C H rn r n r n =-=)!1(.事实上设已将某r 个不同元素在圆周上排好,并从某个元素开始将它们依次记为r A A A ,,,21 ,现在保持这个顺序不变,让去任意选1A 择圆周上的r 个位置之一,有r 种不同的选择,这r 种选择所对应的排列形式不同实则相同由于r 个元素的全排列数为!r ,故r 个元素的圆排列数为)!1(-r ,故n 个元素的圆排列数为)!1(-r C rn .四、重复排列定义 从n 元集中允许重复地任取r 个元素排成一列,称为n 个不同元素的r -可重排列.利用乘法原理易证明,n 个不同元素的r-可重排列数为rn ,这类问题一般可直接用乘法原理求解.五、不全相异元素的全排列定义 设n 个元素可分为k 组,每一组中的元素是相同的,不同组间的元素是不同的,其中第i 组的元素个数为i n ),...,2,1(k i =,n n n n k =+++...21,则这n 个元素的全排列称为不全相异元素的全排列.n 个元素的不全相异元素的全排列个数为!!...!!21k n n n n ,证明如下:先把每组中的元素看作是不相同的,则n 个不同元素的全排列数为!n ,然后分别将每个组的元素还其本来面目——每个组的元素是相同的,则在这个全!n 排列中,每个排列都重复出现了12!!...!k n n n 次,所以不全相异元素的全排列数为!!...!!21k n n n n .六、多组组合定义 将n 个不同的元素分成k 组的组合称为n 个不同元素的k -组合.对于一个n 个不同元素的k -组合,若第i 组有i n 个元素,(k i ,...,2,1=),则不难证明不同的分组方法数为事!!...!!21,...,,21k n n n n n n n n C k=实上,我们把分组的过程安排成相继的k 个步骤:第一步,从n 个不同元素中选1n 个,有1n n C 种方法;第二步,从个元素中1n n -选个有种方2n 21nn n C -法,……,第k 步,从个元素选121...-----k n n n n k n 个元素,有k k nn n n n C )...(121-+++-种方法,再由乘法原理得证. 七、重复组合定义 从n 个不同的元素中任取r 个允许重复出现的组合称为n 个不同元素的r —可重组合.不难证明,n 个不同元素的r —可重组合的个数为rr n C 1-+.事实上,设(r a a a ,...,,21)是取自{1,2,…,n}中的任一r -可重复组合,并设r a a a ≤≤≤...21,令)1(1r i i a b i i ≤≤-+=,从而11a b =,122+=a b ,233+=a b ,…,1-+=r a b r r ,显然下面两组数是一对一的: r a a a ≤≤≤...21,11...211321-+≤-+<<+<+<≤r n r a a a a r设=A {}r i r a a a n a a a a ≤≤≤∈...},,...,2,1{|),...,,(2121,=B{}r i r b b b r n b b b b <<<-+∈...},1,...,2,1{|),...,,(2121,则由A 、B 之间存在一一对应,可知rr n C B A 1||||-+==,得证.在上述证明中,设r-可重复组合r a a a ,...,,21中含有个11x ,2x 个2,…,n x 个n ,则r x x x n =+++...21,且显然有(r a a a ,...,,21)与(n x x x ,...,,21)一一对应,因此我们立即可得:定理1 不定方程的r x x x n =+++...21非负整数解的个数为rr n C 1-+. 定理2 不定方程的r x x x n =+++...21正整数解的个数为11--n r C . 证明:令1-=i i x y ,其中1≥i x ,(n x x x ,...,,21)是已知方程的正整数解,则n r y y y n -=+++...21 (*),由定理1知,方程(*)有个正整数1111)(-------+==n r n r r n r r n n C C C 解. 【赛题解析】例1.在由n 2个小方格组成的正方形中,有多少个由整数个小方格组成的大小或位置不同的正方形? 解:由整数个小方格组成的大小位置不同的正方形可分成n 类,第k 类为k ×k 的正方形,共有2)1(+-k n 个(k=1,2,…,n),于是由加法原理得所求正方形的总个数为)12)(1(61)1(12++=+-=∑=n n n k n N nk .说明:此题将问题进行分类,直接用加法及乘法原理进行求解,两个原理是解决排列组合问题最基本的工具.例2.设整数a,b,c 为三角形三边,a+b=n ∈N,1≢c ≢n-1,求这样的整边三角形的个数 解:不妨设b ≣a ,有1≢a ≢[2n],这样的整边三角形可分为两类. 第一类:c 为最大边,令i a =,则i n b -=,n-i ≢c ≢n-1,这样的三角形有i i n n =+---1)()1(个; 第二类:c 不为最大边,则b a c c b >+>,,故i n c i n a b -<<-=-2,故112--≤≤+-i n c i n ,这样的三角形有11)12()1(-=++----i i n i n .由加法原理,使a+b=n 的整边三角形的个数为∑=-+=]2[1)1()(ni i i n f 2]2[⎪⎭⎫ ⎝⎛=n .例3.有多少个能被3整除而又含有数字6的五位数?解:易知,在由10000~99999这90000个五位数中,共有30000个可被3整除,下面先求其中不含数字6的有多少个. 这件事情可分步来完成:在最高位,不能为0和6,因此有8种可能的情况,在千、百、十位上,不能为6,各有9种可能的情况,在个位上,不能为6,且应使整个五位数能被3整除,因此所出现的数应与前4位数字之和被3除的余数有关:当该余数为2时,个位上可为1,4,7中的一个;当该余数为1时,个位上可为2,5,8中的一个;当该余数为0时,个位上可为0,3,9中的一个,总之,不论前4位数如何,个位数字都有3种可能情况.所以这类五位数的个数为8×9×9×9×3=17496,因此,含数字6而又可被3整除的五位数的个数为30000-17496=12504种可能. 例4.从1,2,3,4,……,49中取出六个不同的数字,其中至少有两个是相邻的取法种数是多少?解:设是取自1126,,,a a a ,2,3,4,……,49中的六个不同的数,不妨设126a a a <<< ,显然12345612345a a a a a a ≤-≤-≤-≤-≤-,且互不相同123456,1,2,3,4,5a a a a a a -----的充要条件是:126,,,a a a 中不含相邻的数.作六元数组126(,,,)a a a 对应于123456(,1,2,3,4,5)a a a a a a -----,则在取自1至49之间的六个不同且没有相邻的数构成的六元组集合与所有取自1至44之间的六个不同的数构成的六元组集合之间建立了一一对应,因此这两个集合中六元组的个数都为644C ,而1至49之间的六个不同的数构成的六元组的个数为649C ,于是,其中有相邻数的六元组的个数为664944C C -. 说明:本题通过对应的方法将数相邻的问题转化为元素互异的问题,从而得到求解,对应的方法是解决排列组合问题的一种常用方法.例5.如图ABC D EF 为六边形,一只青蛙开始在顶点A 处,它每次可随意跳到相邻两个顶点之一.(1)若在5次内跳到D 点,则停止跳动;若5次内不能跳到D 点,跳完5次也停止跳动.问这只青蛙从开始到停止,可能出现的不同跳法有几种?(2)若青蛙共跳12次,最终跳回到A 点的不同跳法有几种? 解:(1)由条件,青蛙的跳法只可能出现两种情况: ① 跳3次到达D 点,有2种跳法.②跳5次停止(前3次不到D 点),注意到前3次的种跳法32中,有2种到达D 点,故前3次有3226-=种跳法,而后2次有22种跳法,因此有种跳26224⨯=法.由①、②可知,共有2+24=26种不同的跳法.(2)设青蛙每逆时针跳一步记为+1,每顺时针跳一步记为-1,共跳12次,将所有这些数相加,若其和为6的倍数,则青蛙跳回A 处,若其和不为6的倍数,则青蛙不可能跳回原处,若其和为0,则必为6个+1和6个-1相加,共有种可能612C ;若其和为6,则必为9个+1和3个-1相加,共312C 种;若其和为-6,则必为3个+1和9个-1相加,共312C 种;若其和为12,则有1种可能,若其和为-12,也有一种可能,因此满足要求的不同跳法总数为种63121222C C ++.C例6.将一个四棱锥S-ABCD的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有5种颜色可供使用,那么不同的染色方法的总数是多少?解法一:由题设,四棱锥S-ABCD的顶点S、A、B所染的颜色互不相同,它们共种染35A色方法.当S、A、B已染好时,不妨设其颜色分别为1、2、3,若C染颜色2,则D可染颜色3、4、5之一,有3种染法;若C染颜色4,则D可染颜色3或5,有2种染法;若C染颜色5,则D可染颜色3或4,也有2种染法,由此可见,当S、A、B已染好时,C与D还有7种染法,从而总的染色方法数为7×35A=420种.解法二:满足题设条件的染色至少要用三种颜色.(1)若恰用三种颜色,可先从5种颜色中任选一种染顶点S,再从余下的四种颜色中任选两种染A、B、C、D四点,此时只能A与C、B与D分别同色,故有种方法60122415=⋅CCC;(2)若恰用四种颜色染色,可以先从5种颜色中任选一种染顶点S,再从余下的四种颜色中任选两种染A与B,由于A与B颜色可以交换,故有种染法24A,再从余下的两种颜色中任选一种染D或C,而D与C中另一个只需染与其相对顶点同色即可,故有种方法24012122415=CCAC;(3)若恰用5种颜色染色,易知有种染12055=A法.综上所知,满足题意的总染色方法数为60+240+120=420种.类题:(2003年高考江苏第15题)某城市在中心广场建造一个花囿,花囿分为6个部分(如图),现要栽种4种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法有______________种(以数字作答).解法一:1、2、3两两相邻,颜色应互不相同,故有种不同34A种法;1、2、3种好后,用树图方法不难得到4、5、6共有5种种法,由乘法原理得共有34A×5=120种种法.解法二:先种1,有4种颜色可选取,2、3、4、5、6形成一个圆环,要求用3种颜色涂上,且相邻的颜色不同即可转化为如下问题:将一个圆分成5个扇形,将三种颜色涂入其中,相邻的扇形涂不同的颜色.先涂1S,有三种涂法,再涂2S,有两种涂法,再涂3、4各有两种涂法,再涂5,如果只要求它与4颜色不同,则仍有两种涂法,这样共有3×2×2×2×2=48种涂法,但这48种涂法中有两类:一类5与1颜色不同,这种涂法符合题意,其数设为一5a类5与1颜色相同,这种涂法不合题意,如果把5与1合并看成一个扇形,这类涂法就相当于把圆分成4个扇形,按题设要求,其数为4a,即5a+4a=48,同理,34aa+=24,而6333==Aa,∴5a=30,故最后的结果为:30×4=120种.此问题可一般化为:把一个圆分成)2(≥nn个扇形,依次记为每,,,,21nSSS 个扇形都可用红、白、蓝三种不同颜色之任一种涂色,且三种颜色均至少用一次,要求相邻的扇形颜色互不相同,涂色法?略解:同上可得:,6,5,4,2311=⨯=+--naa nnn,63=a.若没有条件“颜色均至少用一次”,结果为,6,5,4,2311=⨯=+--naa nnn,62=a.更一般的情形是:把一个圆分成)2(≥nn个扇形,依次记为每,,,,21nSSS 个扇形都可用r种不同颜色之任一种涂色,要求相邻的扇形颜色互不相同,问有多少种涂色法?有11(1),4,5,6,nn na a r r n--+=⨯-= ,可得nnnrra)1()1)(1(-+--=说明:当我们用集合划分的方法对问题进行分类计数时,有时不可能一次性获得成功,这就需要通过建立递推关系来求解,我们把这种计数方法称为递推方法.例7.设集合A={1,2,3,…,366},如果A的一个二元子集B={a,b}满足17|a+b,则称B具有性质P.(1)求A的具有性质P的所有二元子集的个数;(2)求A的两两不相交且具有性质P的所有二元子集的个数.解:(1)a+b≡0(mod17),即a≡k(mod17)且b≡17-k(mod17),k=0,1,2, (16)将1,2,3,…,366按模17可分为17类[0],[1],…[16];因366=17×21+9,故|[1]|=|[2]|=…=|[9]|=22,|[10]|=|[11]|=…=|[16]|=|[0]|=21,欲17|a+b,当且仅当a,b∈[0]或a∈[k],b∈[17-k],当a,b∈[0]时,具有性质P的二元子集的个数为个221C;当a∈[k],b∈[17-k],k=1,2,…,7时,具有性质P的二元子集有1211227CC个;当a∈[8],b∈[9]时,具有性质P的二元子集有121121CC个;所以A的具有性质P的二元子集总个数为39287121121121122221=++CCCCC个.说明:如果把子集换成数对(a,b),则共有2×3928个.(2)为使二元子集两两不交,可作如下搭配:a,b∈[0]时,共有10个子集;a∈[k],b∈[17-k],k=1,2,…,7,有21个子集;当a∈[8],b∈[9]时,有22个子集.故A的具有性质P的两两不交的二元子集共有10+7×21=179个.例8.8个女孩和25个男孩围成一圈,任何两个女孩之间至少站两个男孩,问共有多少种不同的排列方法(只要把圈旋转一下就重合的排法认为是相同的). 解:以1个女孩和2个男孩为一组,且使女孩恰好站在两个男孩中间,余下的9个男孩和这8个组被看成是17个元素,显然这17个元素任意的圆排列数为1616A 种再次,分在8个组内的16个男孩在16个位置上的排列是1616A ,所以总的排列方法数为:16161616925A A C .说明:此题为圆排列问题.例9.试求从集合{}n A ,...,2,1=到集合的映{}m B ,...,2,1=射的个数.解:由映射的定义知,每一个到B 的映射对应着个不同元m 素的n -可重排列,故从A 到B 的映射的个数为n m .例10.一段楼梯共有12级台阶,某人上楼时,有时一步迈一台阶,有时一步迈两台阶,问此人共有多少种上楼的方法? 解:现将“一步迈两级台阶”这一动作记为a ,因为楼梯共有12级台阶,故动作a 至多只能做6次;再记“一步迈一级台阶”的动作为b ,则上楼的整个过程由k 个a 及12-2k 个b 组成,这里k 可取0,1,2,3,4,5,6,对于某个k ,其全排列数为:)!212(!]!212([k k k k --+)!212(!)!12(k k k --=,因此,上楼的方法共有:∑=--60)!212(!)!12(k k k k =233种. 解法2:以k =4为例,即4个两级,4个一级,相当于共8步,其中有四步为两级,即相当于从8步中选4步跨两级,其余跨一级,故结果应为48C ;一般地上楼的整个过程由k 个a 及12-2k 个b 组成,相当于共跨k +(12-2k )=12-k 步,其中有k 步为a ,故结果为kkC-12,这里k 可取0,1,2,3,4,5,6,故最终结果为∑=-612k kkC.解法3:设走n 次台阶的方法总数为n a ,对每种走法可划分为两类第一类:第一步走1级,有1-n a 种走法;第二类:第一步走2级,有2-n a 种走法,故21--+=n n n a a a ,且2,121==a a ,故易得23312=a .因Fibo nacci 数列}{n F 满足2,1321===F F F ,故1+=n n F a ,由上面的一些方法还可知:∑=--=]2[01nk kk n n C F . 若将所跨的每一级台阶,此人均用红、白两种颜色做上记号,则标有不同颜色的路线共有∑=---=⋅]2[02132n i i n i i n n C种,其递推关系式为5,2,22121==-=--a a a a a n n n .例11.把n 个不同的球,分别装入m 个盒子中,使其中个盒1m 子中每个都有1p 个球,2m 个盒子中每个都有个球2p ,…,km 个盒子中每个都有个球kp ,这里,k k k m p m p m p n m m m m +++=+++=...,...221121,求下列情况下,各有多少种不同放法:(1)盒子均不相同;(2)装有相同数目的球的盒子相同.解:(1)这是一个将n 个不同元素分为m组的多组组合,故不同的放法数有k m k m m p p p n f )!...()!()!(!2121=; (2)因为相同数目的球的盒子相同(不加区别),故所求放法数为!!..!21k m m m f.例12.电视台在n 天内共播出r 次商业广告,问若每天至少播p 次广告(r np ≤),就每天播出广告的次数而言,共有几种播出方法?解:设第天播出i 广告i x 次,由题设知:r x x x n =+++...21,),...,2,1(n i p x i =≥,令p x y i i -=,则0...21≥-=+++np r y y y n ,故问题转化为求上述不定方程的非负整数解的个数,从而知广告播放的方法数为npr n np r C --+-1)(.巩 固 练 习1.n 名同学(n ≣3)站成一圈,其中A 、B 两人不能相邻的站法有多少种?解:n 名同学站成一圈有(n-1)!种站法,其中使A 、B 相邻的站法有2×(n-2)!种,从而A 、B 不相邻的站法为(n -1)!-2×(n-2)!=(n-3)(n-2)!种站法.2.设集合A 、B 的并集为一个n 元集,A ≠B .(1) 若(A ,B )与(B ,A )视为不同的对,则这样的A 、B 共有多少个? (2) 若(A ,B )与(B ,A )视为相同的对,则这样的A 、B 共有多少个?解:(1)设集合A 中有k 个元素,则集合B 中必含有A 中没有的n-k 个元素,再加上A 的k 个元素中取0个、1个、…k 个,故共有kknC 2个,故总数为∑=nk kknC 02=n 3个,除去A 与B相同(均为全集)的1个,共n 3-1个;(2)由题意,(A ,B )与(B ,A )一一对应,故结果为个)13(21-n .3.在一个正六边形的六个区域栽种观赏植物,如图,要求同一块中种同一植物,相邻的两块种不同的植物,现有4种不同的植物可供选择,则有多少种不同的栽种方案.解:考虑A 、C 、E 种同一种植物,此时共有4×3×3×3=108种;考虑A 、C 、E 种两种植物,此时共有3×4×3×3×2×2=432种方法;考虑A 、C 、E 种三种植物,此时共有34C ×2×2×2=192种方法;故总计有108+432+192=732种方案.4.如图,矩形ABC D 的边在网格线上,并且AB 是A D 的k 倍(k 为正整数),考虑沿网格的边从A 到C 所有可能的最短路径.证明:在这些路径中,含AB1的条数是含A D 1的条数的k 倍.解:含AB1的最短路径,除AB1外,还应含横向的m-1节,纵向的n 节,因此共有条1nm n C +-,同理,含AD1的最短路径有1mm n C +-条,而11!(1)!!(1)!nm n mm n Cm n m k Cn m n +-+--===-,因此命题得证.5.马路上有编号为1,2,3,…,2005的2005只路灯,为节约用电,现要求把其中的200只灯关掉,但不能同时关掉相邻的两只或三只,也不能关掉两端的路灯,求满足条件的关灯方法共有多少种?解:任意一种关灯的方法,都对应着一种满足题设条件的亮灯与暗灯的排列,于是总是转化为1805只亮灯中插入200只暗灯,且任何两只暗灯不相邻,而且不在两端,也就是在1805只亮灯所形成的1804个间隙中选200个插入暗灯,其方法有种2001804C .6.把2005个不加区别的小球分别放在10个不同的盒子里,使得第i 个盒子中至少有i 个球)10,...,2,1(=i ,问不同放法的总数是多少? 解:先在第个盒i 子里放入个i 球,这时共放了1+2+…+10=55个球,还余下2005-55=1950个球,故问题转化为把1950个球任意放入10个盒子(允许有的盒子不放球),相当于一个不定方程的非负整数解的个数问题,共有195019509101950119591959C C C +-==种.7.n 个人站成一)3(≥n 圈,其中某指定的两人A 、B 肯定不相邻的站法有多少种? 答案:)!2(2)!1(---n n .8.甲、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛,双方先由一号队员比赛,负者被淘汰,胜者再与负方2号队员比赛,……,直到一方队员全部淘汰为止,另一方获得胜利,形成一种比赛过程,那么所有可能出现的比赛过程的种数是多少?解:不妨先设甲方胜出,则问题等价于求方程的7...721=+++x x x 非负整数解的个数,有6137177C C =-+种,同理,乙方胜的比赛过程也有6137177C C =-+种,故可能出现的比赛过程有6132C 种. 9.有男生m n +人,女生m 人(1,≥n m ),(1)这个人排成m n 2+一列,女生不相邻,首尾都是男生,有多少种排法? (2))这个人围成m n 2+一圈,女生不相邻,有多少种排法?解:(1)m m n A m n 1)!(-++;(2)先作男生圆排列,然后插入,共mm n A m n +-+)!1(.10.方程的非负3...210321=++++x x x x 整数解共有多少个? 解:由题意,1,01=x ,故分情况讨论如下:若01=x ,则3...1032=+++x x x ,非负整数解的个数为:1653139=-+C ; 若11=x ,则1...1032=+++x x x ,非负整数解的个数为:91119=-+C .综上,非负整数解的个数为:165+9=174个.11.一个盒子里有7个分别标有号码1,2,…,7的球,每次取出一个,记下它的号码后再放回盒子,共取(放)4次,求4次中最大标号恰是5的取法数?解:最大标号为5,相当于从1,2,…,5中取,共取(放)4次,共有种取法45;从中剔除四次中最大标号均不是5的种数,结果为4544-=369.12.已知集合{}2,,,|12≥∈∈==-n N n C z z z z A n ,在复平面上,以A 中的复数的对应点为顶点可构成多少个直角三角形?解:易求得{}122,,,1,0-=n A εεε ,其中nieπε=(n ≣2)设各复数在复平面上对应点依次为O 、A 0、A 1、A 2、…、A 2n-1,则A0A1A 2…A 2n-1为正2n 边形,易知在中以j i A OA ∆j i A A ,为顶点的内角均为锐角,所以,由O 、A 0、A 1、A 2、…、A 2n-1为顶点的直角三角形可分为两类: 第一类:以O 为直角顶点的直角三角形,不失一般性,可设︒=∠900K OA A ,则nk ππ=2,所以)(2N k k n ∈=,这说明这类直角三角形存在当且仅当n 为偶数时,这时,这样的直角三角形有2n 个;第二类:不以O 为直角顶点的直角三角形这样的直角三角形的顶点均匀分布在单位圆周上,即由A 0、A 1、A 2、…、A 2n-1构成,这些点可确定n 条直径,于是可构成)22(-n n 个直角三角形综上所述,由加法原理,所求直角三角形的总个数为⎩⎨⎧-=+-=为奇数为偶数n n n n n n n n n f ),1(2,22)22()(2.。
一、方法与例题1.抽屉原理。
例1 设整数n ≥4,a 1,a 2,…,a n 是区间(0,2n)内n 个不同的整数,证明:存在集合{a 1,a 2,…,a n }的一个子集,它的所有元素之和能被2n 整除。
[证明] (1)若n ∉{a 1,a 2,…,a n },则n 个不同的数属于n-1个集合{1,2n-1},{2,2n-2},…,{n-1,n+1}。
由抽屉原理知其中必存在两个数a i ,a j (i ≠j)属于同一集合,从而a i +a j =2n 被2n 整除;(2)若n ∈{a 1,a 2,…,a n },不妨设a n =n ,从a 1,a 2,…,a n-1(n-1≥3)中任意取3个数a i , a j , a k (a i ,<a j < a k ),则a j -a i 与a k -a i 中至少有一个不被n 整除,否则a k -a i =(a k -a j )+(a j -a i )≥2n ,这与a k ∈(0,2n)矛盾,故a 1,a 2,…,a n-1中必有两个数之差不被n 整除;不妨设a 1与a 2之差(a 2-a 1>0)不被n 整除,考虑n 个数a 1,a 2,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a n-1。
ⅰ)若这n 个数中有一个被n 整除,设此数等于k n ,若k 为偶数,则结论成立;若k 为奇数,则加上a n =n 知结论成立。
ⅱ)若这n 个数中没有一个被n 整除,则它们除以n 的余数只能取1,2,…,n-1这n-1个值,由抽屉原理知其中必有两个数除以n 的余数相同,它们之差被n 整除,而a 2-a 1不被n 整除,故这个差必为a i , a j , a k-1中若干个数之和,同ⅰ)可知结论成立。
2 极端原理。
例2 在n ×n 的方格表的每个小方格内写有一个非负整数,并且在某一行和某一列的交叉点处如果写有0,那么该行与该列所填的所有数之和不小于n 。
证明:表中所有数之和不小于221n 。
[证明] 计算各行的和、各列的和,这2n 个和中必有最小的,不妨设第m 行的和最小,记和为k ,则该行中至少有n-k 个0,这n-k 个0所在的各列的和都不小于n-k ,从而这n-k 列的数的总和不小于(n-k)2,其余各列的数的总和不小于k 2,从而表中所有数的总和不小于(n-k)2+k 2≥.212)(22n k k n =+- 3.不变量原理。
俗话说,变化的是现象,不变的是本质,某一事情反复地进行,寻找不变量是一种策略。
例3 设正整数n 是奇数,在黑板上写下数1,2,…,2n ,然后取其中任意两个数a,b,擦去这两个数,并写上|a-b|。
证明:最后留下的是一个奇数。
[证明] 设S 是黑板上所有数的和,开始时和数是S=1+2+…+2n=n(2n+1),这是一个奇数,因为|a-b|与a+b 有相同的奇偶性,故整个变化过程中S 的奇偶性不变,故最后结果为奇数。
例4 数a 1, a 2,…,a n 中每一个是1或-1,并且有S=a 1a 2a 3a 4+ a 2a 3a 4a 5+…+a n a 1a 2a 3=0. 证明:4|n.[证明] 如果把a 1, a 2,…,a n 中任意一个a i 换成-a i ,因为有4个循环相邻的项都改变符号,S 模4并不改变,开始时S=0,即S ≡0,即S ≡0(mod4)。
经有限次变号可将每个a i 都变成1,而始终有S ≡0(mod4),从而有n ≡0(mod4),所以4|n 。
4.构造法。
例5 是否存在一个无穷正整数数列a 1,<a 2<a 3<…,使得对任意整数A ,数列∞=+1}{n n A a 中仅有有限个素数。
[证明] 存在。
取a n =(n!)3即可。
当A=0时,{a n }中没有素数;当|A|≥2时,若n ≥|A|,则a n +A 均为|A|的倍数且大于|A|,不可能为素数;当A=±1时,a n ±1=(n!±1)•[(n!)2±n!+1],当≥3时均为合数。
从而当A 为整数时,{(n!)3+A}中只有有限个素数。
例6 一个多面体共有偶数条棱,试证:可以在它的每条棱上标上一个箭头,使得对每个顶点,指向它的箭头数目是偶数。
[证明] 首先任意给每条棱一个箭头,如果此时对每个顶点,指向它的箭头数均为偶数,则命题成立。
若有某个顶点A,指向它的箭头数为奇数,则必存在另一个顶点B,指向它的箭头数也为奇数(因为棱总数为偶数),对于顶点A与B,总有一条由棱组成的“路径”连结它们,对该路径上的每条棱,改变它们箭头的方向,于是对于该路径上除A,B外的每个顶点,指向它的箭头数的奇偶性不变,而对顶点A,B,指向它的箭头数变成了偶数。
如果这时仍有顶点,指向它的箭头数为奇数,那么重复上述做法,又可以减少两个这样的顶点,由于多面体顶点数有限,经过有限次调整,总能使和是对每个顶点,指向它的箭头数为偶数。
命题成立。
5.染色法。
例7 能否在5×5方格表内找到一条线路,它由某格中心出发,经过每个方格恰好一次,再回到出发点,并且途中不经过任何方格的顶点?[解] 不可能。
将方格表黑白相间染色,不妨设黑格为13个,白格为12个,如果能实现,因黑白格交替出现,黑白格数目应相等,得出矛盾,故不可能。
6.凸包的使用。
给定平面点集A,能盖住A的最小的凸图形,称为A的凸包。
例8 试证:任何不自交的五边形都位于它的某条边的同一侧。
[证明] 五边形的凸五包是凸五边形、凸四边形或者是三角形,凸包的顶点中至少有3点是原五边形的顶点。
五边形共有5个顶点,故3个顶点中必有两点是相邻顶点。
连结这两点的边即为所求。
7.赋值方法。
例9 由2×2的方格纸去掉一个方格余下的图形称为拐形,用这种拐形去覆盖5×7的方格板,每个拐形恰覆盖3个方格,可以重叠但不能超出方格板的边界,问:能否使方格板上每个方格被覆盖的层数都相同?说明理由。
[解] 将5×7方格板的每一个小方格内填写数-2和1。
如图18-1所示,每个拐形覆盖的三个数之和为非负。
因而无论用多少个拐形覆盖多少次,盖住的所有数字之和都是非负的。
另一方面,方格板上数字的总和为12×(-2)+23×1=-1,当被覆盖K层时,盖住的数字之和等于8.图论方法。
例10 生产由六种颜色的纱线织成的双色布,在所生产的双色布中,每种颜色的纱线至少与其他三种颜色的纱线搭配过。
证明:可以挑出三种不同的双色布,它们包含所有的颜色。
[证明] 用点A1,A2,A3,A4,A5,A6表示六种颜色,若两种颜色的线搭配过,则在相应的两点之间连一条边。
由已知,每个顶点至少连出三条边。
命题等价于由这些边和点构成的图中有三条边两两不相邻(即无公共顶点)。
因为每个顶点的次数≥3,所以可以找到两条边不相邻,设为A1A2,A3A4。
(1)若A5与A6连有一条边,则A1A2,A3A4,A5A6对应的三种双色布满足要求。
(2)若A5与A6之间没有边相连,不妨设A5和A1相连,A2与A3相连,若A4和A6相连,则A1A2,A3A4,A5A6对应的双色布满足要求;若A4与A6不相连,则A6与A1相连,A2与A3相连,A1A5,A2A6,A3A4对应的双色布满足要求。
综上,命题得证。
二、习题精选1.药房里有若干种药,其中一部分药是烈性的。
药剂师用这些药配成68副药方,每副药方中恰有5种药,其中至少有一种是烈性的,并且使得任选3种药恰有一副药方包含它们。
试问:全部药方中是否一定有一副药方至少含有4种烈性药?(证明或否定)2.21个女孩和21个男孩参加一次数学竞赛,(1)每一个参赛者最多解出6道题;(2)对每一个女孩和每一个男孩至少有一道题被这一对孩子都解出。
求证:有一道题至少有3个女孩和至少有3个男孩都解出。
3.求证:存在无穷多个正整数n ,使得可将3n 个数1, 2,…, 3n 排成数表a 1, a 2…a nb 1, b 2…b nc 1, c 2…c n满足:(1)a 1+b 1+c 1= a 2+b 2+c 2=…= a n +b n +c n =,且为6的倍数。
(2)a 1+a 2+…+a n = b 1+b 2+…+b n = c 1+c 2+…+c n =,且为6的倍数。
4.给定正整数n ,已知克数都是正整数的k 块砝码和一台天平可以称出质量为1,2,…,n 克的所有物品,求k 的最小值f(n)。
5.空间中有1989个点,其中任何3点都不共线,把它们分成点数各不相同的30组,在任何3个不同的组中各取一点为顶点作三角形。
试问:为使这种三角形的总数最大,各组的点数应分别为多少?6.在平面给定点A 0和n 个向量a 1,a 2,…,a n ,且使a 1+a 2+…+a n =0。
这组向量的每一个排列n i i i a a a ,,,21Λ都定义一个点集:A 1,A 2,…,A n =A 0,使得n n i i i A A a A A a A A a n12110,,,21-===Λ求证:存在一个排列,使由它定义的所有点A 1,A 2,…,A n-1都在以A 0为角顶的某个600角的内部和边上。
7.设m, n, k ∈N ,有4个酒杯,容量分别为m,n,k 和m+n+k 升,允许进行如下操作:将一个杯中的酒倒入另一杯中或者将另一杯倒满为止。
开始时,大杯中装满酒而另3个杯子却空着,问:为使对任何S ∈N ,S<m+n+k ,都可经过若干次操作,使得某个杯子中恰有S 升酒的关于m,n,k 的充分必要条件是什么?8.设有30个人坐在一张圆桌的周围,其中的每个人都或者是白痴,或者是聪明人。
对在座的每个人都提问:“你右边的邻座是聪明人还是白痴?”聪明人总是给出正确的答案,而白痴既可能回答正确,也可能回答不正确。
已知白痴的个数不超过F ,求总可以指出一位聪明人的最大的F 。
9.某班共有30名学生,每名学生在班内都有同样多的朋友,期末时任何两人的成绩都可分出优劣,没有相同的。
问:比自己的多半朋友的成绩都要好的学生最多能有多少人?。