高中数学奥赛辅导：第十讲设计与构造

1、高中数学奥赛辅导 第十讲 设计与构造知识、方法、技能组合数学问题，从内容上讲，大体可归结为两大类问题：一类是组合计数问题，这类问题在前几讲中已经充分研究过了；另一类是组合设计问题，我们在本讲和下一讲对此作深入的探讨.组合设计问题的基本含义是，对有限集合A，按照某性质P做出“安排”.对这种“安排”，有时是指需要我们设计一个方案，这个方案满足某些条件；有时是指对组合问题进行构造性证明的具体构造方法. 这就是我们这一讲要讲的设计与构造. 对这种“安排”，有时不容易给出，需要我们对问题的条件重新调整，甚至反复调整；也有时需要对问题的条件重新组阁搭配；这种安排在二人对策（游戏）问题中需要取胜，需要给出至

2、胜策略，这就是我们下一讲要研究的调整与对策.I. 设计有关“设计”的问题近几年来是热点竞赛问题，例如1999年中国数学奥林匹克第三大题：MO太空城由99个空间站组成，任两空间站之间有管形通道相连，规定其中99条通道为双向通行的主干道，其余通道严格单向通行. 如果某四个空间站可以通过它们之间的通道从其中任一站到达另外任一站，则称这四个站的集合为一个互通四站组.试为MO太空城设计一个方案，使得互通四站组的数目最大（请具体算出该最大数，并证明你的结论）.像这样的问题就是一个典型的奥数组合设计问题. 组合设计问题的特点是（1）来源于实际；（2）组合基础知识要扎实. 构造也就是构造方法解决组合问题，是组

3、合问题的解决中一种十分重要、十分奏效的方法. 经常需要构造的有：构造映射，构造集合，构造恒等式，构造组合模型，构造集合划分，构造抽屉，构造子集类，构造图形，构造实例，等等.赛题精讲例1：某市有n所中学，第I所中学派出Ci名学生（）来到体育馆观看球赛，全部学生总数为，看台上每一横排有199个座位，要求同一学校的学生必须坐在同一横排. 问体育馆最少要安排多少横排才能保证全部学生都能坐下？ （1990年全国联赛二度题3）【解】让学生按学校顺次入坐，每排坐满后再转入下一排，共用10（=1990199）排. 这时有的学校学生已坐在同一排，有的学校学生坐在两排. 后一种学校至多9个. 再增加两排座位，每排

4、可容纳5个学校. 将上述（至多）9个学校移到这两排，则每个学校的学生都坐在同一排，因此，12排足够. 另一方面，1990=3458+18. 如果58个学校各有34名学生，1个学校18名学生，那么每排至多安排34名学生的学校5所（346199），11排至多安排34名学生的学校55所，所以11排是不够的.例2：题目请见“知识、方法、技能”. （1999年中国数学奥林匹克试题三）【证明】在下面的讨论中，设n是大于3的奇数，并记我们将讨论n个空间站和n条双行主干道的更一般情形. 对于本题而言.（1）如果某四个空间站中，有一个站与其他三站间的通道都从该站单向发出，那么，这四站的集合必定是不互通的四站组.

5、 约定将所有这样的不互通四站组归入S类；并将所有不属S类的不互通四站组归入T类. 则互通四站组的总数为用1，2，n给n个空间站编号. 设从第i号空间站发出的单行通道数为Si，则S类不互通四站组的总数为（2）对于如上定义的，熟知有关系（可直接验证）：如果，那么，根据以上探讨，通过“调整法”可以断定据此估计互通四站组总数的上界为（3）如果能设计一个方案，使得S类不互通四站组的数目降到最少（实际降到0），那么，该方案的互通四站组的数目达到最大.为此目的，首先将编号为1，2，n的空间站依顺时针次序安排在一个圆周上. 下面将给出满足要求的两种方案.第一方案 首先将沿圆周相邻的空间站对之间的通道定为主干道

6、. 这样设定了n条主干道：1，2，2，3，n1，n，n，1.对于，如果圆周上沿顺时针方向从i到j的弧经过奇数个中间站，那么，规定i号站与j号站之间的通道为ij单行道. 因为n是奇数，从k到l的顺时针圆弧和从l到k的顺时针圆弧当中，恰有一条经过奇数个中间站，所以上述单行约定不会导致矛盾情形.按照此方案，从每个空间发出的单行道都为条，因此，S类不互通四站组总数降至最小下面将指出，按照此方案|T|=0.如果四站组中某两站间有主干道相连，那么，四站组中其余任一站都与这两站互通. 因此，这样的四站组为互通四站组.考察从四站组的某三站到剩下一站的三条通道都单向通往剩下的一站的情形，设在除去剩下一站D的圆周

7、上，所述的三站按顺时针方向依次为A，B，C. 因为AD，BD，CD，根据方案的单行规定可以判断A与B之间和A与D之间的顺时针圆弧上各经过奇数个中间站，我们判明通道AB，AC，AD的单行方向，因此，这样的不互通四站组A，B，C，D应归入S类.根据以上的讨论，可以断定|T|=0.最后算出互通四站组数的最大值 对于n=99，互通四站数组的最大值为 第二方案（同样先将编号为1，2，n的空间站按顺时针次序安排于一个圆周上.）如果从a号空间站到b号空间站的顺时针圆弧恰经个或者个中间站，那么，规定a与b间的通道为双行主干道. 如果从i号空间站到j号空间站的顺时针圆弧经过的中间站数少于，则规定i和j之间的通道

8、单向从i通往j.按照此方案，从每个空间站发出的单行通道数都为条. 因此，S类不互通四站组数降至最小值|S|=.按照此方案，同样可证|T|=0. 事实上，与第一方案类似的验证讨论，I351可以判定：如果某四站组中有两站间的通道是主干道，那么这四站组是互通的. 还可以判定：如果从四站组中某三站到剩下的一站D的通道都单向通往该站，那么这三站在除去D点的圆周上顺时针方向排头的一站A通往其他三站B，C，D的通道都单向发出：AB，AC，AD. 因此，这类四站组A，B，C，D应归入S类.因此，按照此方案建造的太空城，没有T类不互通四站组，并且互通四站组数达到最大. 剩下的计算同第一方案. 【评述】有一些不正

9、确的设计方案虽然能使各站发出的单行通道数目相等，却不能排除如图I351所示的那种不互通四站组，因而不能使互通四站组的数目达到最大.例3：给定空间中的9个点，其中任何4点都不共面，在每一对点之间都连有一条线段，这些线段可染为蓝色或红色，也可不染色. 试求出最小的n值，使得将其中任意n条线段中的每一条任意地染为红蓝二色之一，在这n条线段的集合中都必然包含有一个各边同色的三角形. （1992IMO333）【解】本题的背景是以两个熟知的结果:引理1：对五阶完全图的边作二染色，存在一种染色方法，使得染色后的图中没有单色边三角形，如图I352所示，虚、实线分别表示两种颜色的边，这时，图中无单色边三角形.引

10、理2：对边作二染色的六阶完全图中一定存在单色边三角形.为了求解本题，借助于引理1，我们构造一个9点图如图I353所示，这个图的顶点编号为1，2，9，其中边1，3，1，4，2，3，2，4染成红色（实线），顶点1与2之间没有边连接，类似地，圆圈内的顶点3与4，顶点5与6，顶点7与8均没有边相连，显然，这个图中没有单色边三角形，容易算出，这个图中的边数是.另一方面，没染色的线段至少有33条，则由于线段共条，不染色的线段至多3条.若点A1引出不染色的线段，则去掉A1及所引出的线段，若剩下的图中还有A2引出不染色的线段，则去掉A2及所引出的线段，依此进行，由于不染色的线段至多有3条，所以至多去掉3个顶点（及从它们引出的线段），这时至少剩下6个点. 每两点之间的连线染上红色或蓝色，由引理2知，必存在一个同色三角形.综上所述，n的最小值为33.例4：对. 【证明】构造集合表示从A中取n个元素的组合数，即由n个元素组成的A的真子集有个，而