组合试题选讲05初中.ppt

组合试题选讲05初中（1）,江苏省常州高级中学 周敏泽,简单的组合问题： 如图，每个正方体的六个面上分别写着数字1，2，3，4，5，6，并且任意两个相对的面上所写的两个数字之和都等于7。把这样的4个正方体一个挨着一个连接起来后，紧挨着的两个面上的数字之和都等于8。图中标着 x 的那个面上所写的数字是几？,分析：拐角处正方体前后分别为4，3，则右侧面可能是1或6，而1不能使x面的对面数字为7，故只能为6，所以x的对面数字为2，所以，x=5。,组合数学是上个世纪五十年代后逐步建立和完善起来的一门数学分支，组合数学也称为组合学、组合论，组合分析。教科书上对组合分析的定义：按某种要求把一些元素构成有限集合的研究叫做组合分析。 这种研究比传统的数学讨论的对象更广泛，在实际生活和实践活动中应用性更大。这种研究一般讨论以下问题：在一定的约束条件下，对象构成的存在性（有与没有、能与不能）问题；构成的分类与计数；构成的方法（构造方法）及最优化方法。,人们常把竞赛中某些问题称为杂题，又称为组合数学问题。为什么？ 中学数学竞赛中的一些问题，很难把它们归类为代数问题或几何问题，但它们涉及到的解题目标和解题方法可以归入组合问题和组合分析；当然一些组合数学的习题也直接用作竞赛题。,初等数学竞赛中的组合问题与组合分析常用的方法有抽屉原理、递推（归）原理、容斥原理、染色方法等，这些原理方法都很一般，重要的是经验和技巧应用的能力。,从04年江苏初中数学竞赛的两个组合试题说起 1空间6个点(任意三点不共线)两两连线。现用红、蓝两色染这些线段。其中点A连出来的线段都是红色的。那么，以这6个点为顶点的三角形中，三边同色的三角形至少有（ ） A3个 B4个 C5个 D6个,分析：与著名的赛题有联系 分类方法中的二分表述：,分类方法中的二分表述： 分类法：总体情况可分情况一，情况二，情况N； 若情况一，则； 若情况二，则； ； 若情况N，则， 综上，则。 二分表述： 若情况A，则；否则，若情况A不成立时，则； 综上，则。,著名的赛题证明：任意六个人中，总有三个人，要么相互认识，要么相互不认识。,同色分析三步：把实际问题转化为图形染色；抽屉原理；二分法推理。,证明：圆上六个点A1A2A3A4A5A6表示六个人，两人相互认识，相应两点间连红线，两人不相识，相应两点间连蓝线，原命题即为证明存在三边同色的三角形。,与A1相连的5条线分别染两种颜色，至少有三条线同色。不妨设至少有三条红线，且为A1A2、A1A3、A1A4。若A2、A3、A4三点间的连线有一条红线，则有红色三角形；否则，三条连线都是蓝线，存在蓝色三角形。,圆周上若有5个点，每两个点间连红线或蓝线，最少存在多少个同色三角形？,1空间6个点(任意三点不共线)两两连线。现用红、蓝两色染这些线段。其中点A连出来的线段都是红色的。那么，以这6个点为顶点的三角形中，三边同色的三角形至少有（ ） A3个 B4个 C5个 D6个,分析：另外5点连线均为蓝色线段，有10个同色三角形； 连线中有一条红线，有1+7=8个同色三角形； 连线中有两条红色线，分有无公共端点，至少有2+4=6个三角形；,* 若有6个人聚会，其中任意两个人要么相互认识，要么相互不认识。 证明：一定存在两个三人组，每个组中的三个人，要么相互都认识，要么相互都不认识。,分析：可以用同色分析法，但不易；试用计算分析。,证明：用圆周上六个点表示六个人，两人相识相应两点间连红线，不相识连蓝线。定义过一点的两条边颜色相同的角为同色角，过一点两边颜色不同的角为异色角；三边同色的三角形为同色三角形，三边不同色的三角形为异色三角形。,每个圆周角只在一个圆内接三角形中，不能成为两个三角形的公共角。一个圆内接三角形中，异色角恰好有两个。,整个图中异色角最多有36个，最多可以构成18个异色三角形。以圆周上这六个点为顶点的三角形共有20个，故最少有两个同色三角形，命题得证。,* 圆周上若有9个点，每两个点间连红线或蓝线，至少存在 个同色三角形。,设过点Ai的红线有xi 条，蓝线有5-xi 条，则过点Ai的异色角有xi (5-xi)，xi=0，1，2，3，4，5。所以过Ai的异色角最多有6个。,1、计数中求最大值： 第一步：分类讨论 （1）情况一，推出目标数 f m1； （2）情况二，推出目标数 f m2； （s）情况s，推出目标数 f ms； 第二步：m0=maxm1，m2，ms， 则f m0； 第三步：构造模型使计数恰好等于常数 m0， 则常数 m0 即为最大值。 另一种叙述第1步：由目标数 f m推出可以符合条件； 第2步： 由f =m+1推出是不能符合条件； 所以 fmax=m 。,2、计数中求最小值： 第一步：分类讨论 （1）情况一，推出目标数 f m1； （2）情况二，推出目标数 f m2； （s）情况s，推出目标数 f ms； 第二步：m0=minm1，m2，ms， 则f m0； 第三步：构造模型使计数恰好等于常数 m0， 则常数 m0 即为最小值。 另一种叙述第一步：由目标数 f m推出可以； 第二步：由目标数f =m1推出不能； 所以 fmin=m 。,2. 由9位裁判给参加健美比赛的12名运动员评分。每位裁判对他认为的第一名运动员给1分，第二名运动员给2分，第12名运动员给12分。最后评分结果显示：每名运动员所得的9个分数中高低分之差都不大于3分。设各运动员的得分总和分别为e1，e2，e3，,e12，且e1e2e3e12，求e1 的最大值。,2-1在20名花样滑冰运动员表演完以后，9名裁判员分别给他们判定从1到20的名次，若每一个运动员得到的名次中，最大值与最小值的差不能超过3，将每个运动员所得的名次的和排成递增序列：C1C2C20 。 问：C1可能取得的最大值是几？,2. 由9位裁判给参加健美比赛的12名运动员评分。每位裁判对他认为的第一名运动员给1分，第二名运动员给2分，第12名运动员给12分。最后评分结果显示：每名运动员所得的9个分数中高低分之差都不大于3分。设各运动员的得分总和分别为e1，e2，e3，,e12，且e1e2e3e12，求e1 的最大值。,分析：含1分的格子最多有4列，此4列的每格数字平均不超过22.5，3列呢？2列？1列？,解：对9个1分布的列数进行讨论： （1）1分分布在同一列，该列的和为 9，e1= 9; （2）1分恰在两列中，列中数字不超过4，两列的和最大为59=45，较小的列和452，是整数，则较小的列和22， 故最小的列和e122(21); （3）1分恰在三列中，列中数字不超过4，三列的和最大为89=72，同理 e124; （4）1分恰在四列中，列中数字不超过4，四列的和最大为109=90，同理 e122;,（5）1分恰在5列中，5列45个数都只能取1、2、3、4，9个裁判只能给出9个1、2、3、4，共36个，填不满5列；同理，1分不能分布在比5更多的列中。所以，1 最多能在4列中。 故 e124。,若前三列中，每列三个1、三个3、三个4，每列的和都是24，第四列5个2，4个5，和为30；第五列4个2，5个5，和为33；以后第k列填9个k，和为9k54。则 e1=24。 所以 e1 的最大值为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写在圆周上，并依照上述规则操作，试问最后剩下的一个数为 。,解：第一圈:从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； 第十圈:删去424，1448，余下：936， 1960； 最后，删去936，余下1960 。,3.有两副扑克牌，每副牌的排列顺序是：第一张是大王，第二张是小王，然后是黑桃、红桃、方块、梅花4种花色排列，每种花色的牌又按A，2，3，J，Q，K的顺序排列。某人把按上述排列的两副扑克牌上下叠在一起，然后从上到下把第一张丢掉，把第二张放在最底层，把第三张丢掉，把第四张放在最底层，如此下去，直至最后剩下一张牌。则所剩的这张牌是什么？,分析：也来“做数学” 。,解：依次把牌编为1，2，3，108； 第一圈:从1开始，删去所有奇数，余下2k型数： 2，4，6，8，108； 第二圈:从2开始，删去所有4k-2型数，余下4k型数： 4， 8，12，16，108； 第三圈:从4开始，删去所有8k-4型数，余下8k型数： 8，16，24，104； 第四圈:从8开始，删去所有16k型型数，余下16k-8数： 8，24，40，56，72，88，104； 第五圈:从8开始，删去8，40，72，104，余下 24， 56，88； 第六圈:删去56，余下24，88；再删24，最后留88。 88=54+2+132+6，第88号牌为第二副牌中的方块6。,有没有更好的处理方法？ 我们发现，当牌数为4张时，最后留下的是4号牌； 当牌数为8张时，最后留下的是8号牌； 当牌数为2k张时，最后留下的是2k号牌； 现在共有108张牌，取掉44张时，恰好余64张； 按约定先去掉44张牌，第44张是开始排列中的第87号牌，而第88号牌被放到余下的64张牌的最后，故最后留下的是第88号牌。 请用此方法计算1，2，2004余下的最后的数。,有没有更好的处理方法？ 请用此方法计算1，2，2004余下的最后的数。 因为20041024=980，所以第980个被去掉的数是第一轮中的1959(98021) ，第981个被去掉的数是1961，从这儿按规则数最后的数是前面的1960。,4从1，2，3，2004中任选k个数，使得所选的k个数中，一定可以找到能构成三角形边长的3个数(这里要求三角形三个边长互不相等)。试问：满足条件的k的最小值。,考虑等价命题：1，2，3，2004中存在k1个数，其中任意3个数均不能构成一个三角形的3条边长 (这里要求三角形三个边长互不相等)。求满足此条件的k的最大值。,分析：从小的数开始，找尽量多的数，使之不能构成三角形两小边之和不大于第3边：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597， 16个数！再增加数一定会有两小边之和大于第3边了，所求的k的最大值为17。怎样表达？,解：按条件an-2+ an-1an2004构造递增的正整数数列an ，并使得an值最小n最大：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，共16个数！其中任意3个数 ai、aj、ak (ijk )，总有 ai+ ajak-2+ ak-1ak ，两小数之和大于第3数，不能成为三角形的3条边。 对于任意的、项数不少于17且每项值不超过2004的、递增的正整数数列bn ，若存在bi、bj、bk (ijk 17)满足bi+ bjbk，则此3个数可以成为三角形的3边边长；否则，bkak (k17)， b15+ b16 a15+ a162004 b17，b15，b16，b17可以成为三角形的3边边长 。 即所求的k的最小值为17。,5 在23的矩形方格纸上，各个小正方形的顶点称为格点。以格点为顶点的等腰直角三角形有（ ）个 A24 B38 C46 D50,分析： （1）两个格点间相距多大？1，2，3， （2）连接两格点的线段哪些可以做等腰直角三角形的边？,解： （1）直角边为1的三角形有46=24个； （2）直角边为2的三角形有42=8个； （3）直角边为 的三角形有42+6=14个； （4）直角边为 的三角形有4个；,5-1 在2n(n4)的矩形方格纸上，各个小正方形的顶点称为格点。以格点为顶点的等腰直角三角形有 个。,分析：与23的矩形方格纸上的计数有何联系? 能否考虑3 4的矩形方格纸上的计数?,6从1，2，205共205个正整数中，最多能取出多少个数，使得对于取出来的数中的任意三个数a、b、c(abc)，都有abc。,分析：从14，15，205共192个正整数中，任意取出两个数，乘积大于205，故其中任意3个数a、b、c(abc)，都有abc；加入一个1，依然能满足条件，所以可以取到193个数；问题是是否还可以再加入一些数吗？或者是否可以用一些数置换出一些数，使得能够得到更多的满足条件的数？,解：（1）证明取出的数的个数不能超过193： 12个三元数组 13，14，1314， 12，15，1215， 11，16，1116， 10，17，1117，9，18，918，3，24，324， 2，25，225中，共有36个互不相等的数，其中任意一组的3个数都不满足abc，故不能全部取出，所以205个数中至少有12个数不能取出，即能取出的数不超过193个； （2）可以取出193个数满足条件：14，15，205共192个正整数中，任意取出两个数，乘积大于205，故其中任意3个数a、b、c(abc)，都有abc；加入一个1，依然能满足条件，所以可以取到193个数。综上所述，最多可以取出193个数。,7如果存在1，2，n的一个排列a1，a2，an，使得k+ ak(k=1，2，n)都是完全平方数，则称n为“好数”。 试问：在11，13，15，17，19中，哪些是“好数”，哪些不是“好数”？说明理由。,分析：探索构造,对于11 k： 1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11，12， ak：3， 2， 1， 5， 4， 10， 9， 8， 7， 6， ？,对于13 k： 1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11，12，13 ak：3， 2，13， 12，11，10， 9， 8， 7， 6， 5 4， 3,8证明：存在一个三角形，它能被分成2005个全等的三角形。,分析：把一个三角形的每条边n 等分，可以把三角形分成n2个全等的三角形；2005不是完全平方数，但它是两个完全平方数的和。 2005=392+222。,证明：对于任意的三角形，把三边均n等分，过这些点作三组平行线，即把三角形分成n2 个互相全等的小三角形；,注意到2005=392+222。设直角三角形两直角边的长度分别为22和39，斜边上的高将其分成两个相似的斜边长度分别为22和39的直角三角形； 由前面说明，它们能分别被分成222和392个斜边长度为1的全等的直角三角形；即把原三角形分成了 2005个全等的三角形。,分析：有许多条件，把它理清。 从总体上去找等量关系，设某一学生恰被x个老师教过，则 bk=cx ； 从某个学生的角度去找等量关系。如张学生遇到的同组“师生对”(T，S)，因张共被x个老师教过，则h(c1)=x(k1)；,9. 一所学校有b个老师和c个学生，且满足条件： (1) 每个老师恰好教k个学生； (2)对任意两个不同的学生，恰好有h个老师同时教他们。 证明：,10在面积为1的矩形ABCD中（包括边界）有五个点，其中任意三点不共线，求以这五个点为顶点的三角形中，面积不大于 的 三角形个数的最小值。,分析1：五个无三点共线的点可确定10个三角形；当这些点集中在矩形中的某一小部分时，10个三角形的面积可以都不超