组合试题选.PPTVIP

* * 组合试题选讲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不成立时，则……； 综上，则……。 著名的赛题——证明：任意六个人中，总有三个人，要么相互认识，要么相互不认识。 A3 A2 A1 A6 A5 A4 同色分析三步：把实际问题转化为图形染色；抽屉原理；二分法推理。 证明：圆上六个点A1A2A3A4A5A6表示六个人，两人相互认识，相应两点间连红线，两人不相识，相应两点间连蓝线，原命题即为证明存在三边同色的三角形。 与A1相连的5条线分别染两种颜色，至少有三条线同色。不妨设至少有三条红线，且为A1A2、A1A3、A1A4。若A2、A3、A4三点间的连线有一条红线，则有红色三角形；否则，三条连线都是蓝线，存在蓝色三角形。 圆周上若有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个人聚会，其中任意两个人要么相互认识，要么相互不认识。 证明：一定存在两个三人组，每个组中的三个人，要么相互都认识，要么相互都不认识。 A3 A2 A1 A6 A5 A4 分析：可以用同色分析法，但不易；试用计算分析。 证明：用圆周上六个点表示六个人，两人相识相应两点间连红线，不相识连蓝线。定义过一点的两条边颜色相同的角为同色角，过一点两边颜色不同的角为异色角；三边同色的三角形为同色三角形，三边不同色的三角形为异色三角形。 每个圆周角只在一个圆内接三角形中，不能成为两个三角形的公共角。一个圆内接三角形中，异色角恰好有两个。 整个图中异色角最多有36个，最多可以构成18个异色三角形。以圆周上这六个点为顶点的三角形共有20个，故最少有两个同色三角形，命题得证。 * 圆周上若有9个点，每两个点间连红线或蓝线，至少存在 个同色三角形。 设过点Ai的红线有xi 条，蓝线有5-xi 条，则过点Ai的异色角有xi (5-xi)，xi=0，1，2，3，4，5。所以过Ai的异