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

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

知识、方法、技能

组合数学问题，从内容上讲，大体可归结为两大类问题：一类是组合计数问题，这类问题在前几讲中已经充分研究过了；另一类是组合设计问题，我们在本讲和下一讲对此作深入的探讨.

组合设计问题的基本含义是，对有限集合A，按照某性质P做出“安排”.对这种“安排”，有时是指需要我们设计一个方案，这个方案满足某些条件；有时是指对组合问题进行构造性证明的具体构造方法. 这就是我们这一讲要讲的《设计与构造》. 对这种“安排”，有时不容易给出，需要我们对问题的条件重新调整，甚至反复调整；也有时需要对问题的条件重新组阁搭配；这种安排在二人对策（游戏）问题中需要取胜，需要给出至胜策略，这就是我们下一讲要研究的《调整与对策》.

I. 设计

有关“设计”的问题近几年来是热点竞赛问题，例如1999年中国数学奥林匹克第三大题：MO太空城由99个空间站组成，任两空间站之间有管形通道相连，规定其中99条通道为双向通行的主干道，其余通道严格单向通行. 如果某四个空间站可以通过它们之间的通道从其中任一站到达另外任一站，则称这四个站的集合为一个互通四站组.

试为MO太空城设计一个方案，使得互通四站组的数目最大（请具体算出该最大数，并证明你的结论）.

像这样的问题就是一个典型的奥数组合设计问题. 组合设计问题的特点是（1）来源于实际；（2）组合基础知识要扎实.

Ⅱ. 构造

也就是构造方法解决组合问题，是组合问题的解决中一种十分重要、十分奏效的方法. 经常需要构造的有：构造映射，构造集合，构造恒等式，构造组合模型，构造集合划分，构造抽屉，构造子集类，构造图形，构造实例， ，等等.

赛题精讲

例1：某市有n所中学，第I所中学派出Ci名学生（1 Ci 39,1 i n）来到体育馆观看球赛，

全部学生总数为

C

i 1

n

i

1990，看台上每一横排有199个座位，要求同一学校的学生必须

坐在同一横排. 问体育馆最少要安排多少横排才能保证全部学生都能坐下？ （1990年全国联赛二度题3）

【解】让学生按学校顺次入坐，每排坐满后再转入下一排，共用10（=1990÷199）排. 这时

有的学校学生已坐在同一排，有的学校学生坐在两排. 后一种学校至多9个. 再增加两 排座位，每排可容纳5个学校. 将上述（至多）9个学校移到这两排，则每个学校的学 生都坐在同一排，因此，12排足够.

另一方面，1990=34×58+18. 如果58个学校各有34名学生，1个学校18名学生，那 么每排至多安排34名学生的学校5所（34×6>199），11排至多安排34名学生的学校55所， 所以11排是不够的.

例2：题目请见“知识、方法、技能”. （1999年中国数学奥林匹克试题三）

【证明】在下面的讨论中，设n是大于3的奇数，并记m

n 3

.我们将讨论n个空间站和n条2n 3

48. 双行主干道的更一般情形. 对于本题而言n 99,m 2

（1）如果某四个空间站中，有一个站与其他三站间的通道都从该站单向发出，那么， 这四站的集合必定是不互通的四站组. 约定将所有这样的不互通四站组归入S类；并将所有 不属S类的不互通四站组归入T类. 则互通四站组的总数为

4Cn |S| |T|.

用1，2， ，n给n个空间站编号. 设从第i号空间站发出的单行通道数为Si，则S类 不互通四站组的总数为

|S| Cs3i,这里Ck3

i 1

n

k(k 1)(k 2)

6

3

2

（2）对于如上定义的Ck和Ck

333Ck Ck C 1k 1.

k(k 1)

，熟知有关系（可直接验证）： 2

如果s t 1，那么，

Cs3 Cs3 1 Cs2 1 Ct2 Ct3 1 Ct3,即C C C

n

3s3t3s 1

C.

3t 1

根据以上探讨，通过“调整法”可以断定

1n12n 3

|S| C nC,其中m si (Cn n) .

nn2i 1i 1

3

si

3m

据此估计互通四站组总数的上界为

443Cn |S| |T| Cn nCm.

（3）如果能设计一个方案，使得S类不互通四站组的数目降到最少（实际降到0），那 么，该方案的互通四站组的数目达到最大. 为此目的，首先将编号为1，2， ，n的空间站依顺时针次序安排在一个圆周上. 下面 将给出满足要求的两种方案. 第一方案 首先将沿圆周相邻的空间站对之间的通道定为主干道. 这样设定了n条主干 道：{1，2}，{2，3}， ，{n－1，n}，{n，1}.

对于i,j {1,2, ,n},i j，如果圆周上沿顺时针方向从i到j的弧经过奇数个中间站，

那么，规定i号站与j号站之间的通道为i→j单行道. 因为n是奇数，从k到l的顺时针圆弧 和从l到k的顺时针圆弧当中，恰有一条经过奇数个中间站，所以上述单行约定不会导致矛 盾情形.

按照此方案，从每个空间发出的单行道都为m

n 3

条，因此，S类不互通四站组总 2

3

数降至最小|S| nCm.

下面将指出，按照此方案|T|=0. 如果四站组中某两站间有主干道相连，那么，四站组中其余任一站都与这两站互通. 因 此，这样的四站组为互通四站组. 考察从四站组的某三站到剩下一站的三条通道都单向通往剩下的一站的情形，设在除去 剩下一站D的圆周上，所述的三站按顺时针方向依次为A，B，C. 因为A→D，B→D，C→ D，根据方案的单行规定可以判断A与B之间和A与D之间的顺时针圆弧上各经过奇数个 中间站，我们判明通道A→B，A→C，A→D的单行方向，因此，这样的不互通四站组{A， B，C，D}应归入S类. 根据以上的讨论，可以断定|T|=0. 最后算出互通四站组数的最大值

Cn nCm

4

3

n(n 3)2

(n 6n 31). 48

对于n=99，互通四站数组的最大值为 99

96

(9801 594 31) 99 2 1036 4205207 248

n 3n 1

个或者个中间站，那么，

22

第二方案（同样先将编号为1，2， ，n的空间站按顺时针次序安排于一个圆周上.） 如果从a号空间站到b号空间站的顺时针圆弧恰经

规定a与b间的通道为双行主干道. 如果从i号空间站到j号空间站的顺时针圆弧经过的中间 站数少于

n 3

，则规定i和j之间的通道单向从i通往j. 2

n 3

条. 因此，S类不互通四站 2

按照此方案，从每个空间站发出的单行通道数都为m

3

组数降至最小值|S|=nCm.

按照此方案，同样可证|T|=0. 事实上，与第一方案类似的验证讨论，

可以判定：如果某四站组中有两站间的通道是主干道，那么这四站组是

I—3—5—1 互通的. 还可以判定：如果从四站组中某三站到剩下的一站D的通道都

单向通往该站，那么这三站在除去D点的圆周上顺时针方向排头的一站 A通往其他三站B，C，D的通道都单向发出：A→B，A→C，A→D. 因 此，这类四站组{A，B，C，D}应归入S类. 因此，按照此方案建造的太空城，没有T类不互通四站组，并且互通四站组数达到最大. 剩下的计算同第一方案.

【评述】有一些不正确的设计方案虽然能使各站发出的单行通道数目相等，却不能排除如图I—3

—5—1所示的那种不互通四站组，因而不能使互通四站组的数目达到最大.

例3：给定空间中的9个点，其中任何4点都不共面，在每一对点之间都连有一条线段，这些线

段可染为蓝色或红色，也可不染色. 试求出最小的n值，使得将其中任意n条线段中的每一

条任意地染为红蓝二色之一，在这n条线段的集合中都必然包含有一个各边同色的三角形. （1992IMO33—3）

【解】本题的背景是以两个熟知的结果: 引理1：对五阶完全图的边作二染色，存在一种染色方法，使得染色后的图中没有单色 边三角形，如图I—3—5—2所示，虚、实线分别表示两种颜色的边，这时，图中无单色边三 角形

.

引理2：对边作二染色的六阶完全图中一定存在单色边三角形. 为了求解本题，借助于引理1，我们构造一个9点图如图I—3—5—3所示，这个图的顶 点编号为1，2， ，9，其中边{1，3}，{1，4}，{2，3}，{2，4}染成红色（实线），顶点1 与2之间没有边连接，类似地，圆圈内的顶点3与4，顶点5与6，顶点7与8均没有边相

2

连，显然，这个图中没有单色边三角形，容易算出，这个图中的边数是C9 4 32,所以,n 33.

2

另一方面，没染色的线段至少有33条，则由于线段共C9 36条，不染色的线段至多3

条. 若点A1引出不染色的线段，则去掉A1及所引出的线段，若剩下的图中还有A2引出不染 色的线段，则去掉A2及所引出的线段，依此进行，由于不染色的线段至多有3条，所以至 多去掉3个顶点（及从它们引出的线段），这时至少剩下6个点. 每两点之间的连线染上红色 或蓝色，由引理2知，必存在一个同色三角形 . 综上所述，n的最小值为33.

2n例4：对n 2,求证:2n C2n 4. ①

2【证明】构造集合A {a1,a2, ,an,an 1, ,a2n},则C2n表示从A中取n个元素的组合数，即

n

由n个元素组成的A的真子集有C2n个，而A的所有子集数是

0122n2n C2 4n个， n C2n C2n C2n 2nn故有C2 4n

又设集合B1 {a1,a2, ,an}

B2 {an 1,an 2, ,a2n}

对于集合B1的一个子集，设其有r个元素，若r n,则从集合B2中任取n r个元素；再连同取出B1的全部元素，这种取法实际上是从集合A中取出n个元素的一种方式.注意到，若1 r n,则从集合B2中取出n－r个元素的方式不是惟一的. 因此，集合B1的全部子集数少

n于从集合A中取出n个元素组成的子集数，即2n C2n，故不等式①成立.