tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

组合构造答案及讲稿


【组合十讲】 组合十讲】

组合构造
陶平生
构造法是解证组合问题的重要方法与基本手段,使用它,常常可以将问题化难为易,化 抽象为直观, 它需要较强的结构转化与知识综合能力.常用的构造方法有:数论构造法; 几何构造法;模型构造法;旋转、置换(群)构造法;图表构造法;图论构造法等. 一、数论构造法 我们通过一些具体例子来说明这一方法的运用.

1 、空间有 2011 个点,无三点共线,现将每两点之间用一种颜色的线连接,使得对于 其中任意一点而言, 由该点发出的任两条线皆不同色, 问至少需要多少种不同颜色的线?证 明你的结论.若将 2011 个点改为 2012 个点,情况又将如何? 解:一般化,将 2011 改为 n ,其中正整数 n ≥ 2 ,线段颜色数的最小值记为 f ( n) , 易知 f (2) = 1, f (3) = 3, f (4) = 3, f (5) = 5 ,… … 今证明,一般情况下有 f (2n + 1) = 2n + 1, f (2n) = 2n ? 1 . 设 2n + 1 个点为 A0 , A1 ,L , A2 n ,由于每点都要发出 2n 条线,诸线不同色,这样至少需 要 2n 色; 再证 2n 色不够,若总共只有 2n 色,则每点都要恰好属于各色线的端点一次.现在设总 共有 k 条红色线,它们总共有 2k 个两两互异端点,于是 2k = 2n + 1 ,矛盾! 因此 f (2n + 1) > 2n ,即 f (2n + 1) ≥ 2n + 1 . 下面说明最小值 2n + 1 可以取到,采用数论构造法: 用 S0 , S1 ,L , S 2 n 分别表示这 2n + 1 色,而 x 表示整数 x 模 2n + 1 的最小非负余数,即

x ∈ {0,1,L , 2n} ,对于任意两点 Ai , A j (i ≠ j ) ,将连线 Ai A j 染第 i + j 色 Si + j ,于是,对
于任意一点 Ak ,发自 Ak 的任两条线皆不同色.事实上,假若 Ak Ai 与 Ak A j 同色,则有

k + i = k + j ,即 k + i ≡ k + j (mod 2n + 1) ,得 i ≡ j (mod 2n + 1) ,因 i, j ∈ {0,1,L , 2n} ,
故有 i = j ,矛盾!故这种染色方案合于条件,因此, f (2n + 1) = 2n + 1 . 又对于 2n + 2 个点 A0 , A1 ,L , A2 n , A2 n +1 ,由于每点都要向其余 2n + 1 点共发出 2n + 1 条线,诸线不同色,这样至少需要 2n + 1 色,只要证, 2n + 1 色已足够. 构造,仍用 S0 , S1 ,L , S 2 n 分别表示这 2n + 1 色,暂不考虑点 A2 n +1 ,先对前 2n + 1 个点

A0 , A1 ,L , A2 n 两两间的连线依照上述 2n + 1 个点的情形染色,我们注意到,对于其中任意

1

两点 Ai , A j (i ≠ j ) 的连线 Ai A j 染色时,要求 i ≠ j ,也就是说,由点 Ai 发出的 2n 条线的颜 色代号 i + j , j ∈ {0,1,L , 2n} \ {i} ,为模 2n + 1 的完系中缺少了一个剩余 i + i = 2i . 现将点 A2 n +1 与前 2n + 1 个点中任一点 Ai 的连线 A2 n +1 Ai , (i = 0,1,L , 2n) 染第 i + i 色

S 2i ,由于当 i ≠ j 时 2i 与 2 j 模 2n + 1 不同余,故由点 A2 n +1 发出的 2n + 1 条线互不同色,
由其它点发出的 2n + 1 条线也互不同色,故这种染色方案合于条件. 因此, f (2n + 2) = 2n + 1 ,从而 f (2n) = 2n ? 1 . 于是对于 2011 个点或是 2012 个点,都至少需要 2011 种颜色的线. 下面的图形是 n = 5 和 n = 6 的情况.由此可以看到,利用数论构造法给出的染色方案, 优美和谐,浑然天成.

A0 1 A1 3 A2 0 2 4 0 1 A3 3 2 4 A4 A1
2 3 2 4 1

A0
4 0 0 4

3 3 1 1 2

A4

A2

0

A3

2 、证明:可以将集合 M = {1, 2,L , 2012} 中的元素分成 671 组,使得每组的元素
和相等. 证:我们可一般化为下述命题:若奇数 n > 1 ,则集合 M = {1, 2,L ,3n ? 1} 可以分拆 成 n 个两两不交的元素之和相等的子集之并. 在集合 M 中添加元素 0 ,并将诸元素依自小到大的顺序排列,然后按每 n 个数一段分 成三段: 0,1,L , n ? 1, n, n + 1,L , 2n ? 1, 2n, 2n + 1,L ,3n ? 1 . 易知,对于两个具有 k 个项的递增连续自然数数列 x1 , x2 ,L , xk 及 y1 , y2 ,L , yk ,它们 按相反次序相加的每两项之和为常数:即 x1 + yk = x2 + yk ?1 = L = xk + y1 ; 因此只要证,可以将第一段的 n 个数适当排成 a1 , a2 ,L , an ,第二段的 n 个数适当排成

b1 , b2 ,L , bn , 使得 a1 + b1 , a2 + b2 ,L , an + bn 恰好组成 n 个连续自然数; (此时只要将所得的
) 这 n 个数与第三段的数反序相加,就得到相等的 n 个和.

2

若将第二段的每个数各减 n , 问题又化为: 若奇数 n ≥ 3 , 存在前 n 个自然数 0,1,L , n ? 1 的两个排列: x1 , x2 ,L , xn 及 y1 , y2 ,L , yn ,使得 x1 + y1 , x2 + y2 ,L , xn + yn 恰好组成 n 个连 续自然数; 为此, 采用构造法, n 个连续自然数 x1 + y1 , x2 + y2 ,L , xn + yn 中,最小的一数为 k , 设 则此 n 个数为 k , k + 1,L , k + n ? 1 ,其和为 kn +
n

n(n ? 1) ,又据 2

故由 ∑ ( x + y ) = 2 ( 0 + 1 + L + (n ? 1) ) = n(n ? 1) , kn +
i =1 i i

n(n ? 1) n ?1 = n(n ? 1) , k = 得 , 2 2

这样,问题化为:若奇数 n ≥ 3 ,存在前 n 个自然数 0,1,L , n ? 1 的两个排列: x1 , x2 ,L , xn 及 y1 , y2 ,L , yn ,使得

x1 + y1 =

n ?1 n ?1 n ?1 3(n ? 1) , x2 + y2 = + 1,L , xn + yn = + n ?1 = , 2 2 2 2

为直观起见,记为 ?

? x1 x2 L xn ? ? → ( x1 + y1 , x2 + y2 ,L , xn + yn ) ; ? y1 y2 L yn ? ? x1 x2 x3 ? ? 0 2 1? 3 ?1 = 1 ,而 ? ?=? ? → (1, 2,3) ; 2 ? y1 y2 y3 ? ?1 0 2 ?

注意到, n = 3 时, k =

n = 5 时, k =

? x1 x2 x3 x4 x5 ? ? 0 2 4 1 3 ? 5 ?1 = 2 ,而 ? ?=? ? → (2,3, 4,5,6) ; 2 ? y1 y2 y3 y4 y5 ? ? 2 1 0 4 3 ?

? x1 x2 x3 x4 x5 x6 x7 ? ? 0 2 4 6 1 3 5 ? n = 7 时, k = 3 ,而 ? ?=? ? → (3, 4,5, 6, 7,8,9) ; ? y1 y2 y3 y4 y5 y6 y7 ? ? 3 2 1 0 6 5 4 ?
若用记号 a 表示整数 a 被 n 除得的最小非负余数, a ∈ {0,1,L , n ? 1} , 据上述情况可以推测,对于奇数 n ≥ 3 ,可以构作满足条件的两个数列 { xk } , { yk } , 其中 xk = 2 k , yk =

n ?1 ? k , k = 0,1, 2,L , n ? 1 . 2 n ?1 ? k ,k = 0,1, 2,L , n ? 1 各自通过模 n 2

先说明, xk = 2 k , k = 0,1, 2,L , n ? 1 以及 yk =

的最小非负完全剩余系,事实上,对每个 k , xk = 2k ∈ {0,1,L , n ? 1} ,并且这 n 个 xk 中, 任两个不相等,因为若有 i ≠ j 使 xi = x j ,即 2 i = 2 j ,也就是 2 i ≡ 2 j (mod n) ,由于 n 为
3

奇数,则 i ≡ j (mod n) ,而 i, j ∈ {0,1,L , n ? 1} ,矛盾! 同理可知, yk =

n ?1 ? k , k = 0,1, 2,L , n ? 1 也通过模 n 的最小非负完全剩余系;于 2

是 { xk } , { yk } , k = 0,1, 2,L , n ? 1 分别是 0,1, 2,L , n ? 1 的一个排列; 又注意 x0 + y0 = 2 ? 0 +

n ?1 n ?1 ?0 = , 2 2

? ? ? ? n ?1 n ?1 ( xk +1 + yk +1 ) ? ( xk + yk ) = ? 2(k + 1) ? ? (k + 1) ? ? ? 2k ? ?k? 2 2 ? ? ? ?
? n ?1 ? ? ? n ?1 ?? ≡ 2(k + 1) ? ? ? (k + 1) ? ? ? 2k ? ? ? k ? ? ≡ 1 (mod n) , k = 0,1, 2,L , n ? 2 , ? 2 ? ? ? 2 ??
因此 { xk + yk } , k = 1, 2,L , n ? 1 构成以 于是所证的结论成立.

n ?1 为最小数的 n 个连续自然数. 2

3 、给定两个正整数 m, n ,其中 n > 1 ,且 n ? ;试求最小的正整数 k ,使得在任意 k m
个满足条件: “对一切 1 ≤ i < j ≤ k , n ? ai ? a j ) ”的整数 a1 , a2 ,L , ak 中,都存在两个整 ( 数 as 和 at ( s ≠ t ) ,使得 m + as ? at 可被 n 整除. 解:由于所考虑的是“被 n 整除”这一特征,故可将题中所涉整数皆替换为“被 n 除得 的余数”来考虑;用 x 表示整数 x 被 n 除得的最小正余数,即

?x ∈ Z , x ∈ Z n = {1, 2,L , n} ;
为了探求本题结论的一般性结构,先分析以下特例: 例 1 、取 n = 10, m = 17 ,这时 (m, n) = 1, m = 7, ai , a j ∈ {1, 2,L ,10} ,且

10 m + ai ? a j 当且仅当 10 m + ai ? a j ,即 10 7 + ai ? a j ;
于是,有两种情况: (1) 、 ai ? a j = 3 ;

(2) 、 ai ? a j = ?7 ,即 a j ? ai = 7 .

问题化为,从 {1, 2,L ,10} 中取 k 个数,为了保证这 k 个数中必有两数之差(大数减小数) 为 3 或 7 ,求 k 的最小值.
8 1 4 7 2 9 3 6 10

为此,将数 1, 2,L ,10 排列于一个圆周之上,使得相邻两 两数之差(大数 减小数)都为 3 或 7 ,有右图的排法: 从其中任取 k 个不同的数,为了保证取出的数中必有两个相邻,则至少 要取六个数,即 k ≥ 6 ;

5

4

例 2 、取 n = 15, m = 27 ,这时 (m, n) = 3, m = 12, ai , a j ∈ {1, 2,L ,15} ,且

15 27 + ai ? a j 当且仅当 15 12 + ai ? a j ,
此时也有两种情况: ai ? a j = 3 ;或 a j ? ai = 12 . 将数 1, 2,L ,15 排列于一个圆周 之上,使得相邻两两数之差(大数 减小数)都为 3 或 12 ,这时排出三 个圈: 此处作成三个圈是因为
13 1

2 4 14 5

3

15

6

10

7

11

8

12

9

d = (m, n) = 3 的缘故.
从中任取 k 个不同的数,为了保证取出的数中必有两个相邻,则在三个圈中,总共至少要 取七个数,即 k ≥ 7 ; (若总共只取六个数,可以选择每个圈上各取两个数,且不相邻,这样得到的六数不能满 足条件) 现分析 k = 7 的数字结构: 7 = 3 × 2 + 1 . 其中 3 = (27,15) = ( m, n) = d 是圆周的个数;数 2 是在同一个取出的元素个数,使得在同 一个圆周上可能不存在相邻数的最大允许值,它当然与该圆周上元素的个数有关,而

n ?5? ?n ? 2 = ? ? = ? 0 ? , n0 = ; d ?2? ? 2 ?
于是猜测,一般有: k = d ?

n ? n0 ? * ? + 1 ……○.其中 d = (m, n) , n0 = d . ?2?

m 今考虑一般情况:由 n m + a i ? a j 等价于 n m + a i ? a j ,而 n ≥ 2 ,所以,条件 n ? 等
价于 1 ≤ m ≤ n ? 1 ,且 1 ≤ ai ≤ n, 1 ≤ a j ≤ n , 而条件 n ? ai ? a j ) 等价于 n ? ai ? a j ) ,即 1 ≤ ai ? a j ≤ n ? 1 ,于是 ( (

2 ? n ≤ m + ai ? a j ≤ 2n ? 2 ,由 n m + a i ? a j ,得 m + ai ? a j = 0 或 n ,
即 a j ? ai = m ,或 ai ? a j = n ? m ,……① 记 d = ( m, n) = ( m, n) ,设 m = m0 d , n = n0 d ,则 ( m0 , n0 ) = 1 ,据①得

a j ? ai d

= m0 或

ai ? a j d

= n0 ? m0 ……②

由 1 ≤ m ≤ n ? 1 < n 知, 1 ≤ m0 < n0 ,而由 ( m0 , n0 ) = 1 得 ( m0 , n0 ? m0 ) = 1 ;
5

因此由①得 ai ≡ a j (mod d ) ,设 ai = ud + r , a j = vd + r ; r = 0,1,L , d ? 1 ,

u, v ∈ {0,1,L , n0 } ……③
今按 r 的取值情况讨论:

(1) 、若 r = 0 ,则②化为, v ? u = m0 或 u ? v = n0 ? m0 ……④
且因 1 ≤ ai ≤ n, 1 ≤ a j ≤ n 及 r = 0 ,由③知 u , v 均 不为 0 ,即 u , v ∈ {1, 2,L , n0 } , 改记

m0 = a, n0 ? m0 = b ,则 a + b = n0 , (a, b) = 1 ,于是④式可改写为对称形式: v ? u = a 和 u?v =b.
引理:设 ( a, b) = 1 , a + b = n0 , a, b 为正整数,从 {1, 2,L , n0 } 中取出一个 t 元子集

?n ? M = { x1 , x2 ,L , xt } , 使得 M 中的任两数之差, 既不为 a , 也不为 b , t 的最大值为 ? 0 ? . 则 ?2?
采用数论构造法.为了导出一般性方法,先分析一个特例:取 a = 4, b = 7, n0 = 11 , 将 1, 2,L ,11 按图中顺序排列于圆周上,使得相邻两数之差或者为 4 ,或者为 7 ,而不相邻 的任两数之差,既不是 4 ,也不是 7 ;若将圆周上的 11 个数按顺时针 方向读出, ,就是: 1,5, 9, 2, 6,10, 3, 7,11, 4,8 ,圈中不相邻的数最多
4 8 1 5 9 2 7 3 10 6

可取到 ?

? n0 ? ?11 ? ? = ? ? = 5 个. ?2? ?2?

11

由于对一般的 a, b, n0 ,我们不可能一个个地去构造,为此,重新 研究这组数的结构,对于 a = 4, b = 7 ,不难发现,前三项 1,5,9 分别可看作

1, 1 + a, 1 + 2a ,由此想到,后续的项当是 1 + 3a, 1 + 4a,L ,1 + ( n0 ? 1) a ,即是说,对于一
般的 a, b, n0 ,填写于圆周上的 n0 个数顺次为 1 + ta, t = 0,1, 2,L , n0 ? 1 ; 另一方面,据对称性,我们也可顺次写出 1 + tb, t = 0,1, 2,L , n0 ? 1 ,它与上面填写于 圆周上的 n0 个数实际上是重合的一组,只不过是按相反的方向从圆周上读出而已. 下面证明,排在圆周上的这组数 1 + ta, t = 0,1, 2,L , n0 ? 1 符合要求. 由 ( a, b ) = 1 , ( a, a + b ) = 1, ( b, a + b ) = 1 ,即 ( a, n0 ) = 1, ( b, n0 ) = 1 ,而 x 是整数 x 被 n0 知 除得的最小正余数,故上述 n0 个数 1 + ta, t = 0,1, 2,L , n0 ? 1 ,每个 1 + ta 皆属于
6

{1, 2,L , n0 } ;这组数中,任两个皆不相等:假若1 + ia = 1 + ja , i ≠

j ,则

0 = 1 + ia ? 1 + ja ≡ (1 + ia ) ? (1 + ja ) ≡ ( i ? j ) a ( mod n0 ) ,即 n0 i ? j a ,于是
n0 i ? j ,而 1 ≤ i ? j ≤ n0 ? 1 ,矛盾!
因此 1 + ta, t = 0,1, 2,L , n0 ? 1 就是 1, 2,L , n0 的一个排列; 并且相邻两数之差满足: 1 + (i + 1) a ? 1 + ia ≡ (1 + (i + 1) a ) ? (1 + ia ) ≡ a (mod n0 ) ,

1 + ia ? 1 + (i + 1)a ≡ (1 + ia) ? (1 + (i + 1)a) ≡ ?a ≡ b (mod n0 ) …… ⑤
由于 1 + ta, t = 0,1, 2,L , n0 ? 1 中的数,任两个不等,1 ≤ 1 + ta ≤ n0 ,故相邻两数之差(大 数减小数)属于集 {1, 2,L , n0 } ,而 {1, 2,L , n0 } 为模 n0 的一个完全剩余系,故其中与 a 同 余的只有 a ,与 b 同余的只有 b ,因此由⑤中两式得,相邻两数之差,要么是 a ,要么是 b . 因此,要想在此圆周上所取的数不含相邻数,至多只能取 ? 数时,其中必有两数相邻,其差为 a 或 b .

? n0 ? ?n ? 个数.而当取出 ? 0 ? + 1 个 ? ?2? ?2?

(2) 、当 r ≥ 1 时,由③得 0 ≤ u < n0 , 0 ≤ v < n0 ,即 u, v ∈ {0,1, 2,L , n0 ? 1} ,②式化为,
v ? u = m0 或 u ? v = n0 ? m0 ,这与④的形式完全相同,因此仿照 (1) 的讨论可知,对于每
个 r , r = 1, 2,L , d ? 1 ,我们也分别可以得到一个含有 n0 个数的圈,使得相邻两数之差,要 么是 a ,要么是 b .为了在每个圈上不取到相邻的数,至多只能取 ?

? n0 ? ? 个数.而当取出 ?2?

? n0 ? ? 2 ? + 1 个数时,其中必有两数相邻,其差为 a 或 b . ? ?
并且,任两个圈上的数显然不同:假若 id + r1 = jd + r2 ,则 id + r1 ≡ jd + r2 ( mod d ) , 于是 r1 ≡ r2 ( mod d ) ,得 r1 = r2 ,矛盾! 若取出的元素个数 s ≥ d ?

? n0 ? ?n ? + 1 ,则上述 d 个圈中,必有一个圈至少取出了 ? 0 ? + 1 个 ? ?2? ?2?

数,导致该圈上必有两数相邻,即有 ai , a j ,使 n ( m + as ? at ) ; 另一方面,若取出的元素个数 s ≤ d ?

? n0 ? ? n0 ? ? 时,则有取法,即在每个圈上各取 ? 2 ? 个数, ?2? ? ?
7

使得任两数在圈上都不相邻,这时 n ? m + ai ? a j ) , ( 因此,适合条件的 k 的最小值是 k = d ?

n ? n0 ? (其中 d = ( m, n), n0 = ) . ? +1 , d ?2?

4 、 18 支足球队进行单循环赛,即每轮将 18 支球队分成 9 组,每组的两队比赛一场, 下一轮重新分组进行比赛,共赛 17 轮,使得每队都与另外 17 支球队各赛一场.按任意可行 的程序比赛了 n 轮之后,总存在 4 支球队,它们之间总共只赛了一场; 求 n 的最大可能值.
解:先构造一种比赛方案:将 18 支球队顺次编号为 1, 2,L ,18 ,并按奇数与偶数分成两 个子集:A = {1,3,5,L ,17} ,B = {2, 4,6,L ,18} , 再将每场比赛的队 ( x, y ) 依照其和 x + y 被 9 除的余数情况而规定轮次,并且先在同奇偶的队之间各安排 4 场,再将“挂单”的两个 队安排一场比赛;即要求,第 r 轮中每场比赛的队 ( x, y ) 满足: x + y ≡ r (mod 9) .即 第一轮的 ( x, y ) : x + y ≡ 1 (mod 9) : ?

?(1, 9), (3, 7), (11,17), (13,15) , (5,14) ; ?(2,8), (4, 6), (10,18), (12,16) ?(3,17), (5,15), (7,13), (9,11) , (1,10) ; ?(2,18), (4,16), (6,14), (8,12)

第二轮的 ( x, y ) : x + y ≡ 2 (mod 9) : ?

第三轮的 ( x, y ) : x + y ≡ 3 (mod 9) : ?

?(1,11), (3, 9), ( 5, 7 ), (13, 17) , (6,15) ; ?(2,10), (4,8), (12,18), (14,16) ?( 1, 3), ( 5, 17 ), (7,15), ( 9, 13) , (2,11) ; ?(14,18), (6,16), (8,14), (10,12)

第四轮的 ( x, y ) : x + y ≡ 4 (mod 9) : ?

第五轮的 ( x, y ) : x + y ≡ 5 (mod 9) : ?

?(1,13), (3,11), (5,9), (15,17) , (7,16) ; ?(2,12), (4,10), (6,8), (14,18) ?(1, 5 ), (7,17), (9,15), (11,13) , (3,12) ; ?(2, 4), (6,18), (8,16), (10,14) ?(1,15), ( 3, 13), (5,11), ( 7, 9 ) , (8,17) ; ?(2,14), (4,12), (6,10), (16,18)

第六轮的 ( x, y ) : x + y ≡ 6 (mod 9) : ?

第七轮的 ( x, y ) : x + y ≡ 7 (mod 9) : ?

第八轮的 ( x, y ) : x + y ≡ 8 (mod 9) : ?

?(1, 7), ( 3, 5), ( 9,17 ), (11, 15) , (4,13) ; ?(2, 6), (8,18), (10,16), (12,14)

第九轮的 ( x, y ) : x + y ≡ 9 (mod 9) : ?

?(1,17), (3,15), (5,13), (7,11) , (9,18) ; ?(2,16), (4,14), (6,12), (8,10)

8

在这九轮比赛中,共含有 9 × 4 = 36 个(奇、奇)型搭配, 36 个(偶、偶)型搭配, 而 36 = C9 ,故知在这九轮中,一切(奇、奇)型搭配, (偶、偶)型搭配均已出现,即任
2

一对(奇、奇)号球队都比赛过,任一对(偶、偶)号球队也都比赛过. 于是,当赛完上述的九轮后,在这 18 支球队中任取四个队,设其编号为 a, b, c, d ,由 于 a, b, c 三数中必有两数同奇偶,设为 a, b ,则他们已赛过,去掉 a ,在 b, c, d 三数中,又 有两数同奇偶,他们也已赛过;因此若按这种分组方式进行了 9 轮比赛之后,任何四个队之 间都至少比赛过两场,于是适合条件的 n 必应满足: n ≤ 8 . 此外,我们尚需补充说明,上述的 9 轮比赛确实是一种符合要求安排中的前 9 轮.即, 在以上 9 轮赛完后,我们还可以继续安排后续 8 轮比赛,从而保证全部 17 轮比赛可以顺利 进行下去. 为此,作两个同心圆盘,且各分成 9 个相等的扇形小格,按反时针方向顺次将九个奇数

1,3, 5,L ,17 以及九个偶数 2, 4, 6,L ,18 分别填入外盘及内盘的格子中,然后转动内盘,使
得在前九轮中已经比赛过的每一对(奇、偶)型搭配,分别位于对齐后的同一个小扇形中, 于是得到图一. 在前九轮比赛中,外圈的任两队之间,内圈的任两队之间,以及任一个小扇形中的两队 之间都已比赛过. 为叙述方便,令向量 A = ( a1 , a2 ,L , a9 ) = (1, 3,5, 7, 9,11,13,15,17) ,

B = (b1 , b2 ,L , b9 ) = (10,12,14,16,18, 2, 4, 6,8) ,这样图一便可改记为图二.
在前九轮比赛中, ai , a j 已赛过, bi , b j 已赛过, ai , bi 已赛过,而 ai , b j 未赛过,

i ≠ j , i, j ∈ {1, 2,L ,9} .

11 13

9 a7

a6

a5

2 18 7 16 4 14 5 15 6 8 10 12 17 3 1 图图

b6 b5 a4 b4 b7 b3 a a8 b 8 3 b9 b b2 1 a9 a2 a1 图图

今用下述方法安排后续 8 轮比赛: 将内盘固定,让外盘绕中心作反时针旋转,每次转过一格,对齐后,便在每一扇形内的两队 之间各安排一场比赛, 9 个扇形中的两队共安排出 9 场比赛,这样便构成一轮比赛;八次旋

9

转共得 8 轮比赛,其中第 k 次旋转后的 9 场比赛是:

{a1

b1+ k , a2

b2+ k ,L , a9

b9 + k } , k = 1, 2,L ,8 , (约定 bi +9 = bi ) 经过这样的 8 轮比赛后, ,

所有 ai , b j 都已赛过, (i ≠ j , i, j = 1, 2,L ,9) ,从而在全部 17 轮比赛过后,这 18 支球队的 任两支球队都赛过一场,且仅赛过一场,因此这 17 轮比赛是符合要求的比赛,从而它的前 九轮及后八轮比赛都合要求. 接下来考虑比赛轮数 n = 8 的情况, 我们若将上述 17 轮比赛的顺序颠倒过来, 即先安排 后面的 8 轮比赛,再安排前面的 9 轮比赛,显然,这也是一种可行的安排. 经过这样的 8 轮比赛后,18 支球队 a1 , a2 ,L , a9 , b1 , b2 ,L , b9 满足:ai , a j 未赛过,bi , b j 未赛过, ai , bi 未赛过,而 ai , b j (i ≠ j ) 皆已赛过. 今从 18 支球队中任取四个队,据对称性,不妨设,取自 A 中的球队较多,则有以下三 种情况: (10 ) 、若四个队全取自 A 中,则这四个队两两之间皆未赛过;

(20 ) 、若三个队来自 A ,一个队来自 B ,设为 ai , a j , ak 及 br ,由于 i, j , k 中至少有两个数
异于 r ,因此 br 至少与 ai , a j , ak 中的两个队赛过,于是这四个队之间至少赛过两场;

(30 ) 、若两个队来自 A ,两个队来自 B ,设为 ai , a j 与 bk , br ,则 bk 至少和 ai , a j 中的一个
队赛过, br 也至少和 ai , a j 中的一个队赛过,于是这四个队之间至少赛过两场. 因此,按这种分组方式比赛 8 轮之后,任何四个队之间,或者没有赛过,或者至少赛了 两场,也就是不存在恰好只赛了一场的情况. 于是适合条件的 n 应当满足: n ≤ 7 . 下面证明, n 的最大值就是 7 .即需证,无论每一轮怎样分组,当比赛轮数 n ≤ 7 时, 其中必有四个队,他们两两之间恰好只比赛了一场. 设 18 支球队按任一可行的方式分组,并赛完 n 轮 ( n ≤ 7) ,则每一队恰好赛过 n 场(与 n 个 队赛过) ,而与另外的 17 ? n 个队未赛过(这里注意, 17 ? n ≥ 10 ) . 今用 18 个点表示这 18 支球队, 如果 u , v 两队赛过, 则在点 u , v 间连一条边, 于是得 18 阶 图 G , G 的每个顶点 v 的度数皆为 n (记为 d (v ) = n ) . 在 G 中取两个不相邻的顶点 a1 , a2 ,因 d ( a1 ) + d ( a2 ) = 2n ≤ 14 ,故在 G 中异于 a1 , a2 的

16 个点中,必有一点 a3 ,它与 a1 , a2 都不相邻.
于是 M 1 = {a1 , a2 , a3 } 中的点互不相邻,将 G 中由其余 15 个顶点组成的集记为

N1 = {b1 , b2 ,L , b15 } ,由于 M 1 的三点互不相邻,每点的度数为 n ,故连接 M 1 , N1 之间的边

10

恰有 3n 条, (注意 3n ≤ 21 ) .

(10 ) 、若集合 N1 中有一点,例如 b1 ,向集合 M 1 只发了一条边,则四点 a1 , a2 , a3 , b1 为
所求(它们之间恰有一条边) ;

(20 ) 、若 N1 中的每个点,或者向 M 1 不发边,或者向 M 1 发出的边数 ≥ 2 ,由于连接 M 1 , N1 之间的总边数 3n ≤ 21 ,则 N1 的 15 个点之中,向 M 1 发边的点不能多于 10 个点,即
至少有 5 个点与 M 1 中的点不相邻,设这 5 点为 b1 , b2 ,L , b5 ; 若这 5 点中有某两点相邻,设为 b1 , b2 ,则四点 a1 , a2 , b1 , b2 为所求; 若 {b1 , b2 ,L , b5 } 中的任两点不相邻,则将其并入 M 1 ;令 M 2 = M 1 U {b1 , b2 ,L , b5 } , 这时 M 2 中有 8 个点.

(30 ) 、改记 M 2 = {u1 , u2 ,L , u8 } ,其余 10 点构成集合 N 2 = {v1 , v2 ,L , v10 } .
集 M 2 中, 任两点不相邻, 每点的度数为 n , 则连接 M 2 , N 2 之间的边数为 8n , 于是 N 2 的 10 个点之中必有一点向 M 2 发出的边数 k ≤ n ? 1 ≤ 6 ,设此点为 v10 . 若 1 ≤ k ≤ 6 ,即是说, v10 至少与 M 2 中的两个点不相邻,且必与 M 2 中的一点相邻,数 v10 与 u1 , u2 不相邻,而与 u3 相邻,则四点 u1 , u2 , u3 , v10 为所求; 若 k = 0 ,即 v10 与 M 2 中的每个点都不相邻,改记 v10 为 u9 ,且将其并入 M 2 ; 令 M 3 = M 2 U {v10 } = {u1 , u2 ,L , u9 } , N 3 = N 2 \ {v10 } = {v1 , v2 ,L , v9 } ;

M 3 中任两点不相邻,每一点度数为 n ,故连接 M 3 , N 3 之间的边有 9n 条;由于 N 3 中的 9 个
点,每点的度数也是 n ,则 N 3 的每点必须向 M 3 发出 n 条边,故 N 3 中任两点也不相邻. 取 v1 ∈ N 3 , 由于 v1 向 M 3 发出 n 条边, n ≤ 7 , M 3 中必有两点与 v1