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 不相邻, 而 故 设为 u1 , u2 , 且必有一点与 v1 相邻,设为 u3 ,则四点 u1 , u2 , u3 , v1 为所求. 综以上讨论得,当比赛轮数 n ≤ 7 时,按任何可行的方案分组,当赛完 n 轮后,总有四个队, 它们之间恰好只赛了一场.因此, n 的最大可能值是 nmax = 7 .

二、旋转、置换(群)构造法

5 、集合组 ? 由 11 个五元集 A1 , A2 ,L , A11 组成,其中任意两个集合的交都不是空集,
11

令A=

U A = { x , x ,L, x } , ?x ∈ A , ? 中含有元素 x 的集合数目为 k ,记
i 1 2 n

11

i

i

i

i =1

m = max {k1 , k2 ,L , kn } ,求 m 的最小值.

解:易得

∑k
i =1

n

i

= 55 …… ①

这一事实利用“算两次”原理可立即得到:作一张 n × 11 的表,若 xi ∈ A j ,则在表中 第 i 行、 j 列的交叉处填写一个“*”号;

A1 x1 x2
… … * *

A2

A3
*







A10

A11
*

* … * …

* … … *

xn

于是若按行计算,第 i 行共有 ki 个“*”号,全表共有

∑k
i =1 n

n

i

个“*”号,再按列计算,由

于每列恰有 5 个“*”号,全表的“*”号数是 55 个,因此 含有 xi 的 ki 个集合,共作成 Cki =
2

∑k
i =1

i

= 55 .

ki (ki ? 1) 个“集合对” ,由于任两个集合的交不是空 2

集,故和式

∑C
i =1

n

2 ki

包含了所有的“集合对” ,其中含有重复(因为有些集合对可能不止一个

公共元,有些元素可能属于多个集合) . 据条件,集合组 ? 中的 11 个集 A1 , A2 ,L , A11 两两的交不空,它们构成 C11 = 55 个不重
2

复的“集合对” ,因此

∑ Ck2i ≥ 55 ,即
i =1 n

n

∑ k (k ? 1) ≥ 110
i =1 i i n

n

… ②,

据 max ki = m ,则由②, 110 ≤

∑ ki (ki ? 1) ≤ ∑ ki (m ? 1) = 55(m ? 1) ,所以 m ≥ 3 .
i =1 i =1

12

再证 m > 3 ,反证法,若有 m = max ki = 3 ,即对任何 i ,皆有 ki ≤ 3 ,这时将会导致所 有 ki = 3 ;事实上,若有某个 ki ≤ 2 ,即含有元素 xi 的集合不多于 2 个,于是集合组 ? 中至 少有 9 个集不含 xi , 设不含 xi 的集合是 A1 , A2 ,L , A9 , A10 含 xi , A10 = { xi , a, b, c, d } , 而 记 由于 A10 I Ai ≠ ? ,则 A10 I Ai ? {a, b, c, d } , i = 1, 2,L , 9 ,因此 a, b, c, d 四个元素中, 必有一个元素,例如 a ,要属于 ? 中至少三个集合,即属于 A1 , A2 ,L , A9 , A10 中至少四个 集合,这与 max ki = 3 矛盾!于是所有 ki = 3 ;但这又导致 55 = 所以 m > 3 ,即 m ≥ 4 . 再说明, m = 4 是可以取到的,为此,采用几何 构造法, 考虑如图的五角星,它的 10 个结点以及各边中点, 共得 15 个点,分别标志为 1, 2,L ,15 ,今构造集合

∑k
i =1

n

i

= 3n ,矛盾!

11

12

7 6 8 9 10 1 13

5 4 3 2 14

15

A = {1, 2,L ,15} 的 11 个五元集如下: 由五角星的外
接圆上 5 个点,五条边上的各 5 个点, 五个形如 (1, 4,8, 6,11) 的“十字架”上的 5 个点,

分别作为一个集,这样共得 11 个集,它们分别是: {11,12,13,14,15} ,

{1, 2,3,13,15} , {3, 4,5,11,14} , {5, 6, 7,12,15} , {7,8,9,11,13} , {9,10,1,12,14} , {1, 4, 8, 6,11} , {3, 6,10, 8, 12} , {5, 2,8,10,13} , {7, 4,10, 2,14} , {9, 2, 6, 4, 15} ,
因此, m 的最小值为 4 . (注意,也可将集合 {11,12,13,14,15} 换成集合 {1,3,5, 7,9} , 同样可以确保任两个集的交不空. ) 6 、在一个圆周上给定十二个红点;求 n 的最小值,使得存在以红点为顶点的 n 个三角 形,满足:以红点为端点的每条弦,都是其中某个三角形的一条边. 解:设红点集为: A = A1 , A2 ,L , A12 ,过点 A1 的弦有 11 条,而任一个含顶点 A1 的 三角形,恰含两条过点 A1 的弦,故这 11 条过点 A1 的弦,至少要分布于 6 个含顶点 A1 的三 角形中; 同理知,过点 A i (i = 2, 3,L ,12) 的弦,也各要分布于 6 个含顶点 Ai 的三角形中,这样 就需要 12 × 6 = 72 个三角形,而每个三角形有三个顶点,故都被重复计算了三次,因此至

{

}

13

少需要

72 = 24 个三角形. 3 再说明,下界 24 可以被取到.不失一般性,考虑周长为 12 的圆周,其十二等分点为红
2

点,以红点为端点的弦共有 C12 = 66 条.若某弦所对的劣弧长为 k ,就称该弦的刻度为 k ; 于是红端点的弦只有 6 种刻度,其中,刻度为 1, 2,L ,5 的 弦各 12 条,刻度为 6 的弦共 6 条; 如果刻度为 a, b, c ( a ≤ b ≤ c )的弦构成三角形的 三条边,则必满足以下两条件之一: 或者 a + b = c ;或者 a + b + c = 12 ; 于是红点三角形边长的刻度组 ( a, b, c ) 只有如下 12 种可能: (1,1, 2 ) , ( 2, 2, 4 ) , ( 3,3, 6 ) ,

11 10 9 8 7

12

1 2 3 4

6

5

( 2,5,5) , (1, 2,3) , (1,3, 4 ) , (1, 4,5) , (1,5, 6 ) , ( 2,3,5) , ( 2, 4, 6 ) , ( 3, 4,5) , ( 4, 4, 4 ) ;
下面是刻度组的一种搭配:取 (1, 2,3) , (1,5,6 ) , ( 2,3,5 ) 型各六个, ( 4, 4, 4 ) 型四个;这 时恰好得到 66 条弦,且其中含刻度为 1, 2,L ,5 的弦各 12 条,刻度为 6 的弦共 6 条; 今构造如下:先作 (1, 2,3) , (1,5,6 ) , ( 2,3,5 ) 型的三角形各六个, ( 4, 4, 4 ) 型的三角形 三个,再用三个 ( 2, 4, 6 ) 型的三角形来补充.

(1, 2,3) 型六个:其顶点标号为: {2,3,5} , {4,5, 7} , {6, 7,9} , {8,9,11} , {10,11,1} , {12,1,3} ; (1,5, 6 ) 型六个:其顶点标号为: {1, 2, 7} , {3, 4,9} , {5, 6,11} , {7,8,1} , {9,10,3} , {11,12,5} ;
其顶点标号为: 2, 4,11} , {4, 6,1} , {6,8,3} , {8,10,5} , {10,12, 7} , {12, 2,9} ; ( 2,3,5) 型六个: {

( 4, 4, 4 ) 型三个:其顶点标号为: {1,5,9} , {2, 6,10} , {3, 7,11} ; ( 2, 4, 6 ) 型三个:其顶点标号为: {4, 6,12} , {8,10, 4} , {12, 2,8} .
(每种情况下的其余三角形都可由其中一个三角形绕圆心适当旋转而得) . 这样共得到 24 个三角形,且满足本题条件,因此, n 的最小值为 24 .

7 、在一个圆周上给定 8 个点 A1 , A2 , L , A8 .求最小的正整数 n ,使得以这 8 个点为
顶点的任意 n 个三角形中,必存在两个有公共边的三角形. 解:先考虑两两无公共边的三角形个数的最大值 r .

8 个点,每两点连一条弦,共得 C82 = 28 条弦,若每条弦只属于一个三角形,则这些弦

14

至多能构成两两无公共边的三角形个数 r ≤ ? ? = 9 个, 但若有 9 个这样的三角形, 共得 27 ?3? 个顶点,则八边形必有一顶点,至少属于 4 个三角形,设为 A8 ,共顶点 A8 的 4 个三角形,

? 28 ?

A8 的对边都是 A1 , A2 ,L , A7 之中的两点连线,其中必有一点,设为 A k ,出现了两次,那
么相应的两个三角形将有一条公共边 A8 A k ,这不可能;故 r ≤ 8 . 另一方面,当 r = 8 时,我们确实可以作出这样的 8 个 三角形,使得其中任两个三角形都无公共边; 注意这样的 8 个三角形,共产生 24 个顶点,若使每点 所参与的三角形个数都小于 4 , 那么每点恰好属于 3 个三角 7 形,也就是说,每个点,恰与其余七点中的 6 点有边相连, 而与另一点不连边;考虑每点度数皆为 6 的八阶图 G : 为简明起见, 取圆周的八等分点作为图 G 的八个顶点, 8 作 8 阶完全图,然后去掉其中 4 条直径,这样共得 24 条边, 且每点均属于 6 条边; 在由这些边所构成的三角形中, 选取 八个等腰三角形:

6

5 4

3 1 2

(1, 2,3), (3, 4,5), (5, 6, 7), (7,8,1) 以及 (1, 4, 6), (3, 6,8), (5,8, 2), (7, 2, 4)
它们两两无公共边;每一组的四个三角形, ( 皆可由其中一个三角形绕圆心适当旋转而得到) . 因此, r = 8 ,从而所求的最小值 n = r + 1 = 9 . 8 、将时钟盘面上标有数字 1, 2,L ,12 的十二个点分别染上红、黄、蓝、绿四色,每色 三个点,现以这些点为顶点构作 n 个凸四边形,使其满足: ( 1 )每个四边形的四个顶点染有不同的颜色; ( 2 )对于其中任何三个四边形,都存在某一色,染有该色的三个顶点所标数字互不相同. 求 n 的最大值. 解:为叙述方便,改用 A, B, C , D 分别表示这四种颜色,而同色的三点,则分别用

a1 , a2 , a3 ; b1 , b2 , b3 ; c1 , c2 , c3 以及 d1 , d 2 , d3 来表示.
今考虑其中一色,例如 A 色;若在这 n 个四边形中, A 色点 a1 , a2 , a3 出现的次数分别为

n1 , n2 , n3 ,则 n1 + n2 + n3 = n ,设 n1 ≥ n2 ≥ n3 ;
如果 n ≥ 10 ,则 n1 + n2 ≥ 7 ;再考虑这 7 个四边形(其 A 色顶点要么是 a1 ,要么是 a2 ) , 它们中 B 色点 b1 , b2 , b3 出现的次数分别为 m1 , m2 , m3 ,则 m1 + m2 + m3 = 7 ,据对称性,可 设 m1 ≥ m2 ≥ m3 ,则 m3 ≤ 2 ,即 m1 + m2 ≥ 5 ;

15

继续考虑这 5 个四边形(其 A 色顶点要么是 a1 ,要么是 a2 ; B 色顶点要么是 b1 ,要么 ,它们中 C 色点 c1 , c2 , c3 出现的次数分别为 k1 , k 2 , k3 ,则 k1 + k 2 + k3 = 5 ,据对称性, 是 b2 ) 可设 k1 ≥ k2 ≥ k3 ,则 k3 ≤ 1 ,即 k1 + k 2 ≥ 4 ; 最后考虑这 4 个四边形,记为 T1 , T2 , T3 , T4 (其 A 色顶点要么是 a1 ,要么是 a2 ; B 色顶 ,由于 D 色点只有三个,故其中 点要么是 b1 ,要么是 b2 ; C 色顶点要么是 c1 ,要么是 c2 ) 必有两个四边形,其 D 色点相同,设 T1 , T2 的 D 色点都为 d1 ; 那么,三个四边形 T1 , T2 , T3 中,无论哪种颜色的顶点,所标数字皆有重复,这与条件 (2) 相矛盾!因此, n ≤ 9 . 再说明,最大值 n = 9 可以取到;采用构造法,我们只要作出这样的九个四边形即可.
D3 C3 B1 C1 D1 B2 A1 B3 C3 C2 D2 D2 B2 D1 C2 B1 A2 C2 C1 D3 D3 B2 D2 C1 B1 A3 B3 B3

C3

D1

作三个 “同心圆环图” 给出标号, , 并适当旋转相应的圆, 标号对齐后, 图中的每根线 (半 径) 上的四个点分别表示一个四边形的四个顶点颜色及其标号, 九条半径共给出九个四边形, 且都满足条件( 1 ) ; 再说明,它们也满足条件( 2 ) :从中任取三条半径(三个四边形) ; 如果三条半径(三个四边形)来自同一个图,则除了 A 色之外,其余 B, C , D 每色的顶 点,三数全有; 如果三条半径(三个四边形)分别来自三个图,则 A 色的顶点,三数全有; 如果三条半径(三个四边形)分别来自两个图:将三个图分别称为 A1 图、 A2 图、 A3 图, 每图的三条半径分别称为“向上半径”“向左半径”“向右半径” 、 、 ;且分别记为 S , Z , Y . 来自两个图的三条半径,如果“向上”“向左”“向右”三种半径都有,那么相应的三 、 、 个四边形, B 色的顶点,三数全有; 如果三条半径,只涉及两个图,两个方位,将图 A1 , A2 , A3 分别简记为 1, 2,3 ,则按三个 图的搭配情况,可得下表:

16

S Z Y

1,2 1,2 1 2

2 1,2 1,2 1

1 2 1,2 1,2

S Z Y

1,2 1,2 2 1

1 1,2 1,2 2

2 1 1,2 1,2

产产C色色色

产产D色色色

S Z Y

1,3 1,3 1 3 1 1,3 1,3 3

3 1 1,3 1,3

S Z Y

1,3 1,3 1 3

3 1,3 1,3 1

1 3 1,3 1,3

产产C色色色

产产D色色色

S Z Y

2,3 2,3 3 2 3 2,3 2,3 2

2 3 2,3 2,3

S Z Y

2,3 2,3 2 3 2 2,3 2,3 3

3 2 2,3 2,3

产产C色色色
因此本题所求的 n 的最大值为 9 . 三、几何构造法

产产D色色色

9 、设有 m + n 个正整数 a1 , a2 ,L , am 及 b1 , b2 ,L , bn ,满足: ∑ ai = ∑ b j .
i =1 j =1

m

n

证明: 可以从 m × n 方格表中选出 m + n ? 1 个方格, 在选出的每格中各填写一个自然数, 使得表中第 i 行的填数和为 ai ,而第 j 列的填数和为 b j .

证:采用几何构造法,设

∑ a = ∑b
i =1 i j =1

m

n

j

= S ,则 S 为正整数,在坐标系数第一象限作

一个边长为 S 的正方形 OACB , 在 OA 上顺次截出长度为 a1 , a2 ,L , am 的线段,得到 m ? 1 个分点 A1 , A2 ,L , Am ?1 ,其 中, OA1 = a1 , A1 A2 = a2 , A2 A3 = a3 ,L , Am ?1 A = am ; (称为 A 型线段)

′ 2 在 OB 上顺次截出长度为 a1 , a2 ,L , am 的线段,得到 m ? 1 个分点 A1 , A′ ,L , A′ ?1 ,其 m ′ ′ 2 中, OA1 = a1 , A1 A′ = a2 , A′ A′ = a3 ,L , A′ ?1 B = am ; 2 3 m
17

又在 OB 上顺次截出长度为 b1 , b2 ,L , bn 的段, 得到 n ? 1 个分点 B1 , B2 ,L , Bn ?1 , 其中,

OB1 = b1 , B1 B2 = b2 , B2 B3 = b3 ,L , Bn ?1 B = bn ; (称为 B 型线段) ′ ′ ′ 在 OA 上顺次截出长度为 b1 , b2 ,L , bn 的段,得到 n ? 1 个分点 B1 , B2 ,L , Bn ?1 ,其中, ′ ′ ′ ′ OB1′ = b1 , B1′B2 = b2 , B2 B3 = b3 ,L , Bn ?1 A = bn ; ′ ′ ′ 过诸点 A1 , A2 ,L , Am ?1 , B1 , B2 ,L , Bn ?1 分别作 OA 的垂线,再过点 B1 , B2 ,L , Bn ?1 ,
′ 2 A1 , A′ ,L , A′ ?1 分别作 OB 的垂线.过第 i 条 A 型线段两端点的垂线所夹矩形长条称为第 i m
个 A 型条,过第 j 条 B 型线段两端点的垂线所夹矩形长条称为第 j 个 B 型条, ,它们将线段 OA , 线段 OA, OB 上的分点各有 m + n ? 2 个(其中有些分点可能是重合)

OB 各分成 m + n ? 1 段,每一段的长度都是整数(重合的分点构成的线段长度为 0 ) ; 两组垂线构成了许多正方形,我们主要关注对角线在 OC 上且未被其它正方形所覆盖的 正方形,称为单纯正方形(有些正方形可能蜕化成一个点) ,这种正方形共有 m + n ? 1 个,
它们的边长皆为非负整数; 现在我们这样在 m × n 方格表上填数: 如果一个单纯正方形 T 夹在第 i 个 A 型条与第 j 个

B 型条中,则将正方形 T 的边长填入方格表第 i 行、 j 列的交叉处;由于这些单纯正方形的
对角线覆盖了正方形 OACB 的对角线,且互不重叠,所以第 i 个 A 型条中的单纯正方形的 边长之和恰等于第 i 个 A 型条的宽度 ai , j 个 B 型条中的单纯正方形的边长之和恰等于第 第

j 个 B 型条的宽度 b j ,即有,表中第 i 行的填数和为 ai ,而第 j 列的填数和为 b j .
因此结论得证. 下面的例子是 ( a1 , a2 , a3 ) = (3, 5, 4), (b1 , b2 , b3 , b4 ) = (1, 2,3, 6) 的情形.
B
4

C

1

2 0 3 2 4

2

B3
3

B2
2

B1 1 O

A1

A2

A

2 2 10 、一百个正数 a1 , a2 ,L , a100 满足: a1 + a2 + L + a100 = 3, a12 + a2 + L + a100 > 1 ,

18

证明: a1 , a2 ,L , a100 中必有三数之和大于 1 . 证:据对称性,不妨设 a1 ≥ a1 ≥ L ≥ a100 ,只要证, a1 + a2 + a3 > 1 ;反证法,假若

a1 + a2 + a3 ≤ 1 ,作三个边长为 1 的正方形,拼成一个 3 × 1 矩形,再把边长为 a1 , a2 ,L , a100
的小正方形 [ a1 ] , [ a2 ] , [ a3 ] ,L , [ a100 ] 一个接一个依次放入矩形中,恰好铺成由 A 到 H 的一 长条,记为 L ,据反证法假设知,小正方形 [ a1 ] , [ a2 ] , [ a3 ] 都在大正方形 ABCD 内,长条 L 含于正方形 ABCD 内的这一部分,被 a1 × 1 的矩形 M 所覆盖,而 L 落入大正方形 CDEF 中 的部分当被 a2 × 1 的矩形 N1 所覆盖,L 落入大正方形 EFGH 中的部分当被 a3 × 1 的矩形 K1 所覆盖,因此全体小正方 形的面积和应不大于三个 矩 形 M , N1 , K1 的 面 积 和;另一方面,由于

A
a1 a2 a3

a1 M N2 K2

a2

a3

D
??? ???

E
N1 K1
??? ???

H

a1 + a2 + a3 ≤ 1 ,我们可
以 在正 方形 ABCD 中 剪 出 a1 ×1, a2 ×1, a3 × 1 的 三

B

C

F

G

个矩形 M , N 2 , K 2 ;因此可以将矩形 N1 , K1 分别放置于大正方形 ABCD 中的 N 2 , K 2 处, 于是,全体小正方形的面积和不大于正方形 ABCD 的面积,即 a1 + a2 + L + a100 ≤ 1 ,此为
2 2 2

矛盾!因此假设不真,从而本题结论成立.

11 、平面上给定 n 个点 (n ≥ 3) ,无三点共线,现将每两点用一线段连接,并在每条线
段上配置一个箭头,以给定点为顶点的三角形称为“环形”的,如果从任一顶点出发,沿箭 头方向可环绕三角形周界行走一周,而返回原出发顶点; 试求环形三角形个数的最大值与最小值. 解:配置箭头后的三角形只有“环形”与“非环形”两种形状,因此, 环形三角形个数 ? ( n) + 非环形三角形个数 f ( n) = 全体三角形个数 = Cn .
3

先求 f ( n) ,我们注意到,一个三角形是“非环形”的,当且仅当其三个顶点中,恰有 一个顶点发出两个箭头,也有一个顶点收到两个箭头.我们将“发自同一顶点的一对箭头” 或者“指向同一顶点的一对箭头”统称为一个“同型对” . 于是,一个“非环形”三角形恰有两个“同型对” .对于一个确定的顶点 P 而言,关联 P 的每一个“同型对” ,恰好产生一个“非环形”三角形. 设 P 是任一个给定的点,以 P 为端点的线段共有 n ? 1 条,设点 P 发出 k 个箭头,收到
19

n ? 1 ? k 个箭头,自 P 发出的 k 个箭头,组成 Ck2 个同型对,收到的 n ? 1 ? k 个箭头,组成
2 Cn2?1? k 个同型对,因此关联 P 的同型对有 S = Ck2 + Cn ?1? k =

(n ? 1)(n ? 2) ? k (n ? 1 ? k ) 个. 2

为求 S 的最小值,即需求 k ( n ? 1 ? k ) 的最大值. 当 n 为奇数,则在 k =

n ?1 (n ? 1)2 时, k ( n ? 1 ? k ) 有最大值 ; 2 4

此时 S min

(n ? 1)(n ? 2) (n ? 1)2 (n ? 1)(n ? 3) = ? = ; 2 4 4

当 n 为偶数,则在 k =

n n 或 ? 1 时, 2 2 n(n ? 2) k (n ? 1 ? k ) 有最大值 ; 4 (n ? 1)(n ? 2) n(n ? 2) (n ? 2) 2 ? = . 2 4 4 nS 个,当每个点所关联的 2

此时 S min =

让 P 跑遍全部 n 个点,得到 n ? S 个“非环形”三角形,由于每个“非环形”三角形恰有 两个同型对,故均被计算了两遍,因此, “非环形”三角形共有

“非环形”三角形个数都取得最小值时,全体“非环形”三角形个数也取得最小值,所以,

? n(n 2 ? 1) ? n (n ? 1)(n ? 3) ,n为奇数 ? , n为奇数 ? ?2 ? 24 ? 4 3 f ( n) = ? ,则 ? ( n) = Cn ? f ( n) = ? 2 2 ? n ? (n ? 2) , ? n(n ? 4) , n为偶数 n为偶数 ?2 ? 24 4 ? ?
此值可以取到,构造法,考虑圆周的 n 等分点,对于不经过圆心的每条弦配置箭头时,可使 绕圆周成反时针方向(即,顺着箭头方向沿每条弦行走时,圆心总在左侧) ,而对于经过圆 心的弦(直径) ,箭头方向可任意配置,这样,每个点的出入箭头数至多相差一个. 再求环形三角形个数 ? ( n) 的最小值, (注意上面的方法不能用于此情形, 因为上面的公式是 对于每个点都使关联的“非环形”三角形个数取得最小值时求得的) . 我们指出,环形三角形个数 ? ( n) 的最小值为 0 .构造法,将 n 个点分别标号为 1, 2,L , n , 配置箭头按小数指向大数进行.

12 、设 S = {1, 2,L ,15} 的 n 个七元子集 A1 , A2 ,L , An 满足:

(10 ) 、 Ai I Aj ≤ 3 , 1 ≤ i < j ≤ n ;

(20 ) 、对于 S 的任何 3 元子集 M ,都存在某个 Ak ,使得 M ? Ak .
求这组子集个数 n 的最小值.

20

解:采用“元素跟踪”法, ?x ∈ S ,因 S 中有 15 个元素,其中含 x 的 3 元子集,共计
2 C14 = 91 (不重不漏).此外,若元素 x 在 m 个子集 Ak 中出现,每个 Ak 有 7 个元素,其中

m 含 x 的 3 元子集有 C6 = 15 个, 个这种子集 Ak 共收集到这种 3 元子集 15m(在不同的 7 元
2

子集 Ak 中,有些 3 元子集可能会出现重复,这是因条件 (1 ) 的缘故) (不漏但可重).于是

0

15m ≥ 91 .因 m 为整数,则 m ≥ 7 .
再从元素个数考虑, n 个 7 元子集 Ak 共得 7n 个元素(它们来自 S ,且有重复).另一 方面, S 中的每个元素 x 在诸 Ak 中至少出场 m ≥ 7 次,而这种 x 有 15 个,故 n 个集 Ak 中的 元素个数和至少是 15 × 7 = 105 个(可重,但为“至少重” )所以 7 n ≥ 105 ,则 n ≥ 15 . 以 下 说 明 n = 15 确 为 所 求 的 最 小 值 。 需 构 造 集 S = {1, 2,L15} 的 15 个 7 元 子 集

Ai , i = 1, 2,L15 ,使其覆盖 S 的全体 3 元子集(以下称为“三角形” ).
(注意,本题的构造过程是一项比前一阶段论证过程更为精细的工作,仍采用几何构造 法,以便于检验). 先计算一下 S 中的“三角形”个数,为 C15 = 455 个.
3

再分析 S = {1, 2,L15} 的数字结构,其中有 7 个偶数, 8 个奇数.进而对 S 中的“三角 形”按“顶点”分类.
3 1 (10 ) (偶 偶 偶)型三角形,共 C7 = 35 个; (20 ) (偶 偶 奇)型三角形,共 C72 ? C8 = 168 个; 1 (30 ) (奇 奇 偶)型三角形,共 C82 ? C7 = 196 个; (40 ) (奇 奇 奇)型三角形,共 C83 = 56 个.

为解决第一类(偶 偶 偶)型三角形,只须取

2 14 4

A1 = {2, 4, 6,8,10,12,14} 即可.而为满足 Ai I Aj ≤ 3 ,
每个后续的 Ai , (i = 2,L15) 至多只能含有 3 个偶数,并且

A2 , A3 ,L , A15 必需覆盖所有后三类三角形.因此,这 14 个

12

6

集,每个集必须取三个偶数,四个奇数. 10 8 先考虑偶数搭配.顺次将 7 个偶数填写于圆周的 7 个等 分点上, 易知圆内接正 4 边形只有三种长度的弦.将其搭配成一个三角形, 然后顺时针旋转 7 次,得到 7 个三角形:

(2, 4,8), (4, 6,10), (6,8,12), (8,10,14), (10,12, 2), (12,14, 4), (14, 2, 6) .
这组三角形有特征:任二个三角形恰有一个公共顶点,而无公共边;任一个偶点恰属于 三个三角形.每个三角形有三条边, 共得 21 条偶顶线段.任二条皆不相同.它恰好穷尽了所有

C72 = 21 个二元的偶数子集.
21

由于只有 7 个偶顶三角形,为组成 14 个 7 元子集,每个偶顶三角形必须使用二次,称 为一对“重置偶三角” ,对于“重置偶三角” ,需要将 8 个奇数分成互补的两组,不能有公共 元素,又因任两个“相异偶三角”恰有一个公共元,因此,与之搭配的四元奇数集,至少允 许有两个相同元素. 据此,我们来对 8 个奇数构成的集,设计 7 种互补分拆,使之满足条件. 将 8 个奇数 1,3, 5, 7,9,11,13,15 顺次填写于圆周的八等分点上,然后作 7 种形状的 4 元 分拆(四边形分拆) :

1
十字分拆(正方形分拆) (1, 5, 9,13) : 半圆分拆(薄梯形分拆) :

(3, 7,11,15)

15

3 5

(1, 3,5, 7)
矩形分拆:

(9,11,13,15) , (5, 7, 9,11)

(13,15,1,3)

13

(1, 3,9,11)

(5, 7,13,15) , (1, 7,9,15)

(3, 5,11,13)

11 9

7

梯形分拆(厚梯形分拆) :

(3,5,9,15)

(1, 7,11,13) , (3, 7,9,13)

(1,5,11,15)

易知,分拆有特征:同一分拆中的两组奇数,无公共元素(互补) ;不同分拆中的任二 组奇数(任二个四边形)恰有二个公共元(一条线段) ;任一条线段(一个奇数对)恰好出 现三次. 每个完全四边形有 6 条边, 14 个四边形共得 14 × 6 = 84 条边,而每条边重复三次,故 得 84 ÷ 3 = 28 条不同的边. 另一方面,八个奇数的集共有 C8 = 28 个二元奇子集.因此,这些四元奇数组穷尽了所
2

有二元奇数子集. 又知,每个四元组产生 4 个三元子集,且任二个四元组没有共同的三元子集(因至多一 条公共边).故 14 个四元组共得 14 × 4 = 56 个三元奇子集.它们恰穷尽了所有 C8 = 56 个三
3

元奇子集. 下面, 我们来完成后续 14 个 7 元子集 A2 , A3 ,L , A15 的搭配.首先,只要 14 个四元集一齐 用上,便完成了对所有 S 的奇顶三角形的覆盖;只要每一对“重置三角形”分别搭配一对互 补的 4 元分拆,便完成了对所有“偶偶奇”型三角形的覆盖. 在满足前述情况的前提下,我们作出搭配,使之满足对于全部“奇奇偶”型三角形(共 196 个)的覆盖. 据前面的讨论知,每个偶顶在七个三角形中出现三次,而每条“奇顶边”在 14 个四边 形中也出现三次. 由对称性,只要考虑 7 元子集对于偶数 2 和奇数对 (1, 2n + 1), n = 1, 2,L 7 所形成的“奇 奇偶”型三角形的覆盖.采用“先入为主”的办法.先从 2 和 (1,3) 入手. 含 2 的偶顶三角形有三个: (2, 4,8), (10,12, 2) 和 (14, 2, 6)
22

含 (1,3) 的四边形也有三个: (1, 3,5, 7), (1, 3,9,11) 和 (13,15,1, 3) 先让它们任意 1 对 1 搭配,而让其互补四边形与相应的重置偶顶三角形搭配,这样得到 六个 7 元组:

(2, 4,8) U (1, 3,5, 7) ; (2, 4,8) U (9,11,13,15) ; (10,12, 2) U (1,3,9,11) ; (10,12, 2) U (5, 7,13,15) ; (14, 2, 6) U (13,15,1, 3) ; (14, 2, 6) U (5, 7,9,11) ;
不含 2 的偶顶三角形有 4 个,为 (4, 6,10) , (12,14, 4) , (8,10,14) 和 (6,8,12) ,而含 1 的四边形(四元组)也剩了 4 个,为 (1,5,9,13) , (1, 5,11,15) , (1, 7, 9,15) 和 (1, 7,11,13) , 今让一对一搭配,而让其互补四边形与相应的重置偶顶三角形搭配,于是得到 8 个 7 元组: (*)

(4, 6,10) U (1, 5,9,13) , (4, 6,10) U (3, 7,11,15) ; (12,14, 4) U (1,5,11,15) , (12,14, 4) U (3, 7, 9,13) ; (8,10,14) U (1, 7, 9,15) , (8,10,14) U (3,5,11,13) ;
(*)

(6,8,12) U (1, 7,11,13) , (6,8,12) U (3, 5,9,15) ;
由(*) * )共得到 14 个 7 元子集 A2 , A3 ,L , A15 . ( 由于每一条奇顶线段(这种线段共 C8 = 28 条)在三个四边形中出现,而与这三个四边
2

形搭配的三个偶顶三角形含有全部偶点(例如,与 (9,15) 所在四边形搭配的偶顶三角形为

(2, 4,8) , (8,10,14) , (6,8,12) 这三个三角形含有 2, 4, 6,8,10,12,14 全部 7 个偶点,因此

(9,15,偶) 型三角形全被覆盖, 其余可类似检查, 全部检验共 28 次) .因此,28 × 7=196 个
奇奇偶型三角形全被覆盖. 于是, 15 个 7 元集 A1 , A2 , A3 ,L , A15 满足条件, n 的最小值为 15 . 四、图论、图形、图表构造法

13 、给定 133 个正整数 a1 , a2 ,L , a133 ,若其中至少有 799 对数互质,证明:其中必存
在四个数 a, b, c, d ,满足: ( a, b) = (b, c) = (c, d ) = ( d , a ) = 1 . 证:采用图形构造法:用点 A1 , A2 ,L , A133 分别代表这 133 个正整数, 若 (ai , a j ) = 1 ,则令相应点 Ai , A j 相邻,于是得 133 阶简单图 G ,设点 Ai 的度数为 d i ,
23

据条件,图 G 至少有 799 条边,不妨设,图 G 恰有 799 条边,否则我们就去掉其中一些边, 并不影响问题的性质; 与点 Ai 相邻的点有 d i 个,它们构成 Cdi =
2

d i (d i ? 1) 个“点对” ,据条件, 2
133 i =1

d1 + d 2 + L + d133 = 2 × 799 ;若记 M = ∑ Cd2i ,

D

1 133 1 133 1 133 则 M = ∑ d i2 ? ∑ d i = ∑ d i2 ? 799 , 2 i =1 2 i =1 2 i =1

A B

C

由柯西不等式,

133 1 133 2 1 (2 × 799) 2 2 = ? 7992 , di ≥ (∑ di ) 2 = ∑ 2 ×133 i =1 2 i =1 2 × 133 133

因此, M ≥

2 799 × 1465 798 ×1463 133 × 132 2 ? 7992 ? 799 = > = 798 × 11 = = C133 , 133 133 133 2

故在 A1 , A2 ,L , A133 中必有两个点 A, C ,其所邻接的点中, 具有相同的一个“点对” ,设为 B, D ,即 ABCD 为四边形,从而,

(a, b) = (b, c) = (c, d ) = (d , a ) = 1 .
14 、 n 个正整数 x1 , x2 ,L , xn 的和为 2009 ,如果这 n 个数既可分为和相等的 41 个组,
又可分为和相等的 49 个组,求 n 的最小值. 解: 设分成的 41 个组为 A1 , A 2 ,L , A 41 , 每组中的各数和皆为 49 , 称这种组为 A 类组; 而分成的 49 个组为 B1 , B2 ,L , B49 ,每组中的各数和皆为 41 ,称这种组为 B 类组. 显然,每个项 xk 恰好属于一个 A 类组和一个 B 类组,即同类组之间没有公共项,如果 两个组 A i , B j 中有两个公共项 xr , xt ,则可以将这两个数合并为一个项 xr + xt ,这样可使 n 值减少,故不妨设,每对 A i , B j 至多有一个公共项. 构造图论模型:今用点 u1 , u2 ,L , u41 分别表示 A1 , A 2 ,L , A 41 ,而点 v1 , v2 ,L , v49 表示 组 B1 , B2 ,L , B49 ,如果组 A i , B j 有公共项,则在相应的点 ui , v j 之间连一条边,于是得二部 图 G ,它恰有 n 条边和 90 个顶点.下面证明 G 是连通图. 如果图 G 的最大连通分支为 G ′ ,其顶点数少于 90 ,设在分支 G ′ 中,有 a 个 A 类顶点

uk1 , uk2 ,L , uka 和 b 个 B 类 顶 点 vs1 , vs2 ,L , vsb , 其 中 a + b < 90 , 则 在 相 应 的 A 类 组 Ak1 , Ak2 ,L , Aka 和 B 类组 Bs 1 , Bs 2 ,L , Bs b 中, A 类组 Aki 中的每个数 xi 都要在某个 B 类组

24

Bs j 中出现;而 B 类组 Bs i 中的每个数 x j 也都要在某个 A 类组 Ar j 中出现, (否则将有边与
分支外的顶点连接, 发生矛盾)因此 a 个 A 类组 Ak1 , Ak2 ,L , Aka 中各数的和应等于 b 个 B 类 , 组 Bs 1 , Bs 2 ,L , Bs b 中 各 数 的 和 , 即 有 49a = 41b , 由 此 得 41 a , 49 b , 所 以

a + b ≥ 41 + 49 = 90 , 矛盾! 因此 G 是连通图. 于是图 G 至少有 90 ? 1 = 89 条边, n ≥ 89 ; 即
另一方面,我们可实际构造一个具有 89 项的数列 x1 , x2 ,L , x89 ,满足本题条件.例如 取 x1 = L = x41 = 41, x42 = L = x75 = 8, x76 = L = x79 = 7, x80 = L = x83 = 1, x84 = x85 = 6,

x86 = x87 = 2 , x88 = 5, x89 = 3 , (该数组有 41 个取值为 41 的项; 34 个取值为 8 的项;另
,于是, 将其余七个 8 拆成七对,其中四对 {7,1} ,两对 {6, 2} ,一对 {5,3} ,又得到 14 个项) 每个 A 类组可由一个 41 ,一个 8 ,或者由一个 41 ,添加一对和为 8 的项组成;这样共得 41 个 A 类组,每组各数的和皆为 49 ;为了获得和为 41 的 49 个 B 类组,可使 x1 , x2 ,L , x41 各成一组,其余的数可以拼成八个 B 类组:{8,8,8,8,8,1} 的组四个,{8,8,8,8, 7, 2} 的组两 个, {8,8,8,8, 6,3} 的组一个, {8,8, 7, 7, 6,5} 的组一个.故 n 的最小值为 89 .

15 、设 S = {1, 2,L ,50} ,求最小的正整数 k ,使得 S 的任一个 k 元子集中,都存在两
个不同的数 a 和 b ,满足: (a + b) ab . 解:设 S 中不同的数 a 和 b ,满足: (a + b) ab ,记 ( a, b) = d ,有 a = a1d , b = b1d , 其中 a1 , b1 为正整数,且 (a1 , b1 ) = 1 ,则 a + b = ( a1 + b1 ) d , ab = a1b1d ,由 (a + b) ab ,得
2

(a1 + b1 ) a1b1 d ,又由 (a1 , b1 ) = 1 得 (a1 + b1 , a1 ) = 1, (a1 + b1 , b1 ) = 1 ,所以 (a1 + b1 , a1b1 ) = 1 .
从而 ( a1 + b1 ) d … ①, a1 + b1 ≤ d , 则 因为 a, b 互异,a, b ∈ S , a + b ≤ 99 , 则 又由 a1 , b1 互异,a1 + b1 ≥ 3 , 且由 (a1 + b1 ) ≤ ( a1 + b1 ) d = a + b ≤ 99 , a1 + b1 < 10 , a1 + b1 ≤ 9 , 则 即
2

于是 3 ≤ a1 + b1 ≤ 9

… ②, a1 + b1 可取 3, 4, 5, 6, 7,8,9 .不妨设 a1 < b1 ,讨论不同情况.

(10 ) 、若 a1 + b1 = 3 ,则 3 | d , (a1 , b1 ) = (1, 2) ,由 b = b1d = 2d ≤ 50 ,则 d ≤ 24 , d 可
取 3, 6,9,L , 24 , 所以 ( a, b) = ( a1d , b1d ) = ( d , 2d ) = (3, 6), (6,12), (9,18), (12, 24), (15,30) ,

(18,36), (21, 42), (24, 48) ;

25

(20 ) 、当 a1 + b1 = 4 ,则 (a1 , b1 ) = (1,3) ,由 3d ≤ 50, 4 d ,则 d ≤ 16 , d 可取 4,8,12,16 ,
(a, b) = (d , 3d ) = (4,12), (8, 24), (12, 36), (16, 48) ; (30 ) 、当 a1 + b1 = 5 ,则 (a1 , b1 ) = (1, 4) 或 (2,3) ,前者 d 可取 5,10 ,后者 d 可取 5,10,15 , (a, b) = (d , 4d ) = (5, 20), (10, 40) ; (a, b) = (2d ,3d ) = (10,15), (20,30), (30, 45) ; (40 ) 、当 a1 + b1 = 6 ,则 (a1 , b1 ) = (1,5) , (a, b) = (6, 30) ; (50 ) 、当 a1 + b1 = 7 ,则 (a1 , b1 ) = (1, 6), (2,5), (3, 4) ,故 (a, b) = (7, 42), (14,35), (21, 28) ; (60 ) 、当 a1 + b1 = 8 ,则 (a1 , b1 ) = (3,5), (1, 7) ,因 7 × 8 > 50 ,去掉这组,(a, b) = (24, 40) ; (7 0 ) 、当 a1 + b1 = 9 ,则 (a1 , b1 ) = (4, 5), (2, 7), (1,8) ,去掉后两组,则 (a, b) = (36, 45) .
以上我们共得到 23 个数对 (a, b) ,其中每个数对都满足: (a + b) ab . 为了找出满足条件的最小的 k ,先求最大的 n ,使得存在 S 的 n 元子集 A ,其中任一对 数 a, b 都不满足条件. 为此,构作 50 阶图 G ,以 S 中的数 1, 2,L ,50 为顶点,如果两数 a, b 属于以上数对, 则令 a, b 相邻,于是图 G 恰有 23 条边(图中的孤立点未标出) . 从中删去一些点,使得图中的边一起被删去,则至少要删去 12 个点,例如将点集

M = {3,5, 7,9,10,12,14,16, 21, 24,30,36} 中 的 点 删
去,这时,图 G 还剩下 50 ? 12 = 38 个点,由这 38 个数 则 即 作成集合 A , A 中不含以上任一个数对. A 中任一 个数对都不满足条件.因此, n = A = 38 . 故所求的最小数 k ≥ 39 .以下证, k = 39 满足条件. 首先从图 G 中取 12 条两两无公共顶点的边( 12 个数 对) (9,18), (36, 45), (5, 20), (15, 30), (10, 40), (8, 24) , :
45

9 18 36 3 6 4 12 8

5 20 30 15 10 40 24 48 16 7 42 14 21 35 28

(16, 48), (4,12), (3, 6), (7, 42), (21, 28), (14, 35) , (其中
每条边恰有一个点在集 M 中) 这 12 条边的顶点共有 24 个, , 相应的 24 个数构成 S 的 24 元 子集 B ; S 中其余的数共有 26 个,它们构成子集 C ; S = B U C , B I C = ? . 今从 S 中任取一个 39 元子集 T ,则 T 至多有 26 个数取自 C 中,也就是至少有 13 个数 取自 B ,其中必有两个数取自上述 12 个数对中的同一对,设为 (a, b) ,则 (a + b) ab .

26

因此,满足条件的最小的 k 值为 39 . 16 、数学奥林匹克集训队中共有 30 名队员,其中每人在队中具有同样多的朋友,已知 在一次考试中,所有人的得分各不相同;若某个队员在他的朋友圈中比多数人的得分都高, 则称该队员为“高手” ,问集训队中至多有几名“高手”? 解:设每名队员有 k 个朋友,而这次考试总共产生了 m 个“高手” ,队中成绩最好的一 ;而其余的每个“高手” , 名队员,在他的 k 个“朋友对”中成绩也是最好的,当然是“高手” 都至少在其 ? ? + 1 ≥ 2

?k ? ? ?

k +1 个朋友对中,成绩占优.所以“高手”们至少一共在 2

k +1 个朋友对成绩占优.由于任一个“朋友对”至多为“高手”作一次贡献, 2 30k 故不会被重复计算,因此上述数目不会超过集训队中“朋友对”的总数, 即 = 15k . (这 2 相当于一个 30 阶图,每点的度数为 k ,其边数为 15k . ) k +1 28k 所以, k + ( m ? 1) × ≤ 15k ,故得 m ≤ + 1 …… ① 2 k +1 另一方面,集训队中比最差的“高手”的成绩还差的队员人数不多于 30 ? m 个(其中 m k +1 k +1 是“高手”总数) ,由于最差的“高手”也至少胜了 人,所以 ≤ 30 ? m , 2 2 即 k ≤ 59 ? 2m …… ② 59 ? 2m 代入①式,并注意①的右边是 k 的增函数,则得到 m ≤ 28 × + 1 ,即 60 ? 2m k + (m ? 1) ×
m 2 ? 59m + 856 ≥ 0 …… ③ , 也就是 m(59 ? m) ≤ 856 ……④,
(注意 25 × 34 = 850, 26 × 33 = 858 ) 则满足④及条件 m ≤ 30 的正整数 m 的最大值是 25 , , 即“高手”数不超过 25 个; 另一方面,我们可说明, 25 个“高手”的情况是可能的, 采用构造法: 用 1, 2,L ,30 表示队员的排名(成绩好的排名在前) , 当 m = 25 时,由②得 k = 9 ,即每人恰有 9 个朋友; 今列出一张 6 × 5 的表,并这样定义朋友关系: 若某对学生为朋友,当且仅当满足以下三情形之一:
1 6 11 16 21 26 2 7 3 8 4 9 5 10 15 20

12 13 14 17 18 19 22 23 27 28

24 25 29 30

( A) 、两人同在第一行; ( B ) 、两人在同一列,但其中一人位于最下面一行; (C ) 、两人分别在相邻的两行,但是不同列;
这样,每人恰有 9 个朋友,并且前 25 名都是“高手” . 五、模型构造法

17 、 (售票问题) 2012 个游客排队购买参观票,每张票价 5 元,其中 1006 人各持有一
张 5 元币,另外 1006 人各持有一张 10 元币,开初时售票机中无零钱可找,试确定,使得不 发生售票困难的排队方法有几种?
27

解:将 2012 换为一般的正整数 2n ;如果某人持有一张 5 元票,则赋值“ +1 ”(即,售 , 票机可以收到一张 5 元票) ;若某人持有一张 10 元票,则赋值“ ?1 ”(即,售票机需要付 , 出一张 5 元票用来找另) ;这样,2n 个人的一个排队状态便对应于 2n 个数(其中含有 n 个 1 和 n 个“ ?1 ” )的一个排列: x1 , x2 , x3 ,L , x2 n ,记 S k = x1 + x2 + L + xk , k = 1, 2,L , 2n ,
Y

O
(0,-1) (0,-2)

(2n,0)

X

(2n,-2)

则 S 2 n = 0 ,一个排队方式不发生售票困难,当且仅当对每个 k ,皆有 S k ≥ 0 . 在直角坐标系中标出点 Ak ( k , S k ) , k = 1, 2,L , 2n ,依次连接 OA1 , A1 A2 ,L , A2 n ?1 A2 n 得到 称长度为 2 , 斜率为 1 的线段为 L+ , 长度为 2 , 斜率为 ?1 一条折线 OA1 A2 L A2 n ?1 A2 n , 的线段为 L? , 因此, 折线 OA2n 由 n 条 L+ 和 n 条 L? 按适当排列顺序首尾连接而组成, n 条 因

L+ 和 n 条 L? 的排列方式有 C2nn 种(从 2n 个位置中任取 n 个位置放置 L+ ,其余位置为 L? 的
放置方法有 C2 n 种) ,所以这种折线一共有 C2 n 条;每个发生售票困难的排法所对应的折线 都与直线 y = ?1 接触;为了计算与直线 y = ?1 接触的折线条数,对每条这种折线,从第一 个接触点开始, 把以后的折线部分以直线 y = ?1 为对称轴翻转, 这样就得到一条由原点 O 到 点 A′(2n, ?2) 的折线,所有这种折线都由 n ? 1 条 L+ 和 n + 1 条 L? 按适当排列顺序首尾连接 而组成,一共有 C2 n 条,因此,不发生售票困难的排队方法有 C2 n ? C2 n =
n
n ?1 n n

n ?1

1 n ?1 C2 n 种. n

18 、对于正整数 n ,证明: ∑ 2 C C
k k =0 k n

n

? n?k ? ? 2 ? ? ? n?k

n = C2 n +1 . (单身汉引理)

证:采用组合模型法,设想某社区共有 n + 1 户人家,其中有 n 户夫妻家庭和一户单身汉 家庭,共计 2n + 1 人,今从中任选 n 人参加一项活动,则共有 C2 n +1 种选择方案.
n

另一方面,该事件也可作如下分类:对任一数 k , 0 ≤ k ≤ n , n 户夫妻家庭中恰有 k 户
28

家庭各派出了一人,其余 n ? k 户夫妻家庭皆为两人同去,显然,当 n ? k 为奇数时,单身 汉必须参加;而当 n ? k 为偶数时,则单身汉肯定不能参加. 从 n 对夫妻中选取 k 对,有 Cn 种方法,再从选出的 k 对中各派出一人,有 2 种派法,
? 2 ? ?n ? k ? ? 剩下 n ? k 人中, 共含有 ? 他们来自剩下的 n ? k 个家庭, 选法种数为 Cn ? k ? , ? 对夫妻, 2 ? ?
? n?k ? ? 2 ? ? ? n? k ? n?k ? ? 2 ? ? ? n?k
k

k

? n?k ?

因此按这种分类,得选法种数

∑2 C C
k k =0 k n

n

,所以,

∑2 C C
k k =0 k n

n

n = C2 n +1 .

19 、一副纸牌共 52 张,其中“方块”“梅花”“红心”“黑桃”每种花色的牌各 13 张, 、 、 、
标号依次是 2,3,L ,10, J , Q, K , A ,其中相同花色、相邻标号的两张牌称为“同花顺牌” , 并且 A 与 2 也算是顺牌(即 A 可以当成 1 使用). 试确定,从这副牌中取出 13 张牌,使每 种标号的牌都出现,并且不含“同花顺牌”的取牌方法数. 解:先一般化为下述问题:设 n ≥ 3, 从 A = ( a1 , a2 ,L , an ) , B = ( b1 , b2 ,L , bn ) ,

C = ( c1 , c2 ,L , cn ) , D = ( d1 , d 2 ,L , d n ) 这四个数列中选取 n 个项,且满足:
(1) 、 1, 2,L , n 每个下标都出现;(2) 、下标相邻的任两项不在同一个数列中 (下标 n 与 1 视
为相邻) ,其选取方法数记为 xn ,今确定 xn 的表达式: 将一个圆盘分成 n 个扇形格,顺次编号为 1, 2,L , n ,并将数列 A, B, C , D 各染一种颜色,对于任一个选项方案,如果下标为 i 的项取自某颜色 数列,则将第 i 号扇形格染上该颜色. 于是 xn 就成为将圆盘的 n 个扇形格染四色,使相邻格不同色的染色方 法数,易知, x1 = 4, x2 = 12, 将○写作 1 因此
n-1

n 1 2 3

xn + xn ?1 = 4 ? 3n ?1 ( n ≥ 3) , … ○ 1
xn ?1 = ?4 ? ( ?3)
n?2 n ?1

( ?1) ( ?1) ( ?1)
n

n

xn ? ( ?1)

n ?1

n ?1

xn ?1 ? ( ?1)
……
2

xn ? 2 = ?4 ? ( ?3)
2

n?2

……
2

3

x3 ? ( ?1) x2 = ?4 ? ( ?3) ; ( ?1) x2 = ?4 ? ( ?3) .
n n n

相加得, ( ?1) xn = ( ?3) + 3 ,于是 xn = 3 + 3 ? ( ?1) ( n ≥ 2) . 因此 x13 = 3 ? 3 . 这就是所求的取牌方法数.
13

29

20 、将周长为 24 的圆周等分成 24 段,从 24 个分点中选取 8 个点,使得其中任何两点 间所夹的弧长都不等于 3 和 8 ;问满足要求的 8 点组的不同取法共有多少种?说明理由.
解:将各分点顺次编号为 1, 2, L , 24 ,再按点间所夹弧长为 3 或 8 的情形,列出一张

1
3 × 8 数表: 9

4

7 15 23

10 18 2

13 21 5

16 24 8

19 3 11

22 6 14

12 17 20

表中同行相邻两点间所夹弧长为 3 (首尾两数属于相邻情况) ,同一列的三点之中任两点间 所夹弧长为 8 . 今要所取的数满足要求, 必须每列恰取一数, 且相邻两列所取的数不同行 (第 一列与第八列视为相邻) .

a1
一般化,考虑 3 × n 的数表

a2 b2 c2

a3 L an b3 L bn ,从中选取 n 个数,使每列恰取一 c3 L cn

b1 c1

数,且相邻两列所取的数不同行(第一列与第 n 列视为相邻) .不同的取法种数记为 xn ,将 第一、二、三行的数 {ak } , {bk } , {ck } 分别染红、黄、蓝三色; 作一个圆盘,并将其分成 n 个扇形小格,顺时针编号为 1, 2, L , n ;今作如下映射,若 表中第 i 列所选出的为某色的数,则将圆盘第 i 号格染上该颜色,易知这种对应是一一的, 于是问题转化为,求用三色分别染圆盘的 n 个扇形格,使邻格不同色的方法数 xn . 易知 x1 = 3 , x2 = x3 = 6 ,当 n ≥ 3 , xn + xn ?1 = 3 ? 2 即
n ?1

( ?1)

n

xn ? ( ?1)

n ?1

xn ?1 = ?3 ? ( ?2 )

n ?1

,令 yn = ( ?1) xn ,有
n n?2

yn ? yn ?1 = ?3 ? ( ?2 )
1

n ?1

, yn ?1 ? yn ? 2 = ?3 ? ( ?2 )
n

,… …, y3 ? y2 = ?3 ? ( ?2 ) ,
2 n

y2 = ?3 ? ( ?2 ) .相加得, yn = ( ?2 ) + 2 , n ≥ 2 .所以 xn = 2 n + 2 ( ?1) , n ≥ 2 .
当 n = 8 ,便得本题答案为 x8 = 2 + 2 = 258 .
8

30


推荐相关:

组合构造答案及讲稿

组合构造答案及讲稿_学科竞赛_高中教育_教育专区。陶平生 【组合十讲】 组合十讲】 组合构造陶平生构造法是解证组合问题的重要方法与基本手段,使用它,常常可以将...


组合数学-组合几何答案与讲稿

组合几何例讲(陶平生) 答案及讲稿 基本内容与方法:组合计数;组合构造;组合结构;映射与对应;分类与染色;归纳与 递推;容斥原理;极端原理;调整法;补集法;算两次;数...


钢-混凝土组合结构(考试终结打印稿-计算题)

钢-混凝土组合结构练习题... 3页 免费钢​-​混​凝​土​组​合​结​构​(​考​试​终​结​打​印​稿​-​计​算...


组合数学基础-答案及讲稿

组合构造答案及讲稿 30页 5财富值 仁慧书院-组合(一、二期)-... 9页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行...


集合与组合讲稿

集合与组合讲稿陶平生( 2013 镇江)基本内容与方法:集合的结构问题, 计数问题, ...1230 种,每种情况都获得满足条件的三个集合 A, B, C ,这样,本题答案为 ...


数论综合讲稿与解答

25页 免费 组合构造答案及讲稿 30页 5财富值 高斯函数 4页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


结构主义讲稿

结构主义讲稿_文学_高等教育_教育专区。结构主义文学...为什么写作?为谁写作?萨特给出的答案分别是:介入、...叙述性符号将功能和行为单位重新组合在以叙述者与...


新型组织结构讲稿

新型组织结构讲稿_管理学_高等教育_教育专区。新型组织结构讲稿由于环境产生了重大...把具有不同优势的组织组合成单一的靠信息技术联 系起来的动态联盟,共同对付市场...


关于演讲的结构

结构的中心是回答和解决这 次演讲“怎样讲”的问题。 二、结构的实质和作用 结构的实质是将来自各方面的分散的演讲稿构成因素(主旨、题材、材料等) 组合成一个...


演讲稿结构的安排

结构的构成, 也有它的形式和内容。 从整体看, 结构是演讲材料的组织构造,是演讲者依据主旨、意图对材料进行组合、编排而演讲稿结构的安排 一、结构的形式和内容...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com