组合试题选讲05初中(1)

《组合试题选讲05初中(1)》由会员分享，可在线阅读，更多相关《组合试题选讲05初中(1)（42页珍藏版）》请在金锄头文库上搜索。

1、组合试题选讲05 初中（1）江苏省常州高级中学 周敏泽简单的组合问题：如图，每个正方体的六个面上分别写着数字1，2，3，4，5， 6，并且任意两个相对的面上所写的两个数字之和都等于7。 把这样的4个正方体一个挨着一个连接起来后，紧挨着的两个 面上的数字之和都等于8。图中标着 x 的那个面上所写的数字是几？分析：拐角处正方体前后分别 为4，3，则右侧面可能是1或6 ，而1不能使x面的对面数字为 7，故只能为6，所以x的对面 数字为2，所以，x=5。 22x组合数学是上个世纪五十年代后逐步建立和完善起来的一门数学分支，组合数学也称为组合学、组合论，组合分析。教科书上对组合分析的定义：按某种要求把一

2、些元素构成有限集合的研究叫做组合分析。这种研究比传统的数学讨论的对象更广泛，在实际生活和实践活动中应用性更大。这种研究一般讨论以下问题：在一定的约束条件下，对象构成的存在性（有与没有、能与不能）问题；构成的分类与计数；构成的方法（构造方法）及最优化方法。人们常把竞赛中某些问题称为杂题，又称为组合数学问题。为什么？中学数学竞赛中的一些问题，很难把它们归类为代数问题或几何问题，但它们涉及到的解题目标和解题方法可以归入组合问题和组合分析；当然一些组合数学的习题也直接用作竞赛题。初等数学竞赛中的组合问题与组合分析常用的方法有抽屉原理、递推（归）原理、容斥原理、染色方法等，这些原理方法都很一般，重要的是

3、经验和技巧应用的能力。从04年江苏初中数学竞赛的两个组合试题说起1空间6个点(任意三点不共线)两两连线。现用红、蓝两色染这些线段。其中点A连出来的线段都是红色的。那么，以这6个点为顶点的三角形中，三边同色的三角形至少有（ ）A3个 B4个 C5个 D6个分析：与著名的赛题有联系分类方法中的二分表述：分类方法中的二分表述：分类法：总体情况可分情况一，情况二，情况N；若情况一，则；若情况二，则；若情况N，则， 综上，则。二分表述：若情况A，则；否则，若情况A不成立时，则；综上，则。著名的赛题证明：任意六个人中，总有三个人，要么相 互认识，要么相互不认识。A3A2A1A6A5A4同色分析三步：把实际

4、问题转化为图形 染色；抽屉原理；二分法推理。证明：圆上六个点A1A2A3A4A5A6表示六个人，两人相互认识，相应两点间连红线 ，两人不相识，相应两点间连蓝线，原命 题即为证明存在三边同色的三角形。与A1相连的5条线分别染两种颜色，至少有三条线同 色。不妨设至少有三条红线，且为A1A2、A1A3、A1A4。若 A2、A3、A4三点间的连线有一条红线，则有红色三角形；否则，三条连线都是蓝线，存在蓝色三角形。圆周上若有5个点，每两个点间连红线或蓝线，最少存在多少个同色三角形？ACEDB1空间6个点(任意三点不共线)两两连线。现用红、蓝两色染这些线段。其中点A连出来的线段都是红色的。那么，以这6个点

5、为顶点的三角形中，三边同色的三角形至少有（ ）A3个 B4个 C5个 D6个分析：另外5点连线均为蓝色线段，有10个同色三角形；连线中有一条红线，有1+7=8个同色三角形；连线中有两条红色线，分有无公共端点，至少有2+4=6个三角形；* 若有6个人聚会，其中任意两个人要么相互认识，要么相 互不认识。 证明：一定存在两个三人组，每个组中的三个人，要么相互都认识，要么相互都不认识。A3A2A1A6A5A4分析：可以用同色分析法，但不易；试用计算分析。证明：用圆周上六个点表示六个人，两人 相识相应两点间连红线，不相识连蓝线。 定义过一点的两条边颜色相同的角为同色 角，过一点两边颜色不同的角为异色角；

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）情

7、况二，推出目标数 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推出

8、可以；第二步：由目标数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、9位裁判给参加健美比赛的12名运动员评分。每位裁判对他认为的第一名运动员给1分，第二名运动员给2分，第12名运动员给12分。最后评分结果显示：每名运动员所得的9个分数中高低分之差都不大于3分。设各运动员的得分总和分别为e1，e2，e3，,e12，且e1e2e3e12，求e1 的最大值。121110 分析：含1分的格子最多有4列，此4列的每格数字平均不超过22.5，3列呢？2列？1列？解：对9个1分布的列数进行讨论：（1）1分分布在同一列，该列的和为 9，e1= 9;（2）1分恰在两列中，列中数字不超过4，两列的 和最大为59=45，较小的列和452，是整数，则 较小的列和22， 故最小的列和e

10、122(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.有两副扑克

11、牌，每副牌的排列顺序是：第一张是大王，第二张是小王，然后是黑桃、红桃、方块、梅花4种花色排列，每种花色的牌又按A，2，3，J，Q，K的顺序排列。某人把按上述排列的两副扑克牌上下叠在一起，然后从上到下把第一张丢掉，把第二张放在最底层，把第三张丢掉，把第四张放在最底层，如此下去，直至最后剩下一张牌。则所剩的这张牌是什么？分析:有一个小学的竞赛题，称为“做数学”。请先欣赏。3-1. 依顺时针方向将数字1，2，3，4，5，6，7写在圆周上。首先将数字1删除，然后每次跳过一个未删除的数，删除被跳到位置上的数，依此方法继续进行直到最后只剩下一个数为止。例如，删除数字1，跳过数字2；删除数字3，跳过数字4；

12、删除数字5，跳过数字6；删除数字7，跳过数字2；删除数字4，跳过数字6；删除数字2，所以，剩下最后的一个数是6。如果依顺时针方向将1，2，3，2004写在圆周上，并依照上述规则操作，试问最后剩下的一个数为 。7654312解：第一圈:从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；第五圈:

13、从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， 6

14、80， 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的顺序排列。某人把按上述排列的两副扑克牌上下叠在一起，然后从上到下把第一张丢掉，把第二张放在最底层，把第三张丢掉，把第四张放在最底层，如此下去，直至最后剩下一张牌。则所剩的这张牌是什么？

15、分析：也来“做数学” 。解：依次把牌编为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余下的最后的数。因为200410