高二数学竞赛辅导_组合数学

数学奥赛辅导设计构造与操作组合数学问题，从内容上讲，大体可归结为两大类问题：一类是组合计数问题，这类问题在前几讲中已经充分研究过了；另一类是组合设计问题，我们在本讲和下一讲对此作深入的探讨.组合设计问题的基本含义是，对有限集合A，按照某性质P做出“安排”.对这种“安排”，有时是指需要我们设计一个方案，这个方案满足某些条件；有时是指对组合问题进行构造性证明的具体构造方法.这就是我们这一讲要讲的《设计与构造》.对这种“安排”，有时不容易给出，需要我们对问题的条件重新调整，甚至反复调整；也有时需要对问题的条件重新组阁搭配；这种安排在二人对策（游戏）问题中需要取胜，需要给出至胜策略，这就是我们下一讲要研究的《调整与对策》．有关“设计”的问题近几年来是热点竞赛问题像这样的问题就是一个典型的奥数组合设计问题．组合设计问题的特点是（1）来源于实际；（2）组合基础知识要扎实．构造方法解决组合问题，是组合问题的解决中一种十分重要、十分奏效的方法.经常需要构造的有：构造映射，构造集合，构造恒等式，构造组合模型，构造集合划分，构造抽屉，构造子集类，构造图形，构造实例，…，等等.例1．某市有n所中学，第I所中学派出Ci名学生（niCi1,391）来到体育馆观看球赛，全部学生总数为niiC11990，看台上每一横排有199个座位，要求同一学校的学生必须坐在同一横排.问体育馆最少要安排多少横排才能保证全部学生都能坐下？解析：先考虑几种情况，（1）除1个学校是1人外，每个学校都是39人，共52班级。每排至少坐5个班级，那么至少需要11排，（2）除一个学校是14人外，每个学校都是38人，共有52班级，每排仍然有5个班级，还是需要11排；（3）再调整，设除了一个学校的人数为10，设每个学校的人数34，每排5个班级，用11排让55个班的学生坐下，还需要1排。下面证明：如果给定12排，都可以保证全部学生能坐下，只给定11排，是不可以的。先让1990个学生按学校坐下，有的学校会坐两排，此时共用去10排，坐两排的学校至多9个，再增加两排就可以解决问题。如果只给定11排，注：在各种情况中找最小的界是常用的方法，最后才加以证明，给出一种排法对任何情况都可以的。例2．（Ramsey问题）给定空间中的9个点，其中任何4点都不共面，在每一对点之间都连有一条线段，这些线段可染为蓝色或红色，也可不染色.试求出最小的n值，使得将其中任意n条线段中的每一条任意地染为红蓝二色之一，在这n条线段的集合中都必然包含有一个各边同色的三角形。解析：在考虑这个问题前，先熟悉几个简单的问题。（1）任意6个人中，总有3个人，他们全部认识或全部不认识。运用图论的方法，考虑在6K二色完全图中有同色三角形，这个是显然的。（2）房间里有10个人，任意三人中总有两个人相互认识，证明：其中必有4人相互认识。运用图论的方法，10K中，认识的用黄色相连，不认识的用红色相连。10K中无红色三角形，待证明：10K中有黄色的4K（3）5K二色完全图存在一种染色方法，使得其中无同色三角形我们采用比较原始的方法来证明：其中，右图的证明利用6K二色完全图中有同色三角形且该同色三角形必定为黄色三角形。让我们再回到原始的问题。9个点，可以有36条染色线段，如右图所示，我们可以构造一个如图所示的9个点的二色图，同一处的两个顶点的不连线，共有线段32，所以33n。如何证明这33条线段必定有同色的三角形呢？可以得到的结论是至多三条线段没有被染色？任意取一条不被染色线段，固定一个顶点，去掉该顶点及其相连接的线段，再取另一条不被染色的线段，同样操作。再取最后一条不被染色的线段，同样操作。至多去掉3个顶点，余下6个顶点，则结论必然成立。例3．（图论问题）有一个团队，由2009人组成，其中任意四个人中至少有一个人认识其他三个人，问该团队中认识其他所有人的人数至少为多少？解析：从2009开始，如果是完全图，则显然可以。如果不是完全图，则肯定有两个顶点的度小于或等于2008，如果存在其余两个顶点，他们的之间也没有连线，这四个顶点中有顶点到其余3点的无三条线段，矛盾了。所以人数至少为2007。例4．（组合几何）（1）ABC的最大边长是a，则这个三角形可被一半径为33a的圆所覆盖（2）ABC的最大边BC等于a，试求出覆盖ABC的最小圆．987654321解析：（1）显然（2）分三种情形讨论即可。A为钝角、直角、锐角三种情况。例5．（组合几何）证明不可能在平面上放有限个点，使得每一条过其中两点的直线都过第三点，除非这些点全在一条直线上。解析：过平面上n个点，最多2nC条直线，如果每条直线外都有点，则点到直线的诸距离中必定有最小值，如图，点P到直线l的距离PQ最小，直线l上有3个不同点，则必有两个点在Q的同侧，从而可以知道2P到直线1PP最小。矛盾。lQPP2P1注：这类问题的解法是考虑极端情形。例6．（组合操作题）正五边形的每个顶点对应一个整数，使得这5个整数和为正。若其中三个相连顶点相应的整数依次为,,xyz，而中间的0y，则要进行如下操作：整数,,xyz分别换为,,xyyzy，只要所得的5个整数中至少有一个负时，这种操作就继续进行，问：是否这样的操作进行有限次后必定终止。解析：必定终止。变换前后三个数和虽然不变，但是平方和变小，若不终止，整数的平方和为0，即各整数均为零，还得终止。注：操作过程中的不变性质和变化的性质是解决问题的关键。