nbhkdz.com冰点文库

2012夏令营组合综合


组合综合

1、对应法 定义 设 f 是从集合 M 到集合 N 的映射。 若对任意 x1 , x 2 ? M , x1 ? x 2 时 当

有 f ( x1 ) ? f ( x 2 ) ,则称 f 为 M 到 N 的单射;若对任意的 y ? N ,存在 x ? M ,使 得 f ( x ) ? y ,则称 f 为 M 到 N 的满射;若

f 既是单射又是满射,则称 f 为 M 到
N 的双射,又称 f 为 M 与 N 之间的一一映射。

定理

对于两个有限集合 M 与,若存在从 M 到 N 的单射,则 | M |?| N | ;若

存在从 M 到 N 的满射,则 | M |?| N | ;若存在从 M 到 N 的双射,则 | M |?| N | 。 当计算有限集合 M 中的元素个数比较困难时,我们设法建立 M 到另一个有 限集合 N 上的双射,如果 N 中的元素个数 | N | 容易算出,于是由 | M |?| N | ,得 出 M 中的元素个数,这种计数方法称为映射方法,或者称为配对法。 例 1-1 给定一个正整数 n 。有多少个满足条件: 0 ? a ? b ? c ? d ? n 的四

元有序整数组 ( a , b , c , d ) 。 解:作映射 f : ( a , b , c , d ) ? ( a ? 1, b ? 2, c ? 3, d ? 4 ) 于 是
/ /

f
/

是 从 集 合 A ? {( a , b , c , d ) | 0 ? a ? b ? c ? d ? n} 到 集 合
/ / / / /

B ? {( a , b , c , d ) | 1 ? a ? b ? c ? d ? n ? 4} 的一个映射,容易验证这个映射

是一一对应,所以 | A |?| B | 。 由 于 || B | 就 是 集 合 {1, 2 , ? , n ? 4} 的 四 元 子 集 的 个 数 , 即 C n ? 4 , 从 而
| A |?
4

C

4 n?4



例 1-2
6

试证:从 {1, 2 , ? , 49 } 中取出 6 个不同的数,使得其中至少有两个相
6

邻,共有 C 49 ? C 44 种取法。 证明:首先,集合 M ? {1, 2 , ? , 49 } 的所有不同 6 元子集的个数为 C 49 ,但是,
1
6

其中 6 个数互不相邻的子集
{a1 , a 2 , ? , a 6 }, a i ? 1 ? a i ?1 , i ? 1, 2 ,3, 4 ,5

(1)

记满足(1)式的所有 6 元子集的集合为 A ,并令
f : ( a 1 , a 2 , ? , a 6 ) ? (b1 , b 2 , ? , b 6 )

(2)

其中
b i ? a i ? i ? 1, i ? 1, 2 ,3, 4 ,5,6 .

(3)

易知 b1 , b 2 , ? , b 6 互不相同,且 1 ? b1 ? b 2 ? ? ? b 6 ? 44 。容易验证,由式(2)和 (3) 定义的映射是由集合 A 到集合 S ? {1, 2 , ? , 44 } 的所有不同 6 元子集的集合 B 的一个一一对应,从而有 | A |?| B |? C 44 。易知命题成立。 例 1-3 设 S ? {1, 2 , ? ,1990 } ,如果 S 的一个 31 元子集中的所有数之和是 5
6

的倍数,则称其为“好子集” 。求 S 的所有好子集的个数。 解:对于 S 的的任一子集 A ,分别用 | A | 和 || A || 表示 A 的元素个数和 A 中所 有元素之和。令
F k ? { A | A ? S , | A |? 31, || A || ? k (mod 5 )} ,

其中 k ? 0 ,1, 2 ,3, 4 . 对于任意 { x1 , x 2 , ? , x 31 } ? A ? F0 ,定义
f k ( A ) ? { x1 ? k , x 2 ? k , ? , x 31 ? k }, k ? 1, 2 ,3, 4 , 其中当 x i ? k ? 1990 时,理解为 x i ? k ? 1990 . 因为 31 k ? k ,1990 ? 0 (mod 5 ), 所以 f k ( A ) ? F k , 易知, 映射 f k 是由 F0

到 F k 的一一对应,故有
| F0 |?| F1 |?| F 2 |?| F3 |?| F 4 |

又因 F0 , F1 , F2 , F3 , F4 互不相交, ? | F k | ? C 1990 , 且 所以 S 的所有好子集的个
31 k ?0

4

数为 | F 0 |?

1

C 5

31 1990



2. 构造法

2

例 2-1 (自编题) 设 M ? {1, 2 , ? , 20 } , A 是 M 的子集且满足条件:当 x ? A 时, 2 x ? A 且 3 x ? A 。则 A 中元素的个数最多是多少? 解: 用 n ( A ) 表示集合 A 所含元素的个数。 由题设容易用枚举法验证, M 1 ? {2 , 4 ,8,16 } 中至少有两个元素不属于 A ,
M 2 ? {5,10 ,15 , 20 } 中至少有两个元素不属于 A , M 3 ? {7 ,14 } 中至少有一个元素不

属于 A 。现考虑 M 4 ? {3,6 ,9 ,12 ,18 } ,容易验证 M 4 中至少有两个元素不属于 A , 分情况讨论: (1) M 4 中至少有三个元素不属于 A ,则 n ( A ) ? 20 ? 2 ? 2 ? 1 ? 3 ? 12 。 (2) M 4 中有两个元素不属于 A ,由题设, {6 ,9 ,12 } ? A , {6 ,9 ,18 } ? A ,
{6 ,12 ,18 } ? A , {9 ,12 ,18 } ? A ,则必有 3 ? A ,且 {3,12 ,18 } ? A ,从而 1 ? A ,则 n ( A ) ? 20 ? 2 ? 2 ? 1 ? 2 ? 1 ? 12 。

综合(1)和(2) ,所以至少有 8 个数不属于 A 。 即 n ( A ) ? 12 。 另一方面,可取 A ? {1, 4,5,6,7 ,9,11,13 ,16 ,17 ,19 , 20 } , A 满足题设条件,此时
n ( A ) ? 12 。

所以, n ( A ) 的最大值就是 12。 例 2-2(2010 清华)请设计一个方案,对 1 维实数轴上的每一个点进行染 色,使得距离为 1, 2 或 5 的两个点都不同色,要求所使用的颜色数目尽可能 少。 解:一种颜色显然不行,故最少要两种颜色。下证染两种颜色可行。 设 M ? {a ? 2 b ? 5 c | a , b , c ? Z } ,对 M 中的元素染色,当 a ? b ? c 为奇数 时 染 红 色 , 当 a ?b?c 为 偶 数 时 染 蓝 色 。 任 取 x?M , 设
X ? {x ? a ? 2b ? 5 c | a , b , c ? Z } , x 染成蓝色, 将 对于 X 中的元素, a ? b ? c 当

为奇数时染红色,当 a?b?c 为偶数时染蓝色。任取 y?M ? X ,设
Y ? {y ? a ? 2b ? 5 c | a , b , c ? Z } ,将 y 染成蓝色,对于 Y 中的元素,当 a ? b ? c

3

为奇数时染红色,当 a ? b ? c 为偶数时染蓝色。 重复上述过程知, 只用两种颜色就可以讲每个点进行染色, 且距离为 1, 2 或 5 的两个点都不同色。 上述解答解释如下: 任取 x ? M ,设 X ? { x ? a ? 2 b ? 5 c | a , b , c ? Z } ,将 x 染蓝色,当 a ? b ? c 为奇数时染红色,当 a ? b ? c 为偶数时染蓝色。 任 取 y ? M ? X ,设 Y ? { y ? a ? 2 b ? 5 c | a , b , c ? Z } ,将 y 染蓝色 ,当
a ? b ? c 为奇数时染红色,当 a ? b ? c 为偶数时染蓝色。

然后又是任取 p ? M ? X ? Y , P ? { p ? a ? 2 b ? 5 c | a , b , c ? Z } , p 染 设 将 蓝色,当 a ? b ? c 为奇数时染红色,当 a ? b ? c 为偶数时染蓝色。 ?? 这样无限重复下去,可以验证这种方案中,距离为 1, 2 , 5 的任意两点 都不同色。 例如, M 中两点 a ? 2 b ? 5 c 与 a 1 ? 2 b1 ? 5 c1 同色, a ? 2 b ? 5 c 比 若 且
a1 ? 2 b1 ? 5 c1 大 2 。

所以, a ? 2 b ? 5 c ? ( a 1 ? 2 b1 ? 5 c1 )= 2 所以, ( a ? a1 ) ? 2 (b ? b1 ? 1) ? 5 ( c ? c1 ) ? 0 容易知道, a ? a 1 , b ? b1 ? 1 , c ? c 1 ,则有 a ? b ? c = ( a1 ? b1 ? c1 ) ? 1 即 a ? b ? c 与 a 1 ? b1 ? c1 相差 1,它们奇偶性不同,这与( a ? b ? c 为奇数时 染红色,当 a ? b ? c 为偶数时染蓝色)相矛盾。 其余类似得矛盾。 例 2-3(2012 北京)设 A 是由 m ? n 个实数组成的 m 行 n 列的数表,满足: 每个数的绝对值不大于 1, 且所有数的和为零,记 S ( m , n ) 为所有这样的数表构成 的集合。 对于 A ? S ( m , n ) ,记 ri ( A ) 为 A 的第 i 行各数之和 (1 ? i ? m ) , c j ( A ) 为 A 的第 j 列各数之和 (1 ? j ? n ) : 记 K ( A ) 为 | r1 ( A ) | , | r2 ( A ) | ,?, | rm ( A ) | , | c1 ( A ) | , | c 2 ( A ) | ,?, | c m ( A ) | 中的最 小值。 (1)对如下数表 A ,求 K ( A ) 的值;
1 0.1 1 -0.3
4

-0.8 -1

(2)设数表 A ? S ( 2,3) 形如
1 a 1
b

c

-1

求 K ( A ) 的最大值; (3)给定正整数 t ,对于所有的 A ? S ( 2, 2t ? 1) ,求 K ( A ) 的最大值。 解: (1)由题意可知 r1 ? A? ? 1.2 , r2 ? A? ? ?1.2 , c1 ? A? ? 1.1 , c2 ? A? ? 0.7 , c3 ? A? ? ?1.8 ∴ k ? A? ? 0.7 (2)先用反证法证明 k ? A?≤1 。 若 k ? A? ? 1 则 | c1 ? A? |?| a ? 1|? a ? 1 ? 1 ,∴ a ? 0 同理可知 b ? 0 ,∴ a ? b ? 0 由题目所有数和为 0 ∴ c ? ?1 ? a ? b ? ?1 与题目条件矛盾 ∴ k ? A?≤1 . 易知当 a ? b ? 0 时, k ? A? ? 1 存在 ∴ k ? A? 的最大值为 1 (3) k ? A? 的最大值为
2t ? 1 t?2 2t ? 1 首先构造满足 k ( A) ? 的 A ? {ai , j }(i ? 1, 2, j ? 1, 2,..., 2t ? 1) : t?2 t ?1 , a1,1 ? a1,2 ? ... ? a1,t ? 1, a1,t ?1 ? a1,t ? 2 ? ... ? a1,2 t ?1 ? ? t?2

.

a2,1 ? a2,2 ? ... ? a2,t ?

t ? t ?1
2

t (t ? 2)

, a2,t ?1 ? a2,t ? 2 ? ... ? a2,2 t ?1 ? ?1 .

经计算知, A 中每个元素的绝对值都小于 1,所有元素之和为 0,且
| r1 ( A) |?| r2 ( A) |? 2t ? 1 t?2


t ? t ?1
2

| c1 ( A) |?| c2 ( A) |? ... ?| ct ( A) |? 1 ?

t (t ? 2)

? 1?
?

t ?1 t?2

?

2t ? 1 t?2



| ct ?1 ( A) |?| ct ? 2 ( A) |? ... ?| c2t ?1 ( A) |? 1 ?

t ?1 t?2

2t ? 1 t?2

.

下面证明
k ( A) ? x ?

2t ? 1

t?2 2t ? 1 t?2

是最大值. 若不然,则存在一个数表 A ? S (2, 2t ? 1) ,使得

.

5

由 k ( A) 的定义知 A 的每一列两个数之和的绝对值都不小于 x , 而两个绝对值 不超过 1 的数的和,其绝对值不超过 2,故 A 的每一列两个数之和的绝对值都在 区间 [ x, 2] 中. 由于 x ? 1 ,故 A 的每一列两个数符号均与列和的符号相同,且绝 对值均不小于 x ? 1 . 设 A 中有 g 列的列和为正,有 h 列的列和为负,由对称性不妨设 g ? h ,则
g ? t , h ? t ? 1 . 另外,由对称性不妨设 A 的第一行行和为正,第二行行和为负.

考虑 A 的第一行,由前面结论知 A 的第一行有不超过 t 个正数和不少于 t ? 1 个负数,每个正数的绝对值不超过 1(即每个正数均不超过 1) ,每个负数的绝对 值不小于 x ? 1 (即每个负数均不超过 1 ? x ). 因此
| r1 ( A) |? r1 ( A) ? t ?1 ? (t ? 1)(1 ? x) ? 2t ? 1 ? (t ? 1) x ? x ? ? 2t ? 1 ? (t ? 2) x ? ? x ,

故 A 的第一行行和的绝对值小于 x ,与假设矛盾. 因此 k ? A? 的最大值为
2t ? 1 t?2

.

3、递推法 例 3-1 将圆分成 n ( n ? 2 ) 个扇形 S 1 , S 2 ,?, S n 。现用 m 种颜色给这些扇

形染色, 每个扇形恰染一种颜色且要求相邻的扇形的颜色互不相同。问有多少种 不同的染色方法? 解 设染色方法数为 a n 。

(1)求初始值。 n ? 2 时,给 S 1 染色有 m 种方法,继而给 S 2 染色有 ( m ? 1) 种 方法,所以, a 2 ? m ( m ? 1) 。 (2)求递推关系。因 S 1 有 m 种染色方法, S 2 有 ( m ? 1) 种染色方法, S 3 有
( m ? 1) 种染色方法, ?,S n ?1 有 ( m ? 1) 种染色方法,S n 仍有 ( m ? 1) 种染色方法 (不

保证 S n 与 S 1 不同色) 。这样共有 m ( m ? 1) n ?1 种染色方法,但这 m ( m ? 1) n ?1 种染色 方法可分为两类: 一类是 S n 与 S 1 不同色,此时的染色方法有 a n 种;另一类是 S n 与 S 1 同色,则 将 S n 与 S 1 合并为一个扇形,并注意到此时 S n ?1 与 S 1 不同色,故这时的的染色方 法有 a n ?1 种,由加法原理得
6

a n + a n ?1 = m ( m ? 1)

n ?1

( n ≥2)
b n ?1 =
m m ?1

(3) a n 。 b n = 求 令

an ( m ? 1)
n

, bn + 由
1

1 m ?1

, b n -1=- 有

1

m ?1

( b n ?1

-1)即 b n -1 为首项为 b 2 -1= ,
?

m ?1

, 公比为-

1 m ?1
1

的等比数列的第 n ? 1 项。 ,

b n -1=(

1 m ?1

) (-

1 m ?1

) n ? 2 = ( ? 1) n

( m ? 1)

n ?1



an ( m ? 1)
n

=1+ ( ? 1) n
n n

1 ( m ? 1)
n ?1



a n = ( m ? 1) ? ( ? 1) ( m ? 1)

例 3-2 (2001 联赛) 在 1 个正六边形的 6 个区域栽种观赏植物,要求同 1 区域中种同一种植物, 相邻的 2 区域中种不同的植物。现有 4 种不同的植物可供 选择,问有多少种栽种方案。 解 在上述命题中,取 n =6, m =4,即得
a 6 = ( 4 ? 1) ? ( ? 1) ( 4 ? 1) =732 种。
6 6

例 3-3( 《中等数学》2008,6)集合 S n ? {1, 2 , ? , n} 的子集中,若不含两个相 邻的自然数,则称为“好子集” 。问 S n 中有多少个“好子集”? 解 设 S n 中有 a n 个“好子集” 。 当 n ? 1 时, S n 中有子集 ? 和 {1} 是“好子集” a 1 ? 2 。类似 a 2 ? 3 。 , 当 n ? 3 时,设 M 为 S n 的“好子集” 。 若 n ? M ,则 M 也为 S n ?1 的“好子集” 若 n ? M ,则 M \ {n} 也为 S n ? 2 的 ; “好子集” 。 所以, ?
? a n ? a n ?1 ? a n ? 2 , ? a1 ? 2, a 2 ? 3 .
a n ?1 ? ( 1? 2 5 ? 1? 2 5 )a n ? ( 1? 2 5 ? 1? 2 5

) a n ?1

变形并递推得

7

a n ?1 ?

1? 2

5

an ?

1? 2

5

(a n ?

1? 2

5

a n ?1 )

??
?( 1? 2 1? 2 5 5 )
n ?1

(a 2 ?

1? 2

5

a1 )

?(

)

n?2

同理, a n ?1 ? 消去 a n ?1 得
an ? 1 5 [( 1? 2

1? 2

5

an ? (

1? 2

5

)

n?2

5

)

n?2

?(

1? 2

5

)

n?2

]

4、算两次
n 2 k n

例 4-1(2006 复旦) 求证: ? (C n ) ? C 2 n
k ?0

证明:法一(母函数法) 因为 (1 ? x ) n ?
n

?C
k ?0
n k k ?0

n

k n

x ,所以
k

(1 ? x )

2n

? ( ? C n x )( ? C n x )
k k k k ?0

一方面,这个乘积中 x n 的系数为 ? C n C n ,
k k ?0

n

n?k

又因为 C n ? C n ,所以 ? C n C n
k

n?k

n

k

n?k

?

k ?0

? (C
k ?0
k

n

2 k n

)

另一方面,从展开式 (1 ? x ) 2 n ?
n 2 k n

?C
k ?0

2n

k 2n

x 知道 x 的系数为 C 2 n ,因而得
n

n

? (C
k ?0

) ?

C

n 2n

法二(构造模型)
8

某班共有 2 n 名学生,现从中选出 n 个学生参加某项活动,显然这样的选法 共有 C 2 n 种;另一方面,将这 2 n 名学生分成 A 、 B 两组,每组 n 个学生,若从 A 组中选出 0 个学生,从 B 组中选出 n 个学生,有 C n ? C n ? (C n ) 2 种选法;从 A 组 中选出 1 个学生,从 B 组中选出 n ? 1 个学生,有 C n ? C n ? (C n ) 2 种选法;??; 从 A 组中选出 n 个学生,从 B 组中选出 0 个学生,有 C n ? C n ? (C n ) 2 种选法。由 加法原理, ? (C n ) ? C 2 n 。
k n k ?0 n 2
n 0 n 1 n ?1 1 0 n 0 n

(2008 南开)求 ? ? C 50 C 50 除以 31 的余数。
i j i?0 j?0

50

50

解:因为 (C 50 ? C 50 ? ? ? C 50 ) ? 2 50
(C 50 ? C 50 ? ? ? C 50 ) (C 50 ? C 50 ? ? ? C 50 ) ? 2
0 1 50 0 1 50 100

0

1

50

,展开即

2

0 ? i ? j ? 50

? C 50 C 50 ?
i j

? (C 50 ) ? 2
k k ?0
50 2 k

50

2 100

引由例 4-1 可知, ? (C 50 ) ? C 100 ,所以
50 k ?0

0 ? i ? j ? 50

?C C
i 50

j 50

?2

99

?

1

C 2

50 100

由于

1

C 2

50 100

?

1 100 ? 99 ? ? ? 93 ? ? ? 62 ? ? ? 51 2 50 ? 49 ? ? ? 31 ? ? ? 1

, 而 31 为素数, 又分子中有
1

93 和 62 为 31 的倍数, 分母中只有 31 为 31 的倍数, 故 即被 31 除余数为零。

C 2

50 100

肯定为 31 的倍数,

因为 2 99 ? 2 4 ? 2 95 ? 2 4 ? ( 2 5 ) 19 ? 2 4 (31 ? 1) 19 ,由二项式定理, ( 31 ? 1) 19 被 31 除余数为 1,所以 2 99 ? 2 4 (31 ? 1) 19 被 31 除余数为 2 4 =16。 所以,

0 ? i ? j ? 50

?C C
i 50

j 50

?2

99

?

1

C 2

50 100

被 31 除余数为 16。

例 4-2 设 S ? { A ? ( a1 , ? a 8 ) | a i ? 0或1, i ? 1, ? ,8} 。 对 于 S 中 两 个 元 素
A ? ( a 1 , ? a 8 ) 和 B ? ( b1 , ? b8 ) ,记
9

d ( A, B ) ?

?|a
i ?1

8

i

? bi |

并称其为 A 和 B 之间的距离。问: S 中最多能取出多少个元素,它们之中任 何两个的距离 ? 5 ? 解 设 S 中最多能取出 m 个元素,它们之中任何两个的距离 ? 5 。可以知道,
m ? 0 (mod 2 ) 时, 5 C m ? 8 ( m ? 1(mod 2 ) 时, 5 C m
2 2

m

2 m ?1 m ?1 ? 8( )( ) 2 2

)

2

解之得, m ? 4 。下面构造 4 个元素满足条件:
( 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ) ; (1,1,1,0 ,0 ,1,1,1) ; (1,1,1,1,1, 0 , 0 , 0 ) ; ( 0 ,0 , 0 ,1,1,1,1,1)

所以, m ? 4 。 例 4-3 已知集合 S n ? { X | X ? ( x1 , x 2 , … , x n ), x1 ? {0,1}, i ? 1, 2, …, n}( n ? 2) 对于
A ? ( a 1 , a 2 , ? , a n ) B ? (b1 , b 2 , ? , b n ) ? S n

, 定义 A 与 B 的差为 A ? B ? (| a
n

1

? b1 |, | a 2 ? b 2 |, ? , | a n ? b n |)

A 与 B 之间的距离为 d ( A , B ) ?

?|a
i ?1

i

? bi | .

(Ⅰ)证明: ? A, B , C ? S n , 有 A ? B ? S n ,且 d ( A ? C , B ? C ) ? d ( A , B ) ; (Ⅱ)证明: ? A, B , C ? S n , d ( A, B ), d ( A, C ), d ( B , C ) 三个数中至少有一个是偶数
_

(Ⅲ)

_ 设 P ? S n , P 中有 m ( m ? 2 ) 个元素,记 P 中所有两元素间距离的平均值为 d ( P ) ,则 d ( P ) ?

mn 2 ( m ? 1)

.

证明: (I)设 A ? ( a1 , a 2 , ..., a n ) , B ? ( b1 , b2 , ..., bn ) , C ? ( c1 , c 2 , ..., c n ) ? S n 因为 a i , bi ? ? 0,1? ,所以 ai ? bi ? ? 0,1? , (i ? 1, 2,..., n ) 从而 A ? B ? (| a1 ? b1 |, | a 2 ? b2 |, ..., | a n ? bn |) ? S n 又 d ( A ? C , B ? C ) ? ? || a i ? c i |? | bi ? c i ||
i ?1 n

由题意知 a i , b i , c i ? ? 0,1? (i ? 1, 2,..., n ) . 当 c i ? 0 时, || ai ? ci | ? | bi ? ci ||?|| a i ? bi | ; 当 ci ? 1 时, || ai ? ci | ? | bi ? ci ||?| (1 ? ai ) ? (1 ? bi ) |?| a i ? bi |

10

所以 d ( A ? C , B ? C ) ? ? | a i ? bi | ? d ( A , B )
i ?1

n

(II)设 A ? ( a1 , a 2 , ..., a n ) , B ? ( b1 , b2 , ..., bn ) , C ? ( c1 , c 2 , ..., c n ) ? S n
d ( A, B ) ? k , d ( A, C ) ? l , d ( B , C ) ? h .

记 O ? (0, 0,..., 0) ? S n ,由(I)可知
d ( A, B ) ? d ( A ? A, B ? A ) ? d (O , B ? A ) ? k d ( A, C ) ? d ( A ? A, C ? A ) ? d (O , C ? A ) ? l d ( B , C ) ? d ( B ? A, C ? A ) ? h

所以 | bi ? ai | ( i ? 1, 2, ..., n ) 中 1 个数为 k , | ci ? ai | (i ? 1, 2, ..., n ) 的 1 个数为 l 。 设 t 是使 | bi ? a i |?| ci ? ai |? 1 成立的 i 的个数,则 h ? l ? k ? 2 t 由此可知, k , l , h 三个数不可能都是奇数, 即 d ( A, B ) , d ( A, C ) , d ( B , C ) 三个数中至少有一个是偶数。 (III) d ( P ) ?
1 Cm
2

A , B? P

?

d ( A , B ) ,其中

A , B? P

?

d ( A , B ) 表示 P 中所有两个元素间距离

的总和,设 P 种所有元素的第 i 个位置的数字中共有 t i 个 1, m ? ti 个 0, 则

A , B? P

?

d ( A , B ) = ? ti ( m ? ti )
i ?1

n

由于 t i ( m ? t i ) ?

m

2

4

( i ? 1, 2, ..., n )

所以

A , B? P

?

d ( A, B ) ?

nm 4

2

从而 d ( P ) ?

1 C

2 m A , B? P

?

d ( A, B ) ?

nm 4C
2 m

2

?

mn 2( m ? 1)

例 4-4(1998 IMO) 在某次竞赛中,共有 a 个参赛选手与 b 个裁判,其 中 b ≥3 且为奇数。每个裁判对每个选手的评分只有“通过”或“不及格”两个 等级。设 k 是满足以下条件的整数:任何两个裁判至多可对 k 个选手有完全相同

11

的评分。证明:

k a

?

b ?1 2b



证明 首先, 如果两个裁判对某个选手有相同的评判, 我们就称其为一个 “同 意” 。由已知,任何两个裁判至多可对 k 个选手有完全相同的评判,即任何两个 裁判最多产生 k 个“同意” 。
?

“同意”的总数 ? kC b2 。

另一方面,对任意一个选手,设有 A 个裁判判他通过,而 B 个裁判判他不及 格,其中 A ? B = b ,则对这个选手,有关他的“同意”的个数为
C +C =
2 A 2 B

A ? B ? ( A ? B)
2 2

2

=

( A ? B ) ? ( A ? B ) ? 2( A ? B )
2 2

4

=

b ? ( A ? B ) ? 2b
2 2

4

由于 b ? 3 且为奇数,故 A ? B 也应为奇数。从而
C +C
2 A 2 B

?

b ? 1 ? 2b
2

4

=(

b ?1 2

)

2

? 所有“同意”的个数≥ a ( ?a (

b ?1 2

)

2

b ?1 2

) ? kC b ?
2

2

k a

?

b ?1 2b



5、容斥原理 容斥原理Ⅰ 设 Ai ( i ? 1 , 2 , ? ? ? , n ) 是有限集,那么
i ?1

? Ai ?

n

?
i ?1

n

Ai ?

1? i ? j ? n

?

Ai ? A j ?

1? i ? j ? k ? n

?

Ai ? A j ? Ak ? ? ? ? ? ( ? 1)

n ?1

n i ?1

? Ai

?

容斥原理Ⅱ 设 I 为全集, Ai ( i ? 1 , 2 ? ? ? , n ) 是有限集,那么
? Ai ? ? Ai ? I ? ? Ai ? I ? ? Ai ?
i ?1 i ?1 n n n

n

i ?1

i ?1

1? i ? j ? n

?

Ai ? A j

?

1? i ? j ? k ? n

?

Ai ? A j ? Ak ? ? ? ? ? ( ? 1) ? Ai
n i ?1

n

?

例 5-1 (错位排列)若{1,2,?, n }的一个排列{ i1 , i 2 ,?, i n }满足 i1 ≠
12

1,i 2 ≠2,?, i n ≠ n ,则称{ i1 ,i 2 ,?, i n }为{1,2,?, n }的一个错位排列。 试求{1,2,?, n }的所有错位排列的个数 D n 。 解 将{1,2,?, n }的所有排列集合记为 S ,则显然 S = n! 。设 A j ={( i1 ,

i 2 ,?, i n )|( i1 , i 2 , i n ) ? S 且 i j ? j }( j =1,2,?, n ) ,于是
D n =| A1 ? A 2 ? ? ? A n |
_ _
_

| A j |= ( n ? 1)! (1≤ j ≤ n ) Ai ? A j |= ( n ? 2 )! (1≤ i < j ≤ n ) ,?, ,| | Ai ? A i ? ? ? A i |= ( n ? r )! (1≤ i1 < i 2 <?< i r ≤ n ) ,?,
1 2 r

_

| A1 ? A 2 ? ? ? A n |= 0! =1。 故由容斥原理得,
D n = S - ? Ai +
i ?1 n

1? i ? j ? n

?

( Ai ? A j -?+ ? 1) A1 ? A 2 ? ? ? A n
n

1 n ( = n! - C n ( n ? 1)! + C n2 ( n ? 2 )! - C n3 ( n ? 3)! +?+ ? 1)C nn ? 0!

= n! ( 1 ?

1 1!

?

1 2!

?

1 3!

???

( ? 1) n!

n

) 。

例 5-2 在不含数字 0,9 的所有 n 位自然数中,同时包含数字 1,2,3,4,5 的 数有多少个?这里数字可重复, n ? 5 。
A 解 设 I 为 1, 3, 6,7,8 组成的 n 位数集, i 为 I 中不含数字 i ( i ? 1, 2 , ? ,8 ) 2, 4,5,

的 n 位数集。
5

I 中不全含数字 1,2,3,4,5 的 n 位数集为 ? A i
i ?1

? A =?
5 i i ?1

5

5

Ai 2 n

i ?1

1? i ? j ? 5
3 n

?

Ai A j +
4

1? i ? j ? k ? 5
n n

?

Ai A j Ak

?

1? i ? j ? k ? l ? 5

?

Ai A j A k Al +

?A
i ?1

i

? 5?7 ?C5?6 ? C5?5 ?C5? 4 ? 3
n

故 I 中同时包含数字 1,2,3,4,5 的 n 位数的个数为
8 ? 5? 7 ?C5? 6 ? C5?5 ?C5? 4 ? 3
n n n n n 2 3 4 n

13

变例 由数字 1,2,3 组成 n 位自然数,且在这个 n 位数中,1,2,3 的每一 个至少出现一次,问这样的 n 位数有多少个? 解 设 I 是由 1, 3 组成的 n 位数的集合,Ai 为 I 中不含数字 i (i ? 1, 2 ,3) 的 n 2, 位数集。则
| I |? 3 ; | A1 |?| A 2 |?| A3 |? 2 ; | A 1 A 2 |?| A 2 A3 |?| A3 A1 |? 1 ; | A 1 A 2 A3 |? 0 ;
n
n

因此
| A1 ? A2 ? A3 |

= | I | - | A1 | ? | A2 | ? | A3 | + | A 1 A2 | ? | A2 A3 | ? | A3 A1 | - | A 1 A2 A3 | = 3n ? 3 ? 2 n ? 3 ? 1 ? 0 即符合题意的 n 位数的个数为 3 n ? 3 ? 2 n ? 3 . 6、反证法 例 6-1 (2009 清华) 用有限条抛物线以及它们的内部能否覆盖整个平面? (含焦点的区域称为抛物线内部) 解:不能。采用反证法:假设存在 n 条抛物线,这 n 条抛物线以及它们的内 部能覆盖整个平面。现在我们任取一条与 n 条抛物线的对称轴均不平行的直线, 那么这 n 条抛物线中的任意一条,与该直线或者没有交点,或者相切,或者有两 个不同的交点。 换句话说就是每条抛物线只能盖住该直线有限的部分。所以有限 条抛物线以及它们的内部不能覆盖整个平面。 例 6-2(1982 西德)如果一个集合不包含满足 x ? y ? z 的三个数 x 、 y 、 z , 则称之为单纯的。设 M ? {1, 2 , ? , 2 n ? 1} , A 是 M 的单纯子集,求 | A | 的最大值。 解 令 A ? {1,3, ,5 ? , 2 n ? 1} ,则 A 是单纯的,此时 | A |? n ? 1 。下面,证明:

对任何单纯子集 A , | A |? n ? 1 。 有 用反证法。 假设 | A |? n ? 2 , A 中至少有 n ? 2 即 个元素, 设为:a1 ? a 2 ? ? ? a n ? 2 。 A 中有 p 个奇数 a1 ? a 2 ? ? ? a p 和 n ? 2 ? p 设 个偶数 b1 ? b 2 ? ? ? b n ? 2 ? p ,注意到 M 中共有 n ? 1 个奇数, n 个偶数,故 p ? 2 。 考 察 a 2 ? a1 ? a 3 ? a1 ? ? ? a p ? a1 , 它 们 都 是 正 偶 数 , 连 同 前 面 假 设 的
b1 ? b 2 ? ? ? b n ? 2 ? p ,共有 ( p ? 1) ? ( n ? 2 ? p ) ? n ? 1 ? n 个正偶数。由抽屉原理,

14

必有两个元素相等,且只能是某个 b i 与某个 a j ? a 1 相等,于是 a j ? a 1 ? b i ,与 A 是单纯的矛盾。 7、不等式法 例 7-1 ( 1982 瑞 典 ) 在 坐 标 平 面 上 给 定 集 合

M ? {( x , y ) | x , y ? N , x ? 12 , y ? 12 } ,并将 M 中的每点都涂上红、白、蓝三色之

一,试证存在一个矩形,它的边平行于坐标轴,4 个顶点都在 M 中且颜色相同。 证明 显然,集合 M 中共有 144 个点且构成 12 行和 12 列的正方形点阵。 由抽屉原理知,必有一种颜色的点至少有 48 个,不妨设红点有 48 个。设第 i 列 中共有 a i 个红点, i ? 1, 2 , ? ,12 ,于是 a1 ? a 2 ? ? ? a12 ? 48 。 将同一列中的两个红点称为一个点对并考察点对的数目。第 i 列上的点对有
1 2 a i ( a i ? 1) ,从而点对总数为 m? ? 1 2 1 2 1 24 ( a 1 ? a 2 ? ? ? a 12 ) ?
2 2 2 2 2 2

1 2

( a 1 ? a 2 ? ? ? a 12 )

( a 1 ? a 2 ? ? ? a 12 ) ? 24



由柯西不等式有
m? ( a 1 ? a 2 ? ? ? a 12 ) ? 24
2

=96-24=72 ② 显然。每个红点对都对应一个由两点的纵坐标组成的“行对” 。于是由②知,至 少有 72 个“行对” 。另一方面,由于点阵共 12 行,共可组成 C 12 ? 66 个不同的 “行对” ,由抽屉原理,必有两个不同列的红点对对应于同一个“行对” 。易见, 以这两队中的 4 个红点为顶点的矩形即为所求。 例 7-2(2003 西部) 1650 个学生排成 22 行、75 列。已知其中任意两列 处于同一行的两个人中,性别相同的学生不超过 11 对。证明:男生的个数不超 过 928。 解: 设第 i 行的男生数为 a i ,则女生数为 75- a i 。依题意,可得
2

? (C
i ?1

22

2 ai

? C 75 ? a i ) ≤ 11 ? C 75
2

2

这是因为任意给定的两列处于同一行的两个人中,性别相同的学生不超过
2 11 对,故所有性别相同的两人对的个数不超过 11 ? C 75 。

15

?

? (a
i ?1

22

2 i

? 75 a i ) ≤-30525
2 i

?

? (2a
i ?1

22

? 75 ) ≤1650

利用柯西不等式,可得

? ? (2ai
i ?1

22

? 75 )

? ≤22 ? ( 2 a i
2

22

2

? 75 ) ≤36300

i ?1

?

? (2a
i ?1

22

i

? 75 ) <191

?

?a
i ?1

22

i



191 ? 1650 2

<921

8、抽屉原理 例 8-1 (2008 科大)一个平面由红点、蓝点组成,且既有红点又有蓝点。 对于给定任意长 a ( a ? 0 ) ,证明: (1)平面上存在两个同色点,距离为 a ; (2)平面上存在两个异色点,距离为 a 。 证明 (1)取一个边长为 a 的正三角形,由抽屉原理,必有两点同色,则 这两点即为所求。 (2)由于平面内既有红点又有蓝点,所以可以任取一个红点 A 和一个蓝点 B ,又由于平面上所有点均染了两色之一,所以这两点 A 、 B 可以由若干条长度 为 a 的线段相连,这一定可以做到。由于 A 、 B 异色,则必存在相邻的两点 C 、 D ,使 C 、 D 异色且 CD ? a ,则 C 、 D 两点即为所求。 例 8-2 (2008 东南) 已知集合 S ? {1, 2 ,3, ? ,3 n} ,n 是正整数,T 是 S 的子集, 满足:对任意的 x , y , z ? T (其中 x , y , z 可以相同)都有 x ? y ? z ? T ,求所有这 种集合 T 的元素个数的最大值。 解:若取 T 0 ? {n ? 1, n ? 2 , ? ,3 n} ,此时 | T 0 |? 2 n ,且 T 0 中任意三个数之和大 于 3 n ,即不在 T 0 中,故 max | T |? 2 n 。 另一方面,作三元子集列
A 0 ? { n , 2 n , 3 n} Ak ? {k , 2 n ? k , 2 n ? k }, k ? 1, 2 , ? , n ? 1 ,
16

则 S ? ? A k ,对于 S 的任意一个 2 n ? 1 元子集 T / ,必包含有某个 Ak 。
k ?0

n ?1

若 A 0 ? T / ,则其中有元素 3 n ? n ? n ? n ; 若某个 A, k ? T / , k ? {1, 2 , ? , n ? 1} ,则其中有元素
2n ? k ? k ? k ? (2n ? k )

于是 所以

max | T |? 2 n ? 1 max | T |? 2 n

例 8-3 (自编题) 已知集合 S ? {1, 2 ,3, ? ,100 } ,T 是 S 的子集,满足性质:对 于 T 中的任意一个元素 x , x 至多与 T 中其余的 2 个元素不互素,求所有这种集 合 T 的元素个数的最大值。 解:A ? {2,3,5,7 ,11,13 ,17 ,19 , 23 , 29 ,31,37 , 41, 43 , 47 ,53 ,59 ,61,67 ,71,73 ,79 ,83 ,89 ,97 } , 即 A 表示不超过 100 的所有素数。令
T 0 ? A ? {2 ? 43 , 2 ? 47 ,3 ? 29 ,3 ? 31,5 ? 17 ,5 ? 19 ,7 ? 11,7 ? 13}

容易验证, T 0 满足性质,且 | T 0 |? 33 。所以, max | T |? 33 。 另一方面,假设 max | T |? 34 。不妨设 T1 满足性质,且 | T1 |? 34 ,考虑 T1 中所 有元素的最小素因子。显然 S 中其最小素因子大于 10 的元素本身就是素数,而 100 以内的超过 10 的所有素数有 21 个, 又容易知道 1 ? T1 , 所以 T1 中其最小素因 子是 2 或 3 或 5 或 7 的数至少有 13 个。根据抽屉原理, T1 中其最小素因子相同 的数至少有 4 个, 这与 T1 中任意一个元素至多与 T1 中其余的 2 个元素不互素矛盾。 于是 所以
max | T |? 34 max | T |? 33 。

9、调整法 调整法是先证明所求的极值存在,然后由问题的直观性,猜想出极值点。最 后从反面证明函数在其他点不能达到极值: 假设函数在另外的点 ( x1 , x 2 , ? , x n ) 处 达到极值,经过适当调整(常常是将小的分量变大,大的分量变小) ,发现函数
17

在点 ( x1 , x 2 , ? , x n ) 处的值更大或更小,从而断定它不是极值点。

/

/

/

例 9-1 (1985 美国) 在不减正整数序列 a1 , a 2 , ? , a m , ? 中, 对任何正整数 m , 定义 b m ? min{ n | a n ? m} 。 已知 a 19 ? 85 , S ? a1 ? a 2 ? ? ? a19 ? b1 ? b 2 ? ? ? b85 求 的最大值。 解:首先,最大的数一定存在。由条件有 a1 ? a 2 ? ? ? a19 ? 85 。猜想:极 值 点 是 各 个 a i 尽 可 能 大 且 各 个 a i 相 等 , 各 个 bi 相 等 。 实 际 上 , 若 有
a i ? a i ?1 (1 ? i ? 18 ) , 则令 a i ? a i ? 1 。 对任何 j ? i , a 令
/

/ j

? aj, 对应的 b j 记为 b

/ j



那 么 , 因 为 a i ?1 ? a i , 所 以 a i ?1 ? a i ? 1 。 但 a i ? a i ? 1 , 故 b a ?1 ? i ? 1 ,
i

b

/

a i ?1

? i ? b a i ?1 ? 1 , b

/ j

? b j (当 j ? a i ? 1 时) 。由此可知,调整使得 b a i ?1 减少 1,

其余的 b i 不变, S 的值不减。综上所述, S ? 19 ? 85 ? 1 ? 85 ? 1700 ,等号在
a i ? 85 , b i ? 1(1 ? i ? 19 ,1 ? j ? 85 ) 时成立。

10、奇偶分析 例 10-1 (IMO—50 预选题)有排成一列的 2009 张卡片,每张卡片一面为 金色,另一面为黑色,开始时,所有卡片的金色面朝上。两人交替操作,规则如 下:选择相邻的 50 张卡片,且最左边的一张卡片的金色面朝上,其翻转张 50 张卡片。 规定最后一个按上述规则操作的玩家获胜。 (1) 问: 操作是否一定结束? (2)先操作的玩家是否有获胜策略? 解: (1)记黑色面朝上的卡片为 0,金色面朝上的卡片为 1。 对 2009 张卡片的每一种摆放, 从左到右读与 2009 个数码在二进制表示下的 非负整数(首位数码可以是 0)构成一一对应。而每次操作该数变小,因此,操 作一定结束。 (2)只需证明:先操作的玩家没有获胜策略。 事实上,将卡片从右到左进行编号。考虑编号为 50 i (i ? 1, 2 , ? , 40 ) 的集合 S 。 设 S 中 n 次操作后,金色面朝上的卡片的数目是 U n 。 显然, U 0 ? 40 ,且 | U n ? U n ?1 |? 1 。 于是奇数次操作后,S 中金色面朝上的卡片的数目是奇数,后操作的玩家可 以从 S 中选一张金色面朝上的卡片, 对这张卡片及其右边的 49 张卡片进行操作。 因此,后操作的玩家总能获胜。
18

11、极端原理 例 11-1(2010 江苏)将凸 n 边形 A1 A2 ? An 的边与对角线染上红、蓝两色之 一,使得没有三边均为蓝色的三角形. 对 k=1, 2,?,n,记 bk 是由顶点 Ak 引 出的蓝色边的条数,求证:
b1 ? b2 ? ? ? bn ? n
2

.

2

证明:不妨设 b ? max{b1 , b2 , ? , bn } ,并且由点 A 向 A1 , A2 , ? , Ab 引出 b 条蓝色 边,则 A1 , A2 , ? , Ab 之间无蓝色边, A1 , A2 , ? , Ab 以外的 n ? b 个点,每点至 多引出 b 条蓝色边,因此
n ? (n ? b) ? b ? 蓝色边总数 ? ( n ? b )b ? ? . ? ? 2 4 ? ?
2 2

故 b1 ? b2 ? ? ? bn ? 2 ?

n

2

4

?

n

2

.

命题得证.

2

19

思考题: 1. 集合 A 是一个整数集合,它的最小元素是 1,最大元素是 100。除 1 外, 它的每个元素都等于 A 中两个元素(可能是相等的两个数)之和。在满足这些条 件的一切集合中,求具有最少元素的集合。 (1980 年全俄数学奥林匹克) 2. 定义一个“希望集合” (Hope Set)简称 HS 如下: HS 为一个非空集合, 它满足条件“若 x ? HS ,则 2 x ? HS ” 。试问:在集合 {1, 2 , ? ,30 } 中,一共有多少 个“希望子集合”? ( 《中等数学》2007,6) 3. 在 2005 张卡片的背面分别写有 2005 个不同的实数,每次提问可以指着 其中任意三张卡片询问写在它们之上的三个数组成的数集,试问:最少可以通过 多少次提问,就一定能理解清楚写在每张卡片背面的都是什么数? (2005 年俄罗斯数学奥林匹克) 4. 在考试中,有 4 个选择题,每题有 3 个可能的答案。一群学生参加考试, 结果是对于其中任意 3 个人,都有一个问题,他们的答案各不相同。问至多有多 少个学生? (第 29 届 IMO 预选题) 5. 有一根由 60 个环组成的锁链,每环重 1 克。最少砍断几个环,就可以利 用断成的一段段锁链,凑出 1 克,2 克,?,59 克,60 克的重量来(被砍断的 环仍然为 1 克)? (1951 年莫斯科数学奥林匹克) 6. 设 M ? {1, 2, ? ,1995 } , A 是 M 的子集且满足条件:当 x ? A 时, 15 x ? A 。 则 A 中元素的个数最多是多少? (1995 年全国高中数学联赛) 7. 在 2 ? n 方格表的每个方格中都写有一个正数,使得每一列中的两个数的 和都等于 1。 证明:可以自每一列中删去一个数,使得每一行中剩下的数的和不 超过
n ?1 4



(2005 年俄罗斯数学奥林匹克)

8. 20 个足球队参加全国冠军赛,问至少进行多少场比赛,才能使得任何 3 个队中总有两个队彼此赛过? (1969 年苏联数学奥林匹克) 9. 设 { B1 , B 2 , ? , B k } 是 A 的一族非空子集,当 i ? j 时, B i ? B j 至多有两个 元素,求 k 的最大值。 (1985 年 IMO 预选题)

10. 设 M ? { x1 , x 2 , ? , x n } 是自然数 1, 2 , ? , n 的一个排列。 f (M ) 是 M 中每两 个 相 邻 元 素 的 差 的 绝 对 值 的 最 小 值 。 求 f (M ) 的 最 大 值 。 (1989 年 IMO 预选题) 11. 试证可以用 4 种不同颜色为数集 M ? {1, 2, ? ,1987 } 中的每个数都涂上一 种颜色,使得 M 中任何一个成等差数列的 10 元子集中的 10 个数的涂色都不全 相同。 (1987 年 IMO 预选题) 12. 设有一个正 2 n + 1 ( n > 1)边形。两人按如下法则做游戏:轮流在该 正多边形内画对角线,每人每次画一条新的(以前没有画过的)对角线 ,而它恰好 与已画出的偶数条对角线相交(交点在正多边形内) ,凡无法按照要求画出对角 线者即为负方。问:谁有取胜策略 ? (2007 年俄罗斯数学奥林匹克)
20

13. 坐标平面上的每个整点都被染为 3 种颜色之一,且 3 种颜色的点都 有。证明:可找到 1 个直角三角形,它的 3 个顶点是 3 种不同颜色的点。 (2004 年俄罗斯数学奥林匹克) 14. 已知 n ( n ? 2 )条直线把平面分成若干个区域,其中的一些区域被涂 上颜色,使得任何两个涂色区域都没有公共边,求证涂色区域的数目不超过
1 3 (n ? n) 。
2

(1985 年全苏数学奥林匹克)

15. 从 n 个元素 a1 , a 2 , ? , a n 中取两个组成一对,共组成 n 对 p 1 , p 2 , ? , p n 。 如果 {a i , a j } 是其中一对,则两对 p i 和 p j 中恰好有 1 个公共元素,求证每个元素 恰好属于其中两对。 (1985 年 IMO 预选题)

16. 将 ( n ? 1) ? ( n ? 1) 的方格表的 n 2 个结点中的每个涂上红、蓝两色之一, 求使表中每个方格都恰有两个红色顶点的不同涂色方案的种数。 IMO 预选题) (1996 年
xy 25

17. 设 A 是正整数集合 N ? 的子集,对任何 x , y ? A , x ? y ,有 | x ? y |? 求 | A | 的最大值。 (1985 年 IMO 预选题)



18. 有 1999 个集合,每个集合有 45 个元素,任意两个集合的并集有 89 个 元素,问此 1999 个集合的并集有多少个元素。 (1993 年湖北竞赛题) 19.围绕一个圆桌坐着来自 50 个国家的 100 名代表,每个国家 2 名代表。证 明:可将他们分成两组,使得每一组都是由来自 50 个国家的 50 名代表组成,并 且每一个人都至多与自己的一个邻座的人同组。 (2005 年俄罗斯数学奥林匹克) 20.在凸 100 边形的每个顶点上都写有两个不同的数。证明:可以从每个顶 点上划去一个数 ,使得任意两个相邻的顶点上剩下的数都互不相同。 (2007 年俄罗斯数学奥林匹克) 21. 设凸 n 边形的任意 3 条对角线不相交于形内一点,求它的对角线在形内 的交点总数。 22. 已知一个保险柜由 11 个成员的委员会负责管理,保险柜上加了若干把 锁, 这些锁的钥匙分配给各个委员保管使用。为了使任何 6 个委员同时到场就能 打开保险柜, 而任何 5 个委员同时到场都不能打开保险柜,最少应给保险柜加多 少把锁? (1971 年波兰数学奥林匹克) 23. 如图,在 7× 的长方形棋盘的每个小方格的中心点各放一个棋子。如果 8 两个棋子所在的小方格共边或共顶点,那么称这两个棋子相连。现从这 56 个棋 子中取出一些,使得棋盘上剩下的棋子,没有五个在一条直线(横、竖、斜方向) 上依次相连。问最少取出多少个棋子才可能满足要求?并说明理由。 (2007 ,全国高中数学联赛) 24.将周长为 24 的圆周等分为 24 段,从 24 个分点中选取 8 个点,使得其中 任何两点所夹的弧长都不等于 3 和 8。问满足要求的 8 点组的不同取法有多少 种? (2001 年 CMO 题) 25. 一种密码锁的密码设置是在正 n 边形 A1 A2 ? An 的每个顶点处赋值 0 和 1

21

两个数中的一个,同时在每个顶点处涂染红、蓝两种颜色之一,使得任意相邻的 两个顶点的数字或颜色中至少有一个相同。问:该种密码锁共有多少种不同的密 码设置? (2010 年全国高中联赛题) 26.将与 105 互素的正整数从小到大排成数列,求出这个数列的第 1000 项。 (1994 年全国高中联赛题) 27. 设 f (n ) 表示平面上任何三点不共线的 n ( n ? 4 )个点所组成的三角形
? 中,非锐角三角形个数的极小值。 ? 1 ? ? 2 ? ? 3 ? 0 , 4 ? 设
f (4)

C

3 4

? , 5 ?

f (5)

C

3 5

, ?,

?n ?

f (n)

C

3 n

,?,则数列{ ? n }是递增数列。 (自编题)
1 2

征解题:是否 lim ? n ?
n? ?



28.有多少种方法能将从 1 到 n 的 n 个整数排成下面的排列:除了左边的 第一个整数外,每一个数都与它左方(不必相邻)的某一个数相差 1? (1965 年第 26 届美国普特南数学竞赛题) 29.不定方程 x1 ? x 2 ? ? ? x m ? n ( m ? 2, n ? 2, m ? n )的正整数解有 组。 推论:不定方程 x1 ? x 2 ? ? ? x m ? n ( m ? 2 , n ? N )非负整数解有 C n ? m ?1 组。 30. 8 个女孩,25 个男孩围成一个圆周,每两个女孩之间至少站有 2 个男 孩,共有 种不同的排列方法。 (只把圆旋转一下就重合的排法认为是相同 的) (1990 年全国高中联赛题) 31.如果从数 1 ,2 , ?,14 中,按由小到大的顺序取出 a 1 、 a 2 、 a 3 ,使得同时 满足 a 2 ? a 1 ? 3 与 a 3 ? a 2 ? 3 .那么,所有符合要求的不同取法有多少种。 (1989 ,全国高中数学联赛)
m ?1

C

m ?1 n ?1

22

思考题解答: 1.集合 A 是一个整数集合,它的最小元素是 1,最大元素是 100。除 1 外, 它的每个元素都等于 A 中两个元素(可能是相等的两个数)之和。在满足这些条 件的一切集合中,求具有最少元素的集合。 (1980 年全俄数学奥林匹克) 解:答案: {1, 2 ,3,5,10 , 20 , 25 ,50 ,100 } 。 设 k 1 ? 1 ? k 2 ? k 3 ? ? ? k n ? 100 , 因为 2 k i ? k i ?1 , 那么对于任意 i 有 k i ? 2 i ?1 , 特别, 100 ? 2 n ?1 ,故 n ? 8 。假设 n ? 8 得出, k 7 ? 50 ,而 2 k 5 ? 25 ,矛盾。 2. 定义一个“希望集合” (Hope Set)简称 HS 如下: HS 为一个非空集合, 它满足条件“若 x ? HS ,则 2 x ? HS ” 。试问:在集合 {1, 2 , ? ,30 } 中,一共有多少 个“希望子集合”? ( 《中等数学》2007,6-26) 解: 下面用“ a ? 2 a ”表示 a 与 2 a 的两倍关系。注意到 ① 15 ? 30 , ② 13 ? 26 , ③ 11 ? 22 , ④ 9 ? 18 , ⑤ 7 ? 14 , 14 ? 28 ⑥ 5 ? 10 , 10 ? 20 ⑦ 3 ? 6 , 6 ? 12 , 12 ? 24 , ⑧ 1 ? 2 , 2 ? 4 , 4 ? 8 , 8 ? 16 。 显然,17,19,21,23,25,27,29 是否在 HS 中不影响 HS 成为希望子集(因为这些数 不能被 2 整除,且每个数的两倍均大于 30),所以,这 7 个数的归属方案有 2 7 种。 在①中,15 与 30 不能同时取,故有 2 2 ? 1 ? 3 种方案。 同理,在②、③、④中,也各有 3 种方案。 下面采用递推算法。 在⑤中,若取 7,则不能取 14,此时,28 可取亦可不取,有两种方案;若不取 7,则 由①知,关于 14 和 28,共有 3 种方案(14 和 28 的情况与①相同)。 因此,在⑤中共有 2+3=5 种方案。 同理,在⑥中共有 5 种方案。 在⑦中,若取 3,则不能取 6,由①知关于 12 和 24,有 3 种方案;若不取 3,则由 ⑤知,关于 6,12,24,有 5 种方案。因此,在⑦中共有 3+5=8 种方案。 在⑧中,若取 1,则不能取 2,由⑤知关于 4,8,16,有 5 种方案;若不取 1,则由⑦ 知关于 2,4,8,16,有 8 种方案。因此,在⑧中共有 5+8=13 种方案。 再考虑到除去空集 (即 1,2,?,30 都不取),因此,所求的{1,2,,?,30}的希望子 集的个数为 2 7 ? 3 4 ? 5 2 ? 8 ? 13 ? 1 ? 26956799 。

23

3.在 2005 张卡片的背面分别写有 2005 个不同的实数, 每次提问可以指着其 中任意三张卡片询问写在它们之上的三个数组成的数集,试问:最少可以通过多 少次提问,就一定能理解清楚写在每张卡片背面的都是什么数? (2005 年俄罗斯数学奥林匹克) 解:1003 次。 假设已经提出了 N 个问题。显然,每一张卡片都至少应当参与其中一个问 题,否则无法弄清楚该张卡片上的数。 假设其中有 k 张卡片恰好各参与其中一个问题。那么,在同一个问题中不可 能遇到两张此类卡片。事实上,如果有两张此类卡片参与了同一个问题,那么, 交换这两张卡片上所写的数,所得到的回答不会有丝毫改变,从而,无法确定它 们上面所写到底是哪个数。因此, k ? N 。其余的各张卡片至少参与两个问题。 如果累加各张卡片锁参与的问题数目,就有
3 N ? k ? 2 ( 2005 ? k ) ? 4010 ? k ? 4010 ? N

故 2 N ? 2005 ,即 N ? 1003 。 下面举例说明,可通过 1003 个问题达到目的。 去掉一张卡片,将其余卡片分成 334 组,每组 6 张卡片。将每组卡片都分别编号 为 1—6 号,且都询问 3 个问题: (1,2,3)(3,4,5)(5,6,1) , , 。这样一来, 在每一组中,编号为 1 ,3 ,5 的卡片都分别出现在两个问题中 ,因此,可以 唯一地确定下来; 而写在编号为 2 , 6 的卡片上的数也可以确定下来。 4, 从而 , 通过
2004 6 ? 3 ? 1002 个问题,就可以知道 2 004 张卡片上的数。剩下的一个问题

用于弄清预先去掉的那一张卡片上的数(只需把它与其他任意两张卡片一起询问 一次)。 4.在考试中,有 4 个选择题,每题有 3 个可能的答案。一群学生参加考试, 结果是对于其中任意 3 个人,都有一个问题,他们的答案各不相同。问至多有多 少个学生? (第 29 届 IMO 预选题) 解: 至多有 9 个学生。 我们设每题有 3 个答案为 0、1、2 三种。如果人数 ? 10 ,则第 4 个问题的答 案中最多的两种至少出现 7 次。考虑这 7 个人,他们对第 4 个问题的答案为 0、 1(设答案 2 最少) 。 这 7 个人对第 3 个问题的答案中, 最多的两种 (设为 0 和 1) 至少出现 5 次。 5 个人(他们对第 3 个问题的答案为 0 或 1)对第 2 个问题的答案中,最多 的两种(不妨仍设为 0 和 1)至少出现 4 次。 因此,有 4 个人,他们对第 2、第 3、第 4 个问题的答案均为 0 或 1,这 4 个人中有两个人对第 1 个问题的答案相同。 这两个人及 (4 个人中的) 另一个人, 对第 1 个问题的答案至少有两个是相同的。因此,如果人数 ? 9 。 另一方面,构造如下: 1 2 3 4 1 0 1 0 1 2 1 2 1 1 3 2 0 2 1 4 0 0 1 0
24

5 6 7 8 9

1 2 0 1 2

1 2 2 0 1

2 0 2 0 1

0 0 2 2 2

5. 有一根由 60 个环组成的锁链,每环重 1 克。最少砍断几个环,就可以利 用断成的一段段锁链,凑出 1 克,2 克,?,59 克,60 克的重量来(被砍断的 环仍然为 1 克)? (1951 年莫斯科数学奥林匹克) 解: 将锁链的第 5,14,31 环砍断,则整个锁链断成 7 部分,其重量分别为 1,1,1,4,8,16,29。容易验证,由它们可以组成从 1 克到 60 克的任何一个 整数重量。 当仅砍断两环时,整个锁链断成 5 部分。5 个元素的集合只有 31 个非空子 集,故由 5 部分锁链所能组成的不同重量不超过 31 个,不满足题设。 所以,最少砍断 3 个环。 6. 设 M ? {1, 2, ? ,1995 } , A 是 M 的子集且满足条件:当 x ? A 时, 15 x ? A 。 则 A 中元素的个数最多是多少? (1995 年全国高中数学联赛)

解: 用 n ( A ) 表示集合 A 所含元素的个数。6、 由题设, k 与 15 k ( k =9,10,?,133)这两个数中至少有一个不属于 A ,所 以至少有 125(=133-9+1)个数不属于 A 。 即 n ( A ) ? 1995 ? 125 ? 1870 另一方面,可取 A ? {1, 2, ? ,8} ? {134 ,135 , ? ,1995 } , A 满足题设条件,此时
n ( A ) ? 1870 。

所以, n ( A ) 的最大值就是 1870。 7. 2 ? n 方格表的每个方格中都写有一个正数,使得每一列中的两个数的和 都等于 1。 证明:可以自每一列中删去一个数,使得每一行中剩下的数的和不超 过
n ?1 4



(2005 年俄罗斯数学奥林匹克)

证明:假设第一行中所放的数为 a1 , a 2 , ? , a n 。必要时通过交换列的位置 ,
b 使得 a 1 ? a 2 ? ? ? a n 。 此时,第二行中所写的数依次为 b1 ? 1 ? a 1 , 2 ? 1 ? a 2 , ?,
b n ? 1 ? a n 。显然 , b1 ? b 2 ? ? ? b n 。

25

如果 a 1 ? a 2 ? ? ? a n ?

n ?1 4

, 那么,就删去第二行中的所有数即可达到目的。
n ?1 4

否则,可以找到使得 a 1 ? a 2 ? ? ? a n ?

成立的最小的 k 。此时,在第一行中删

去 a k , a k ?1 , ? , a n ,在第二行中删去 b1 , b 2 , ? , b k ?1 。由 k 的取法可知
a 1 ? a 2 ? ? ? a k ?1 ? n ?1 4 n ?1 4

.

下面只须证明 b k ? b k ?1 ? ? ? b n ? 由于 a k ?
a1 ? a 2 ? ? ? a k k ? n ?1 4k

,所以

b k ? b k ?1 ? ? ? b n ? ( n ? 1 ? k ) b k ? ( n ? 1 ? k )(1 ? a k )
? ( n ? 1 ? k )(1 ? n ?1 4k )? 5 4 ( n ? 1) ? [ ( n ? 1) ? ( 2 k )
2 2

4k

]

?

5 4

( n ? 1) ? [

2 ( n ? 1)( 2 k ) 4k

]?

n ?1 4

8. 20 个足球队参加全国冠军赛,问至少进行多少场比赛,才能使得任何 3 个队中总有两个队彼此赛过? (1969 年苏联数学奥林匹克) 解: 设进行了 m 场比赛后使得任何 3 个队中总有两个队彼此赛过。 A 队是 设 所有球队参赛场次最少的一个球队,它共参赛 k 场。于是已经与 A 队赛过的队至 少进行了 k 场比赛。没与 A 队赛过的 19 ? k 个队中的任何两队之间都得赛一场, 否则存在 3 个队,其中任何两个队都未彼此赛过。于是有
2 m ? ( k ? 1) k ? 2 C 19 ? k ? 2 ( k ? 9 ) ? 180 ? 180
2 2

这意味着至少进行 90 场比赛。 另一方面,将 20 个足球队分成两组,每组内的任何两队之间比赛一场,不 同组的任何两队之间不比赛,则共进行了 90 场比赛。由于任何 3 个队中总有两 个队同组,它们之间已经进行了一场比赛,这种安排满足题设要求。 所以,至少要进行 90 场比赛。 9. 设 { B1 , B 2 , ? , B k } 是 A 的一族非空子集,当 i ? j 时, B i ? B j 至多有两个 元素,求 k 的最大值。 (1985 年 IMO 预选题) 解: 首先, 易见 A 的至多含 3 个元素的所有子集所构成的子集族满足题设要 求,其中子集的个数为

C

1 10

?

C

2 10

?

C

3 10

? 175

所以, k 的最大值不小于 175。 另一方面,设有一个子集族 ? 满足题设要求且有 A 的子集 B ? ? , B 中至少
26

有 4 个元素。 x ? B , B / ? B ? { x} 。 设 令 因为 B ? B / 至少有 3 个元素, B / ? ? 。 故 于是当用 B / 代替 ? 中的 B 时, ? 中的子集数不减且仍然满足题设要求。重复这 个过程,总可使得 ? 中的每个子集的元素不多于 3 而且 ? 中的子集数不减。由 此可见, ? 中的子集数不多于 175。 因此, k 的最大值为 175。 10. 设 M ? { x1 , x 2 , ? , x n } 是自然数 1, 2 , ? , n 的一个排列。 f (M ) 是 M 中每两 个相邻元素的差的绝对值的最小值。求 f (M ) 的最大值。 (1989 年 IMO 预选题) 解: f (M ) 的最大值为 ? ? 。下面分情况讨论: ?2? (1) n ? 2 k 时, k 与其相邻数之差的绝对值不大于 k ,故 f ( M ) ? k ? ? ? 。 ?2? 另一方面,令 M ? ( k ? 1,1, k ? 2, 2, ? , 2 k , k ) ,则有 f ( M ) ? k 。 ( 2 ) n ? 2k ? 1 时 , k ? 1 与 其 相 邻 数 之 差 的 绝 对 值 不 大 于 k , 故
?n? f ( M ) ? k ? ? ? 。 另 一 方 面 , 令 M ? ( k ? 1,1, k ? 2 , 2 , ? , 2 k , k , 2 k ? 1) , 则 有 ?2?
f (M ) ? k 。

?n?

?n?

综上,命题成立。 11. 试证可以用 4 种不同颜色为数集 M ? {1, 2, ? ,1987 } 中的每个数都涂上一 种颜色,使得 M 中任何一个成等差数列的 10 元子集中的 10 个数的涂色都不全 相同。 (1987 年 IMO 预选题) 证明: 首先,我们计算 M 中包含的 10 项等差数列的个数。公差为 1 的 10 项等差数列共 1978 个;公差为 2 的 10 项等差数列共 1969 个;公差为 3 的 10 项等差数列共 1960 个;?;公差为 220 的 10 项等差数列共 7 个。故 M 中包含 的 10 项等差数列的总数为 1978+1969+1960+?+7=218350 因此,有同色的 10 项等差数列的染色法的种数不多于
n ? 218350 ? 4 ? 4
1977

?4

1987

而所有不同的染色法的总数为 4 1987 ,故必有一种染色法满足题设要求。

27

12. 有一个正 2 n ? 1( n ? 1) 边形。 两人按如下法则做游戏:轮流在该正多边 形内画对角线,每人每次画一条新的(以前没有画过的)对角线 ,而它恰好与已画 出的偶数条对角线相交(交点在正多边形内) ,凡无法按照要求画出对角线者即 为负方。问:谁有取胜策略? (2007 年俄罗斯数学奥林匹克) 解:将先开始的人称为甲 ,后开始的人称为乙。 如果 n 为奇数 ,则乙有取胜策略;如果 n 为偶数 ,则甲有取胜策略。 由于正多边形的边数为奇数 ,则对于任何一条对角线来说 ,都是在它的一 侧有奇数个顶点 ,在另一侧有偶数个顶点。 因此 ,每一条对角线都与偶数条其他 对角线相交。 假设到某个时刻 ,游戏不能再继续下去 ,此时 ,每一条未画出的对角线都 与奇数条已画出的对角线相交。 这样的情况只能出现在未画出的对角线的条数为 偶数的时刻。 事实上 ,如果对每一条未画出的对角线都数一数与它相交的未画出 的对角线的条数 ,那么 ,每一条未画出的对角线都被数了两次 ,总和应当为偶 数;但若未画出的对角线的条数为奇数 ,那么 ,总和就是奇数个奇数的和 ,仍为 奇数 ,由此产生矛盾。因此 ,未画出的对角线的条数为偶数。 如此一来 ,如果多边形中的对角线的总条数为奇数 ,那么 ,就应当是甲取 胜;而若对角线的总条数为偶数 ,那么 ,就应当是乙取胜。 众所周知 ,在正 2 n ? 1 边形中 ,共有
( 2 n ? 1)( 2 n ? 2 ) 2 ? ( n ? 1)( 2 n ? 1)

条对角线。 所以 ,当 n 为奇数时 ,对角线的总数为偶数 ,此时 ,乙可取胜;当 n 为偶数时 ,对角线的总数为奇数 ,此时 ,甲可取胜。 13. 坐标平面上的每个整点都被染为 3 种颜色之一,且 3 种颜色的点都有。 证明:可找到 1 个直角三角形,它的 3 个顶点是 3 种不同颜色的点。 (2004 年俄罗斯数学奥林匹克) 证明:将平面上的整点称为结点。 如果在每 1 条竖直直线上的所有结点都 是同一种颜色的 ,则任选其中 1 个结点(设其为 1 号色) 。作 2 条经过它的相 互垂直的直线 ,使它们与竖直方向都交成 45° 的角 ,且在它们上面分别取出 1 个 2 号色的点和一个 3 号色的点(这是可以做到的 ,因为存在具有这些颜色 的点的竖直直线) ,所得的直角三角形即为所求。如果每 1 条水平直线上的所有 结点都是同一种颜色的 ,则可类似地解答。 如果存在 1 条竖直直线 l ,其上的结点分别被染为 2 种不同颜色(设为 1 号 色和 2 号色) ,那么 ,我们任取 1 个 3 号色的点 C ,再取出与点 C 同在 1 条水 平直线上的那个位于直线 l 上的点 A (不妨设其为 1 号色) ,以及位于直线 l 上 的具有 2 号色的点 B ,所得的直角三角形即为所求。 如果存在一条竖直直线 l ,其上的结点分别被染为 3 种不同颜色 ,那么 , 我们再取 1 条水平直线 h ,使得其上的点不是同一种颜色。 不妨设它们的交点 A 是 1 号色的。我们在直线 h 上取一点 B 使其与 A 异色(设其为 2 号色) ,再在直 线 l 上取 1 个 3 号色的点 C 即可。 14. 已知 n ( n ? 2 )条直线把平面分成若干个区域,其中的一些区域被涂 上颜色,使得任何两个涂色区域都没有公共边,求证涂色区域的数目不超过
28

1 3

(n ? n)
2

(1985 年全苏数学奥林匹克)

证明: 如果给定的 n 条直线两两平行,结论显然成立。设有 k 条边的涂色区 域的个数为 m k , k ? 2 ,3, ? , n 。因为每条直线被其他直线分割成至多 n 部分(线 段或射线) ,因此, n 条直线互相相交至多分成 n 2 个部分。由已知,每个部分至 多是一个涂色区域的边,所以
2 m 2 ? 3 m 3 ? ? ? nm n ? n
2



又因每条直线上只有两端的射线部分才可能是有两条边的涂色区域的边,故有
m 2 ? n ,从而由①知
m2 ? m3 ? ? ? mn ?
m2 3 ? 1 3 ( 2 m 2 ? 3 m 3 ? ? ? nm n ) ?

1 3

(n ? n)
2

15. 从 n 个元素 a1 , a 2 , ? , a n 中取两个组成一对,共组成 n 对 p 1 , p 2 , ? , p n 。 如果 {a i , a j } 是其中一对,则两对 p i 和 p j 中恰好有 1 个公共元素,求证每个元素 恰好属于其中两对。 (1985 年 IMO 预选题)

证明: 设包含 a k 的数对的个数为 d k , k

? 1, 2 , ? , n ,于是有


d1 ? d 2 ? ? ? d n ? 2n

对于每个 d k ,在 d k 个数对中,任何两个数对 p i , p j 都以 a k 为公共元素。 由已知, {a i , a j } 是数对之一时,两对 p i 和 p j 中恰好有 1 个公共元素,从而

C
由此及①得
2

2 d1

?Cd ???Cd ? n
2 n

2

2

d1 ? d 2 ? ? ? d n ? 4n
2 2



由均值表达式和①、②有

4n ? (d 1 ? d 2 ? ? ? d n ) ? n (d12 ? d 2 2 ? ? ? d n 2 ) ? 4n 2
2 2

这意味着上述不等式中等号成立,从而必有 d 1 即每个元素恰好属于两对之中。

? d2 ? ? ? dn ? 2 ,

16. 将 ( n ? 1) ? ( n ? 1) 的方格表的 n 2 个结点中的每个涂上红、蓝两色之一,
29

求使表中每个方格都恰有两个红色顶点的不同涂色方案的种数。 (1996 年 IMO 预选题) 解: 将第 1 行的 n 个结点中的每个涂上红、蓝两色之一,共有 2 n 种不同涂色 方案,分情况计数。 (1)第 1 行中任何两个相邻结点都异色,即红蓝相间地涂色,有两种不同 的涂色方案。这时不难发现,第 2 行结点也必须红蓝相间地涂色,又是有两种不 同的涂色方案。以此类推,每行结点也必都须红蓝相间地涂色。由乘法原理知, 整个方格表共有 2 n 种不同涂色方案。 (2)第 1 行结点中有两个相邻结点同色,共有 2 n ? 2 种不同的涂色方案。 这时不难发现, 1 行结点中同色的两个相邻结点下方第 2 行的两个相邻结点也 第 必须同色,且与第 1 行的两个结点异色。以此推出,第 2 行的每个结点都与第 1 行的同列结点异色,即第 2 行结点只有唯一的涂色方案。同理可知,后面每行结 点也只有唯一的涂色方案。所以这种情形共有 2 n ? 2 种不同的涂色方案。 由加法原理知,整个方格表共有 2 n ?1 ? 2 种不同涂色方案。
xy 25

17. 设 A 是正整数集合 N ? 的子集,对任何 x , y ? A , x ? y ,有 | x ? y |? 求 | A | 的最大值。 (1985 年 IMO 预选题)



解: 令 X 1 ? {1} , X 2 ? {2} , X 3 ? {3} , X 4 ? {4} , X 5 ? {5,6} , X 6 ? {7 ,8,9} ,
X 7 ? {10 ,11, ? ,16 } , X 8 ? {17 ,18 , ? ,53 } , X 9 ? {54 ,55 , ?} ? N \ {1, 2 , ? ,53} 。
?

对 于 X 9 , 当 x , y ? X 9 时 , x ? 25 , 所 以 y ? x ? y ? y ?
X i ( i ? 1, 2 , ? ,8 ) ,当 x , y ? X i 时,显然有 y ? x ?
xy 25

x 25

?

xy 25

,而对于

,于是 A 最多只能含有上述每

个集合中的一个数,所以 | A |? 9 。 令 A ? {1, 2 ,3, 4 ,5,7 , ,10 ,17 ,54 } 满足题设条件,所以 | A | 的最大值为 9。 18.有 1999 个集合, 每个集合有 45 个元素, 任意两个集合的并集有 89 个元 素,问此 1999 个集合的并集有多少个元素。(1993 年湖北竞赛题) 解: 首先说明这 1999 个集合中必有一个集合 A 中的元素 a 出现在 A 以外的 45 个集合中。 如若不然, 集合 A 中的每个元素至多出现在 A 以外的 44 个集合中, 则集合 A 中的元素在其余集合中出现的次数和小于等于 44 ? 45 ? 1998 , 这与任意 两个集合有且仅有一个公共元素矛盾。
30

因此,可设 A 中的元素 a 出现在 A1 , A 2 , ? , A 45 ,其余的设为 A 46 , A 47 , ? , A1998 。 设 B 为 A 46 , A 47 , ? , A1998 中任一集合,且 a ? B 。由题设, B 和 A , A1 , A 2 , ? , A 45 都 有一个公共元素,因此 46 个元素各不相同,故 B 中有 46 个元素,与题设矛盾, 可见这 1999 个集合都含有 a ,故这 1999 个集合中任意两个集合除了 a 这个公共 元素外再无其他公共元素。 因此,所求结果为 1999 ? 44 ? 1 。 19.围绕一个圆桌坐着来自 50 个国家的 100 名代表,每个国家 2 名代表。 证明:可以将他们分成两组,使得每一组都是由来自 50 个国家的 50 名代表组成, 并且每一个人都至多与自己的一个邻座的人同组。 (2005 年俄罗斯奥林匹克) 解:将 100 名代表分成 50 个 “相邻对” ,将同一对中的二人称为熟人。 显然 ,为了证明题中断言 ,只须证明每一对熟人都可以被分拆到两个不同的组 中。下面给出一种具体的操作方法。 先将第 1 个国家的代表甲分在第 1 组 ,代表乙分在第 2 组;接着将代表乙的 熟人(假设他是第 i 个国家的代表甲)分到第 1 组 ,将第 i 个国家的代表乙分 在第 2 组;再将他的熟人分到第 1 组 ,如此下去。 如果到某一步发现某个代表的 熟人已经被分在第 1 组 ,那么 ,该熟人一定就是那个最先被分到第 1 组的人。 到此所作的分组方式都是符合要求的。 如果此时还有人没有被分配 ,那么 ,就对他们重新进行与刚才一样的分组 过程即可。 20. 在凸 100 边形的每个顶点上都写有两个不同的数。证明:可以从每个顶 点上划去一个数 ,使得任意两个相邻的顶点上剩下的数都互不相同。 (2007 年俄罗斯数学奥林匹克) 解: 如果在各个顶点上都写着同样的一对数 a 与 b ,则只需在所有偶数编号 的顶点上都留下 a ,在所有奇数编号的顶点上都留下 b ,即满足要求。 现在假设不是这种情况 ,即可以找到两个相邻的顶点 A、 B ,在它们上面写 着的是两对不同的数。 从顶点 A 开始 ,依次为各个顶点编号 ,使得 A 为 1 号 ,B 为 100 号。 将各个顶点上的数都染为一红一蓝。 首先 ,任意将第 1 号顶点上的两个数分 别染为一红一蓝。 其次 ,假设已经将第 k 号顶点上的两个数 a 与 b 分别染为红 色与蓝色 ,那么 ,在将第 k + 1 号顶点上的两个数染色时 ,便有意地使得红色 的数不是 a ,蓝色的数不是 b。依此下去。 于是 ,除了 1 号顶点 A 和 100 号 顶点 B 之外 ,任何两个相邻顶点上的颜色相同的数都是互不相等的。而在顶点 A、 B 上 ,决不可能红色两数彼此相等 ,蓝色两数也彼此相等(否则 ,与 “它们 上面写着的是两对不同的数” 的事实相矛盾) ,因此 ,其中必有某一种颜色的两 数互不相等。 不妨设它们上面的蓝色两数互不相等。 于是 ,只要擦去所有红色的 数即满足要求。 21. 设凸 n 边形的任意 3 条对角线不相交于形内一点,求它的对角线在形内 的交点总数。 解: 依题意,一个交点 P 由两条对角线 l 与 m 相交而得,反之,两条相交的
31

对角线 l 与 m ,确定一个交点 P ,而 P 与( l , m )可建立一一对应。 又因两条相交的对角线 l 与 m 分别由凸 n 边形中两对顶点 A , B 和 C , D 连 接而成,故( l , m )又可与 4 顶点组( A , B , C , D )建立一一对应,即有 P ? (l ,m )? ( A , B ,C , D ) 因此,形内对角线的交点总数=凸 n 边形的 4 顶点组的组数= C n4 。 22. 已知一个保险柜由 11 个成员的委员会负责管理,保险柜上加了若干把 锁, 这些锁的钥匙分配给各个委员保管使用。为了使任何 6 个委员同时到场就能 打开保险柜, 而任何 5 个委员同时到场都不能打开保险柜,最少应给保险柜加多 少把锁? (1971 年波兰数学奥林匹克) 解: 设满足要求的锁的最少把数为 n ,并记这 n 把锁的集合为 A 。设 Ai 为

是第 i 个委员可以打开的锁的集合。依题意,对于 {1, 2, ? ,11} 的任何 5 元子集
{i1 , i 2 , ? , i 5 } ,都有

Ai1 ? Ai2 ? Ai3 ? Ai4 ? Ai5 ? A
对于 {1, 2, ? ,11} 的任何 6 元子集 { j1 , j 2 , ? , j 6 } ,都有



A j1 ? A j 2 ? A j 3 ? A j 4 ? A j 5 ? A j 6 ? A
5



由①知集合 A ?

?A
k ?1

ik

非空,设

x i1 ? i5

是它的一个元素。这表明, x i1 ? i5

所代表的锁是编号为 i1 , ? , i 5 的那 5 个委员打不开的一把锁。②式则表明,对任 何 j ? {i1 , ? , i5 } ,都必有 x i1 ? i 5 与锁之间建立一个对应关系。 这个关系是个单射。否则,设对于两个不同的 5 元子集 {i1 , i 2 , ? , i 5 } 和
{k 1 , k 2 , ? , k 5 } 有

? A j 。从而将 {1,2, ? ,11} 的任何

5 元子集

x i1 ? i5 ? x k 1 ? k 5

。因为两个 5 元子集不同,故这两个 5 元子

集的并集至少有 6 个元素,而这就导致有 6 个人都打不开同一把锁,矛盾。
5 因为 {1, 2, ? ,11} 的不同 5 元子集共有 C 11 ? 462 个,所以锁的把数 ? 462 。

另一方面,如果给保险柜加了 462 把锁,并将这些锁与 {1, 2, ? ,11} 的 462 个 5 元子集建立一一对应关系。将每把锁的 6 枚钥匙分发给这把锁对应的 5 人组之 外的 6 个委员掌管使用,则任何 6 个委员同时到场就能打开保险柜,而任何 5 个委员同时到场都不能打开保险柜。 所以,最少应给保险柜加 462 把锁。
32

23. 如图,在 7× 的长方形棋盘的每个小方格的中心点各放一个棋子。如果 8 两个棋子所在的小方格共边或共顶点,那么称这两个棋子相连。现从这 56 个棋 子中取出一些,使得棋盘上剩下的棋子,没有五个在一条直线(横、竖、斜方向) 上依次相连。问最少取出多少个棋子才可能满足要求?并说明理由。 (2007 ,全国高中数学联赛) 解:最少要取出 11 个棋子,才可能满足要求。其原因如下: 如果一个方格在第 i 行第 j 列,则记这个方格为(i,j)。 第一步证明若任取 10 个棋子, 则余下的棋子必有一个 五子连珠,即五个棋子在一条直线(横、竖、斜方向) 上依次相连。用反证法。假设可取出 10 个棋子,使余 下的棋子没有一个五子连珠。 如图 1, 在每一行的前五 格中必须各取出一个棋子,后三列的前五格中也必须 各取出一个棋子。这样,10 个被取出的棋子不会分布 在右下角的阴影部分。同理,由对称性,也不会分布 在其他角上的阴影部分。 1、 行必在每行取出一个, 第 2 且只能分布在(1,4)、(1,5)、(2,4)、(2,5)这些方格。同理(6,4)、(6,5)、(7, 4)、(7,5)这些方格上至少要取出 2 个棋子。在第 1、2、3 列,每列至少要取出 一个棋子,分布在(3,1)、(3,2)、(3,3)、(4,1)、(4,2)、(4,3)、(5,1)、(5, 2)、(5,3)所在区域,同理(3,6)、(3,7)、(3,8)、(4,6)、(4,7)、(4,8)、(5, 6)、(5,7)、(5,8)所在区域内至少取出 3 个棋子。这样,在这些区域内至少已 取出了 10 个棋子。因此,在中心阴影区域内不能取出棋子。由于①、②、③、 ④这 4 个棋子至多被取出 2 个,从而,从斜的方向看必有五子连珠了。矛盾。

图1 图2 第二步构造一种取法,共取走 11 个棋子,余下的棋子没有五子连珠。如图 2, 只要取出有标号位置的棋子,则余下的棋子不可能五子连珠。 综上所述,最少要取走 11 个棋子,才可能使得余下的棋子没有五子连珠。

24.将周长为 24 的圆周等分为 24 段,从 24 个分点中选取 8 个点,使得其中 任何两点所夹的弧长都不等于 3 和 8。问满足要求的 8 点组的不同取法有多少 种? (2001 年 CMO 题) 解 设 24 个分点依次为 1,2,?,24,将 24 个数列成下表: 1 4 7 10 13 16 19 22
33

9 12 15 18 21 24 3 6 17 20 23 2 5 8 11 14 表中每行相邻两数所代表的点所夹弧长为 3,每列相邻两数所代表的点所夹 弧长为 8,故每列至多取一个数,8 列至多取 8 个数,但一共要取 8 个数,故每 列恰取一个数且相邻两列所取的数不同行。 若将每列看作一个扇形,每列中第一、二、三行看作三种颜色,则由上面例 题知,
a 8 = ( 3 ? 1) ? ( ? 1) ( 3 ? 1) =258 种。
8 8

25. 一种密码锁的密码设置是在正 n 边形 A1 A2 ? An 的每个顶点处赋值 0 和 1 两个数中的一个,同时在每个顶点处涂染红、蓝两种颜色之一,使得任意相邻的 两个顶点的数字或颜色中至少有一个相同。问:该种密码锁共有多少种不同的密 码设置? (2010 年全国高中联赛题) 解:每个顶点都有红 0、红 1、蓝 0、蓝 1 共 4 种不同标法,其中红 0 与蓝 1、 红 1 与蓝 0 不能相邻,这里称之为相冲。由于正 n 边形并非本质,我们不妨只考 虑凸 n 边形,设给按环形排列的 n 个点 A1 A2 ? An 作标记的总的方法数有 T n 种。
? 现依次给 A1、 A2、 A3、 An ? 2、 An ?1 作标记,使得 Ai ?1 与 Ai 不相冲,总的方法

数有 4 ? 3 n ? 2 种。 设其中 An ?1 与 A1 数字和颜色都相同的方法数为 a n , 其中 An ?1 与 A1 数字和颜色不都相同的方法数为 b n 。因此有
4?3
n?2

? a n ? bn



若 An ?1 与 A1 数字和颜色都相同, A n 有 3 种标记方法使得其与 An ?1 和 A1 均不 相冲,例如, An ?1 与 A1 都标记红 0, A n 可选择标记红 0、红 1、蓝 0 中的任何一 种。若 An ?1 与 A1 数字和颜色不都相同, A n 有 2 种标记方法使得其与 An ?1 和 A1 均 不相冲,例如, An ?1 标记蓝 0 而 A1 标记红 0, A n 可选择标记红 0、蓝 0 中的任何 一种。因此有
T n ? 3a n ? 2b n



又当 An ?1 与 A1 数字和颜色都相同时,可将 A n ? 2 与 A1 连接得到凸 n ? 2 边形, 而使得 A n ? 2 与 A1 不相冲,因此有
a n ?1 ? T n ? 2



34

①×2-②得
8?3
n?2

? T n ? a n ?1

又由③得
8?3
n?2

? Tn ? Tn ? 2

易得
T n ? 3 ? ( ? 1) ? 2
n n

26.将与 105 互素的正整数从小到大排成数列,求出这个数列的第 1000 项。 (1994 年全国高中联赛题) 解: 首先,求出 S ={1,2,?,105}内与 105=3 ? 5 ? 7 互素的正整数的个数, 令 Ai ={ m | m ∈ S 且 m 被 i 整除}( i =3,5,7) 。于是 S 中与 105 互素的正整数的 个数为 | A3 ? A 5 ? A 7 | =| S |-| A3 |-| A5 |-| A7 |+| A3 ? A5 |+| A3 ? A7 |+| A5 ? A7 |-| A3 ? A5 ? A7 | =105- ?
? 105 ? ? 105 ? ? 105 ? ? 105 ? ? 105 ? ? 105 ? ? 105 ? ? - ? 5 ? - ? 7 ? + ?3 ? 5 ? + ?3 ? 7 ? + ?5 ? 7 ? - ?3? 5 ? 7 ? ? 3 ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ?

=105-35-21-15+7+5+3-1=48 其次,设所有正整数中与 105 互素的正整数从小到大排成数列为{ a n },于 是有,a 1 =1,a 2 =2,a 3 =4, ?,a 46 =101,a 47 =103,a 48 =104, 并记 P ={ a 1 ,a 2 , ?,
a 48 }。

一方面, 数列{ a n }中每一项 a n 可表示成为 a n = 105 ? k ? r ( k ,r 为非负整数, 0≤ r ≤104) ,于是由( a n ,105)=( 105 ? k ? r ,105)=( r ,105)=1,知 r ∈ P , 即数列{ a n }中每一项 a n 可表示成为 a n = 105 ? k ? r ( k 为非负整数, r ∈ P )的形 式。 另一方面,对任意非负整数 k 及任意 r ∈ P ,由( 105 ? k ? r ,105)=( r , 105)=1,知数列{ a n }中必有某一项 a n = 105 ? k ? r 。 可见, 数列{ a n }有且仅有形如 105 ? k ? r ( k 为非负整数,r ∈ P )的数组成, 因对每一个固定的 k , r 取遍 P 中的数时,形如 105 ? k ? r 的数有 48 个,得到数 列中的 48 个项,因为 1000= 48 ? 20 +40,所以, a 1000 = 105 ? 20 + a 40 。
35

而 a 48 =104, a 47 =103, a 46 =101, a 45 =97, a 44 =94, a 43 =92, a 42 =89, a 41 =88,
a 40 =86,所以 a 1000 = 105 ? 20 +86=2186。

27. 设 f (n ) 表示平面上任何三点不共线的 n ( n ? 4 )个点所组成的三角形
? 中,非锐角三角形个数的极小值。 ? 1 ? ? 2 ? ? 3 ? 0 , 4 ? 设
f (4)

C

3 4

? , 5 ?

f (5)

C

3 5

, ?,

?n ?

f (n)

C

3 n

,?,则数列{ ? n }是递增数列。 (自编题)
1 4 ? ?3

证明: 用数学归纳法证明。显见 ? 4 ?

假设当 n ? k 时 , ? k ? ? k ?1 ,当 n ? k ? 1 时 ,选取非锐角三角形个数取得极小 值的 k ? 1 个点 ,这 k ? 1 个点组成 k ? 1 个 “ k 点组” ,显然每个“ k 点组”中至 少有 f (k ) 个非锐角三角形 ,总共至少有 ( k ? 1) f ( k ) 个非锐角三角形,因为每个非 锐角三角形存在于( k ? 2 )个“ k 点组”(因为 k ? 1 点中除了该三角形三点外还有 k ? 2 个点 ,去掉 k ? 2 个点中的任意一点就与该三角形组成一个“ k 点组”) ,即每 个非锐角三角形重复计算了( k ? 2 )次 ,故有
f ( k ? 1) ? ( k ? 1) f ( k ) k?2

不等式两边同时除以 从而命题得证。 征解题:是否 lim ? n ?
n? ?

C

3 k ?1

,即得 ? k ?1 ? ? k 。

1 2



28.有多少种方法能将从 1 到 n 的 n 个整数排成下面的排列:除了左边的 第一个整数外,每一个数都与它左方(不必相邻)的某一个数相差 1? (1965 年第 26 届美国普特南数学竞赛题) 解:对从 1 到 n 的符合题意的每一个排列都称之为 n 排列。 当 n ? 2 时,可得两个 2 排列: 12,21. 当 n ? 3 时,可得 4 ? 2 2 个 3 排列: 123,213,231,321. 当 n ? 4 时,可得 8 ? 2 3 个 4 排列: 1234,2134,2314,3214,
36

2341,4321,3421,3241. 猜想: (1) n 排列必以 1 或 n 结尾; (2) n 排列的个数为 2 n ?1 . 下面用数学归纳法证明. 对 n ? 1, 2 ,3, 4 ,猜想(1)已成立. 假设对 n ? k 结论成立.则当 n ? k ? 1 时,任取一个 k ? 1 排列:
a ? a 1 a 2 ? a k a k ?1

若 a k ?1 ? 1 或 a k ?1 ? k ? 1 ,则从 a 中删去 k ? 1 ,则由归纳假设,这个 k 排列应以 1 或 k 结尾,即 a k ?1 ? 1 或 a k ?1 ? k .但 k ? 1 不论位于前面的什么位置, a 都不能成为
k ? 1 排列,矛盾.因而 k ? 1 排列也是以 1 或 k ? 1 结尾.

从而对所有自然数 n ,猜想(1)成立. 假设 n ? 1 排列的个数为 2 n ? 2 ,在其每个末尾处添上 n 即可得 n 排列,个数仍为
2
n?2

. 对这样的每个 n 排列作一一映射:
a 1 , a 2 , ? , a n ?1 , n ? n ? 1 ? a 1 , n ? 1 ? a 2 , ? , n ? 1 ? a n ?1 ,1 ,

恰好得到以 1 结尾的 n 排列,个数也为 2 n ? 2 . 因此, n 排列的个数 ? 2 n ?1 . 另一方面,由猜想(1)知, n 排列必以 1 或 n 结尾.对于以 n 结尾的 n 排列,删去 n 后得到 n ? 1 排列,其个数不超过 2 n ? 2 ;对于以 1 结尾的 n 排列,删去 1 后,再将每个元 素减去 1 后得到 n ? 1 排列, 其个数不超过 2 n ? 2 . 因此, n 排列的个数 ? 2 n ?1 . 故猜想(2)成立. 29.不定方程 x1 ? x 2 ? ? ? x m ? n ( m ? 2, n ? 2, m ? n )的正整数解有 组。 证明:用 “隔板法” 证明引理。 由于 x 1 ? 1 ,x 2 ? 1 , ?, x m ? 1 ,把 n 分成 n 个 1 ,这 n 个 1 共有 n - 1 个空 档。插入 m - 1 块“隔板”,把 n 个 1 分成 m 个部分,则 每一种情况对应不定方程的一组解.所以,原不定方程共有 C n ?1 组解.
37
m ?1

C

m ?1 n ?1

推论:不定方程 x1 ? x 2 ? ? ? x m ? n ( m ? 2 , n ? N )非负整数解有 C n ? m ?1 组。 30. 8 个女孩,25 个男孩围成一个圆周,每两个女孩之间至少站有 2 个男 孩,共有 种不同的排列方法。 (只把圆旋转一下就重合的排法认为是相同 的) (1990 年全国高中联赛题) 解 以 8 个女孩为组长, 25 个男孩分入该 8 个组,各组内男孩数记为 x 1 , 将

m ?1

x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 ,则 x 1 + x 2 +?+ x 8 =25( x i ? 2 , i ? 1, 2 , ? ,8 )①

令 y i = x i -2,则 y 1 + y 2 +?+ y 8 =9( Yi ? 0 , i ? 1, 2 , ? ,8 )②
?1 7 于是,①的正整数解组的组数等于②的非负整数解组的个数 C 98? 8 ?1 = C 16 ,即

7 25 个男孩分入该 8 个组,每组至少两人的分组方法有 C 16 种。8 个组排成每组以

女孩为头的圆排列有 (8 ? 1)! = 7! 种排列方法,再 25 个男孩站入的方法数为 25 ! ,
7 所以总的排列方法为 C 16 ? 7! ? 25 !

31.如果从数 1 ,2 , ?,14 中,按由小到大的顺序取出 a 1 、 a 2 、 a 3 ,使得同时 满足 a 2 ? a 1 ? 3 与 a 3 ? a 2 ? 3 .那么,所有符合要求的不同取法有多少种。 (1989 ,全国高中数学联赛) 解: 由 a 1 ? 1 , a 2 ? a 1 ? 3 , a 3 ? a 2 ? 3 , 14 ? a 3 ? 0 令 a 1 ? x1 , a 2 ? a1 ? x 2 , a 3 ? a 2 ? x 3 , 14 ? a 3 ? x 4 ,则
x1 ? x 2 ? x 3 ? x 4 ? 14 .

于是,问题转化为求不定方程在
x 1 ? 1 , x 2 ? 3 , x 3 ? 3 , x 4 ? 0 下的整数解的组数。

将方程转化为
x1 ? ( x 2 ? 2 ) ? ( x 3 ? 2 ) ? ( x 4 ? 1) ? 11

令 x1 ? y 1 , x 2 ? 2 ? y 2 , x 3 ? 2 ? y 3 , x 4 ? 1 ? y 4
a 而 y 1 ? y 2 ? y 3 ? y 4 ? 11 的正整数解的组数是 C 10 。 所以 ,符合条件的 a 1 、 2 、
a 3 的不同取法有 C 10 ? 120 种。
3 3

38


2012夏令营组合综合

2012员工夏令营专刊 7页 免费 2012夏令营方案 5页 1下载券 2012夏令营班主任点到...组合综合 1、对应法 定义 设 f 是从集合 M 到集合 N 的映射。 若对任意 ...

2012夏令营班主任点到册

夏令营方案2012-2 6页 2财富值 2012夏令营组合综合 38页 1财富值 2012夏令营申请 2页 2财富值 2012班主任培训 28页 2财富值 2012夏令营 暂无评价 16页 10财富...

2012,应该给孩子选择怎样的夏令营

夏令营方案2012-2 6页 1下载券 2012夏令营组合综合 38页 1下载券喜欢...以夏令营的形式有限制地对外开放原本封闭式训练的高尔夫 训练基地, 旨在为高尔夫爱好...

2012夏令营瞭望起航夏令营

夏令营方案2012-2 6页 2财富值 2012夏令营组合综合 38页 1财富值 2012夏令营申请...励志夏令营是面向全国中小学生举办的以“怀青云之志,观华东名校”和“感受名校,...

青草2012夏令营教案

2012夏令营 3页 免费 2012夏令营 20页 4下载券 夏令营手册2012 25页 免费 夏令营方案2012-2 6页 1下载券 2012夏令营组合综合 38页 1下载券 2012夏令营申请 2页...

电气工程学院2012年夏令营综合成绩

电气工程学院2012夏令营综合成绩_其它考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 电气工程学院2012夏令营综合成绩_其它考试_资格考试/认证...

2012年夏令营申请全套附件(排版完整,下载及修改标题即可打印或发布)

湖南大学工商管理学院 2012 年优秀大学生暑期夏令营 申请表 申请类别:□硕博连读生 □推免研究生姓名 性别 民族 申请攻读专业:出生日期 手机号码 年月 当年一寸 ...

2012夏令营试题

2012 年“扬子石化”杯第 26 届全国高中生化学竞赛(江苏赛区)夏令营选拔赛试题...山东省2012届高中数学夏... 5页 免费 2012夏令营组合综合 38页 1下载券 ©...

2012夏令营《营员手册》

2012 年世界文化之旅夏令营 《营员手册》特别声明: 营员须遵守夏令营营规,如营员严重违反营规,主办方管理人员、夏令营训练师及管理 人员、学校带队老师及辅导员等...

201207组合初步

2012 年江苏省中学数学奥林匹克夏令营 组合初步 2012 年江苏省中学数学奥林匹克夏令营讲座 组合初步(竞赛题) 例题: 1、 (2012 年 5 月日本算数奥林匹克广中杯...