当前位置:首页 >> 学科竞赛 >>

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


数学奥赛辅导 第十讲 设计与构造
知识、方法、技能
组合数学问题,从内容上讲,大体可归结为两大类问题:一类是组合计数问题,这类问题在 前几讲中已经充分研究过了;另一类是组合设计问题,我们在本讲和下一讲对此作深入的探讨. 组合设计问题的基本含义是,对有限集合 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 条 2 n?3 ? 48 . 双行主干道的更一般情形. 对于本题而言 n ? 99, m ? 2

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

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

| S |? ? C s3i , 这里C k3 ?
i ?1

n

k (k ? 1)(k ? 2) 6
3 2

(2)对于如上定义的 C k 和C k ?
3 3 3 Ck ? Ck ?1 ? Ck ?1 .

k (k ? 1) ,熟知有关系(可直接验证) : 2

如果 s ? t ? 1 ,那么,

C s3 ? C s3?1 ? C s2?1 ? Ct2 ? Ct3?1 ? Ct3 , 即C s3 ? Ct3 ? C s3?1 ? Ct3?1 .
根据以上探讨,通过“调整法”可以断定
3 | S |? ? C s3i ? nCm , 其中m ? i ?1 n

1 n 1 2 n?3 si ? (C n ? n) ? . ? n i ?1 n 2

据此估计互通四站组总数的上界为
4 4 3 Cn ? | 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 ?
3 数降至最小 | S |? nCm .

n?3 条,因此,S 类不互通四站组总 2

下面将指出,按照此方案|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. 最后算出互通四站组数的最大值
4 3 Cn ? nC m ?

n(n ? 3) 2 (n ? 6n ? 31). 48

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

99 ?

96 ? (9801 ? 594 ? 31) ? 99 ? 2 ? 1 0 3 6 ? 4 2052072 48 n?3 n ?1 个或者 个中间站,那么, 2 2

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

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

n?3 ,则规定 i 和 j 之间的通道单向从 i 通往 j. 2

按照此方案,从每个空间站发出的单行通道数都为 m ?
3 组数降至最小值|S|= nCm .

n?3 条. 因此,S 类不互通四站 2

按照此方案,同样可证|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.
2 n 例 4:对 n ? 2, 求证 : 2 n ? C2 n ?4 .



2 【证明】构造集合 A ? {a1 , a2 ,?, an , an?1 ,?, a2n }, 则C2 n 表示从 A 中取 n 个元素的组合数,即 n 由 n 个元素组成的 A 的真子集有 C 2 n 个,而 A 的所有子集数是 0 1 2 2n 2n C2 ? 4n 个, n ? C2n ? C2n ? ? ? C2n ? 2 n n 故有 C2 n ? 4

又设集合 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 个元素组成的子集数,即 2 n ? C2 n ,故不等式①成立.


相关文章:
高中数学奥赛辅导 第十讲 设计与构造
高中数学奥赛辅导 第十讲 设计与构造_学科竞赛_高中教育_教育专区。数学奥赛辅导...经常 需要构造的有:构造映射,构造集合,构造恒等式,构造组合模型,构造集合划分,...
数学奥赛辅导_第十讲_设计与构造
关键词:高中数学竞赛辅导 同系列文档 数学奥赛辅导_第一讲_奇数... 数学奥赛辅导...数学奥赛辅导_第十讲_设计与构造数学奥赛辅导_第十讲_设计与构造隐藏>> 数学...
数学奥赛辅导 第十讲 设计与构造
高中数学奥赛辅导教材第十... 7页 免费如要投诉违规内容,请到百度文库投诉中心...数学奥赛辅导 第十讲 设计与构造数学奥赛辅导 第十讲 设计与构造隐藏>> 欢迎光临...
高中数学奥赛辅导教材(共十讲)精品
高中数学奥赛辅导教材(共十讲)精品_高三数学_数学_高中教育_教育专区。相当不错...评述】应用排序不等式的技巧在于构造两个数组,而数组的构造应从需要入手来设计....
高中数学奥赛辅导 第八讲 组合计数
高中数学奥赛辅导 第八讲 组合计数_学科竞赛_高中教育...(全国高中数学联赛,1991 年) 【解】构造具有如下...例 10 设 A1,A2,A3 是集合{1,2,?,n}的具有...
高中数学奥赛赛前辅导
高中数学奥赛赛前辅导_学科竞赛_高中教育_教育专区。...(1)设 A 是 Sn 的任一奇子集,构造映射 f 如...易想到用面积法来求解. 第十讲 立体几何 1、如图...
高中数学奥赛辅导 第六讲 集合与映射
高中数学奥赛辅导 第六讲 集合与映射_学科竞赛_高中...竞赛题是这种类型.例如映射法可与抽屉 原理、构造法...{1,2,?,10}, A 到 A 的映射 f 满足下列两...
高中数学奥赛辅导 第二讲 整除
高中数学奥赛辅导 第二讲 整除_学科竞赛_高中教育_教育专区。数学奥赛辅导整除知识...1 . 例 10:求所有这样的自然数 n ,使得 2 ? 2 ? 2 是一个自然数的...
数学奥赛辅导 第六讲 集合与映射
数学奥赛辅导 第十讲 设计...1/2 相关文档推荐 ...高中数学奥赛辅导教材第十... 7页 免费如要投诉违规...竞赛题是这种类型.例如映射法可与抽屉 原理,构造法...
数学奥赛辅导第六讲
高中数学奥赛辅导教材第一... 64页 免费 数学奥赛辅导 第九讲 10页 1财富值...而且大多数竞赛题是这种类型.例如映射法可与 抽屉原理、构造法、反证法等各种方法...
更多相关标签:
高中数学奥赛辅导总结 | 高中奥赛辅导方案 | 高中物理奥赛辅导 | 高中化学奥赛辅导 | 高中化学奥赛辅导书 | 高中数学奥赛辅导书 | 高中物理奥赛辅导书 | 高中奥赛辅导书 |