初中综合题目选讲

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合试题选讲,05,初中（,1,）,江苏省常州高级中学 周敏泽,简单的组合问题：,如图，每个正方体的六个面上分别写着数字,1,，,2,，,3,，,4,，,5,，,6,，并且任意两个相对的面上所写的两个数字之和都等于,7,。把这样的,4,个正方体一个挨着一个连接起来后，紧挨着的两个面上的数字之和都等于,8,。图中标着,x,的那个面上所写的数字是几？,分析：拐角处正方体前后分别为,4,，,3,，则右侧面可能是,1,或,6,，而,1,不能使,x,面的对面数字为,7,，故只能为,6,，所以,x,的对面数字为,2,，所以，,x,=5,。,2,2,x,组合数学是上个世纪五十年代后逐步建立和完善起来的一门数学分支，组合数学也称为组合学、组合论，组合分析。教科书上对组合分析的定义：,按某种要求把一些元素构成有限集合的研究叫做组合分析,。,这种研究比传统的数学讨论的对象更广泛，在实际生活和实践活动中应用性更大。这种研究一般讨论以下问题：在一定的约束条件下，,对象,构成的存在性,（有与没有、能与不能）问题,；,构成的分类与计数,；,构成的方法（,构造方法,）,及,最优化方法,。,人们常把竞赛中某些问题称为杂题，又称为组合数学问题。为什么？,中学数学竞赛中的一些问题，很难把它们归类为代数问题或几何问题，但它们涉及到的解题目标和解题方法可以归入组合问题和组合分析；当然一些组合数学的习题也直接用作竞赛题。,初等数学竞赛中的组合问题与组合分析常用的方法有抽屉原理、递推（归）原理、容斥原理、染色方法等，这些原理方法都很一般，重要的是经验和技巧,应用的能力。,从,04,年江苏初中数学竞赛的两个组合试题说起,1,空间,6,个点,(,任意三点不共线,),两两连线。现用红、蓝两色染这些线段。其中点,A,连出来的线段都是红色的。那么，以这,6,个点为顶点的三角形中，三边同色的三角形至少有（）,A,3,个,B,4,个,C,5,个,D,6,个,分析：与著名的赛题有联系,分类方法中的二分表述：,分类方法中的二分表述：,分类法：总体情况可分情况一，情况二，,情况,N,；,若情况一，则,；,若情况二，则,；,；,若情况,N,，则,，综上，则,。,二分表述：,若情况,A,，则,；否则，若情况,A,不成立时，则,；,综上，则,。,著名的赛题,证明：任意六个人中，总有三个人，要么相互认识，要么相互不认识。,A,3,A,2,A,1,A,6,A,5,A,4,同色分析三步：把实际问题转化为图形染色；抽屉原理；二分法推理。,证明：圆上六个点,A,1,A,2,A,3,A,4,A,5,A,6,表示六个人，两人相互认识，相应两点间连红线，两人不相识，相应两点间连蓝线，原命题即为证明存在三边同色的三角形。,与,A,1,相连的,5,条线分别染两种颜色，至少有三条线同色。不妨设至少有三条红线，且为,A,1,A,2,、,A,1,A,3,、,A,1,A,4,。,若,A,2,、,A,3,、,A,4,三点间的连线有一条红线，则有红色三角形；,否则,，三条连线都是蓝线，存在蓝色三角形。,圆周上若有,5,个点，每两个点间连红线或蓝线，最少存在多少个同色三角形？,A,C,E,D,B,1,空间,6,个点,(,任意三点不共线,),两两连线。现用红、蓝两色染这些线段。其中点,A,连出来的线段都是红色的。那么，以这,6,个点为顶点的三角形中，三边同色的三角形至少有（）,A,3,个,B,4,个,C,5,个,D,6,个,分析：另外,5,点连线均为蓝色线段，有,10,个同色三角形；,连线中有一条红线，有,1+7=8,个同色三角形；,连线中有两条红色线，分有无公共端点，至少有,2+4=6,个三角形；,*若有,6,个人聚会，其中任意两个人要么相互认识，要么相互不认识。,证明：一定存在两个三人组，每个组中的三个人，要么相互都认识，要么相互都不认识。,A,3,A,2,A,1,A,6,A,5,A,4,分析：可以用同色分析法，但不易；试用计算分析。,证明：用圆周上六个点表示六个人，两人相识相应两点间连红线，不相识连蓝线。定义过一点的两条边颜色相同的角为同色角，过一点两边颜色不同的角为异色角；三边同色的三角形为同色三角形，三边不同色的三角形为异色三角形。,每个圆周角只在一个圆内接三角形中，不能成为两个三角形的公共角。一个圆内接三角形中，异色角恰好有两个。,整个图中异色角最多有,36,个，最多可以构成,18,个异色三角形。以圆周上这六个点为顶点的三角形共有,20,个，故最少有两个同色三角形，命题得证。,*圆周上若有,9,个点，每两个点间连红线或蓝线，至少存在,个同色三角形。,设过点,A,i,的红线有,x,i,条，蓝线有,5-,x,i,条，则过点,A,i,的异色角有,x,i,(5-,x,i,),，,x,i,=0,，,1,，,2,，,3,，,4,，,5,。所以过,A,i,的异色角最多有,6,个。,1,、计数中求最大值：,第一步：分类讨论,（,1,）情况一，推出目标数,f m,1,；,（,2,）情况二，推出目标数,f m,2,；,（,s,）情况,s,，推出目标数,f m,s,；,第二步：,m,0,=maxm,1,，,m,2,，,，,m,s,，,则,f m,0,；,第三步：构造模型使计数恰好等于常数,m,0,，,则常数,m,0,即为最大值。,另一种叙述,第,1,步：由目标数,f,m,推出可以符合条件；,第,2,步：由,f,=,m,+1,推出是不能符合条件；,所以,f,max,=,m,。,2,、计数中求最小值：,第一步：分类讨论,（,1,）情况一，推出目标数,f m,1,；,（,2,）情况二，推出目标数,f m,2,；,（,s,）情况,s,，推出目标数,f m,s,；,第二步：,m,0,=minm,1,，,m,2,，,，,m,s,，,则,f m,0,；,第三步：构造模型使计数恰好等于常数,m,0,，,则常数,m,0,即为最小值。,另一种叙述,第一步：由目标数,f,m,推出可以；,第二步：由目标数,f,=,m,1,推出不能；,所以,f,min,=,m,。,2.,由,9,位裁判给参加健美比赛的,12,名运动员评分。每位裁判对他认为的第一名运动员给,1,分，第二名运动员给,2,分，,，第,12,名运动员给,12,分。最后评分结果显示：每名运动员所得的,9,个分数中高低分之差都不大于,3,分。设各运动员的得分总和分别为,e,1,，,e,2,，,e,3,，,e,12,，且,e,1,e,2,e,3,e,12,，求,e,1,的最大值。,2-1,在,20,名花样滑冰运动员表演完以后，,9,名裁判员分别给他们判定从,1,到,20,的名次，若每一个运动员得到的名次中，最大值与最小值的差不能超过,3,，将每个运动员所得的名次的和排成递增序列：,C,1,C,2,C,20,。,问：,C,1,可能取得的最大值是几？,2.,由,9,位裁判给参加健美比赛的,12,名运动员评分。每位裁判对他认为的第一名运动员给,1,分，第二名运动员给,2,分，,，第,12,名运动员给,12,分。最后评分结果显示：每名运动员所得的,9,个分数中高低分之差都不大于,3,分。设各运动员的得分总和分别为,e,1,，,e,2,，,e,3,，,e,12,，且,e,1,e,2,e,3,e,12,，求,e,1,的最大值。,12,11,10,分析：含,1,分的格子最多有,4,列，此,4,列的每格数字平均不超过,22.5,，,3,列呢？,2,列？,1,列？,解：对,9,个,1,分布的列数进行讨论：,（,1,）,1,分分布在同一列，该列的和为,9,，,e,1,=9;,（,2,）,1,分恰在两列中，列中数字不超过,4,，两列的和最大为,59=45,，,较小,的列和,452,，是整数，则,较小,的列和,22,，故,最小,的列和,e,1,22(21);,（,3,）,1,分恰在三列中，列中数字不超过,4,，三列的和最大为,89=72,，同理,e,1,24;,（,4,）,1,分恰在四列中，列中数字不超过,4,，四列的和最大为,109=90,，同理,e,1,22;,（,5,）,1,分恰在,5,列中，,5,列,45,个数都只能取,1,、,2,、,3,、,4,，,9,个裁判只能给出,9,个,1,、,2,、,3,、,4,，共,36,个，填不满,5,列；同理，,1,分不能分布在比,5,更多的列中。所以，,1,最多能在,4,列中。,故,e,1,24,。,若前三列中，每列三个,1,、三个,3,、三个,4,，每列的和都是,24,，第四列,5,个,2,，,4,个,5,，和为,30,；第五列,4,个,2,，,5,个,5,，和为,33,；以后第,k,列填,9,个,k,，和为,9,k,54,。则,e,1,=24,。,所以,e,1,的最大值为,24,。,3.,有两副扑克牌，每副牌的排列顺序是：第一张是大王，第二张是小王，然后是黑桃、红桃、方块、梅花,4,种花色排列，每种花色的牌又按,A,，,2,，,3,，,，,J,，,Q,，,K,的顺序排列。某人把按上述排列的两副扑克牌上下叠在一起，然后从上到下把第一张丢掉，把第二张放在最底层，把第三张丢掉，把第四张放在最底层,，如此下去，直至最后剩下一张牌。则所剩的这张牌是什么？,分析,:,有一个小学的竞赛题，称为“做数学”。请先欣赏。,3-1.,依顺时针方向将数字,1,，,2,，,3,，,4,，,5,，,6,，,7,写在圆周上。首先将数字,1,删除，然后每次跳过一个未删除的数，删除被跳到位置上的数，依此方法继续进行直到最后只剩下一个数为止。例如，,删除数字,1,，跳过数字,2,；,删除数字,3,，跳过数字,4,；,删除数字,5,，跳过数字,6,；,删除数字,7,，跳过数字,2,；,删除数字,4,，跳过数字,6,；,删除数字,2,，所以，剩下最后的一个数是,6,。,如果依顺时针方向将,1,，,2,，,3,，,，,2004,写在圆周上，并依照上述规则操作，试问最后剩下的一个数为,。,7,6,5,4,3,1,2,解：第一圈,:,从,1,开始，删去所有奇数，余下,2k,型数：,2,，,4,，,6,，,8,，,2002,，,2004,；,第二圈,:,从,2,开始，删去所有,4k-2,型数，余下,4k,型数：,4,，,8,，,12,，,16,，,2000,，,2004,；,第三圈,:,从,4,开始，删去所有,8k+4,型数，余下,8k,型数：,8,，,16,，,24,，,1992,，,2000,；,第四圈,:,从,16,开始，删去所有,16k,型数，余下,16k-8,型数：,8,，,24,，,40,，,1976,，,1992,；,第五圈,:,从,24,开始，删去所有,32k-8,型数，余下,32k-24,型数：,8,，,40,，,721960,，,1992,；,第六圈,:,从,8,开始，删去所有,64k-56,型数，余下,64k-24,型数：,40,，,104,，,1896,，,1960,；,第六圈,:,从,8,开始，删去所有,64k-56,型数，余,64k-24,型数：,40,，,104,，,1896,，,1960,；,第七圈,:,从,104,起，删去所有,128k-24,型数，余,128k-88,型数：,40,，,168,，,296,，,424,，,552,，,680,，,808,，,936,，,1064,，,1192,，,1320,，,1448,，,1576,，,1704,，,1832,，,1960,；,第八圈,:,从,40,起，删去所有,256k-216,型数，余,256k-88,型数：,168,，,424,，,680,，,936,，,1192,，,1448,，,1704,，,1960,；,第九圈,:,从,168,起,删去所有,512k-344,型数，余,512k-88,型数：,424,，,936,，,1448,，,1960,；,第十圈