9512.net
甜梦文库
当前位置:首页 >> 高一数学 >>

数学奥赛辅导


数学奥赛辅导
知识、方法、技能
Ⅰ.组合恒等式

第九讲

组合恒等式、组合不等式

竞赛数学中的组合恒等式是以高中排列组合、二项式定理为基础,加以推广、补充而形 ① 成的一类组合问题.组合恒等式的证明要借助于高中常见的基础组合等式.例如
Cn ? Cn
r n?r r ?1



C n ?1 ? C n

r ?1

? Cn

r

③ C r ? n C r ?1 n n ?1
r

④ C C ⑤ 0
r n

m n

? C n ? C n?m
m 1 2

r?m

Cn ? Cn ? Cn ?? ? Cn ? 2
n

n

⑥ C 0 ? C 1 ? C 2 ? C 3 ? ? ? ( ? 1) n C n ? 0 n n n n n 组合恒等式的证明方法有: ①恒等变形,变换求和指标; ②建立递推关系; ③数学归纳法; ④考虑组合意义; ⑤母函数. Ⅱ.组合不等式 组事不等式以前我们见的不多,在其他一些书籍中组合不等式的著述也很少,但是近年 来组合不等式的证明却出现在国内、国际大赛上.例如 1993 年中国高中数学联赛二试第二大 题为: 设 A 是一个有 n 个元素的集合,A 的 m 个子集 A1,A2?,Am 两两互不包含,试证: (1) ?
m

1 Cn
| AI |

? 1;

i ?1

1

(2) ? C n
i ?1

m

| AI |

? m

2

其中|Ai|表示 Ai 所含元素的个数, C n 表示 n 个不同元素取|Ai|的组合数. 再如 1998 年第 39 届国际数学奥林匹克竞赛中第二大试题为: 在某一次竞赛中,共有 a 个参赛选手与 b 个裁判,其中 b≥3,且为奇数.每个裁判对每 个选手的评分中只有“通过”或“不及格”两个等级,设 k 是满足条件的整数;任何两个裁 判至多可对 k 个选手有完全相同的评分. 证明:
k a ? b ?1 2b .

| AI |

因此我们有必要研究组合不等式的证明方法.组合不等式的证明方法有: 1.在集合间建立单射,利用集合阶的不等关系 定理,设 X 和 Y 都是有限集,f 为从 X 到 Y 的一个映射, (1)若 f 为单射,则|X|≤|Y|; (2)若 f 为满射,则|X|≥|Y|. 2.利用容斥原理 例如: 设元素 a 属于集族{A1, 2, An}的 k 个不同集合 A i , A i , ? , A i , A ?, 则在 ? | A i |
1 2 k

n

i ?1

中 a 被计算了 k 次,当 k≥2 时,集合 A i , A i , ? , A i 两两的交集共有 C k2 个.由于
1 2 k

Ck ?
2

k ( k ? 1) 2

? k ? 1, 故 a 在

1? i ? j ? n

?|A

i

? A j | 中至少少被计算了 k-1 次,这样我们得到下面

的不等式:
n

| ? A i |?
i ?1

? |A
i ?1

n

i

|?

1? i ? j ? n

?|A

i

? Aj |

组合不等式(*)可由容斥公式:
n

| ? A i |?
i ?1

?

n

|A i | ?

i ?1

1? i ? j ? n

?

| A i ? A j | ? ? ? ( ? 1)

( n ?1 )

n

| ? A i | 删去右边第三个和式起的所有
i ?1

和式得到.
2

采用这种办法,我们可以从容斥公式得到另外一些组合不等式,只是要注意这些不等式 的方向的变化. 3.利用抽屉原则 由于抽世原则的结论本身就是组合不等式关系,所以我们利用抽屉原则,巧妙构造抽屉 的方法证明组合不等式. 4.利用组合分析 在复杂的组合计数问题、离散极值问题等问题中,会出现一些组合不等式,这时可运用 组合分析方法证明之.

赛题精讲
n

例 1 证明: ? C 2 n ? 2
k k ?0 n

2 n ?1

?

( 2 n )! 2 ? n! n!
2n 2n

【分析】 把 ? C 2 n 变形为
k k ?0 n 2n

?

2n

C 2n ?
k

k ?0

k ? n ?1

?

C 2 n , 而对于

k

k ? n ?1

?C

k 2n

,变换求和指标.

【证明】 ? C 2 n ? ? C 2 n ?
k k k ?0 k ?0

k ? n ?1

?C
n

2n

k 2n

? 2

2n

?

k ? n ?1

?C
n

2n

k 2n

, 对于和式

k ? n ?1

?C

2n

k 2n

,令 j ? 2n ? k ,



k ? n ?1

?

2n

C 2n ?
k

?
n

n ?1

j?0

C 2n ?? C 2n ? C 2n ?? C 2n ? C 2n .
j j n k n j?0 k ?0

所以 ? C 2 n ? 2
k k ?0 n

n

2n

?

?C
k ?0 n

k 2n

? C 2n .
n



2? C 2n ? 2
k k ?0

2n

? C 2 n ,从而有

?C
k ?0

n

k 2n

? 2

2 n ?1

?

( 2 n )! 2 ? n! n!
Cn ?
0

.
1 m ?3
1

例 2 求证: 证明 设 an ?

1 m ?1

1 m ? 2
0

Cn ?
1

C n ? ? ? ( ? 1)
2

n

1 m ? n ?1

Cn ?
n

1 ( m ? n ? 1) C m ? n
n

, 其中 n ? N .

1 m ?1

Cn ?

1 m?2

Cn ?

1 m?3
3

C n ? ? ? ( ? 1)
2

n

1 m ? n ?1

C n ,则由基本

n

?1 恒等式 C nr ? C nr ?1 ? C nr ?1 及 C nr ?1 ?

r n

Cn 得
r

an ?

1 m ?1

Cn ?
0

1 m ? 2

( C n ?1 ? C n ?1 ) ?
1 0

1 m ?3

( C n ?1 ? C n ?1 ) ? ? ?
2 1

( ? 1)

n ?1

m ? n

( C n ?1 ? C n ? 2 ) ?

n ?1

n?2

( ? 1)

n ?1

m ? n ?1

C n ?1 .

n ?1

故 a n ? a n ?1 ? 所以 a n ? ? 而 a1 ?

m ?1 n n

a n ,即 a n ? a n ?1 ? n!

m ?1 n

a n ? a n ?1 . a n?2 ? ?

n ( n ? 1) ( m ? n ? 1)( m ? n ) a1 , ,

m ? n ?1

( m ? n ? 1)( m ? n ) ? ( m ? 3 ) 1 ? 1 m ? 2 ? 1

m ?1

( m ? 2 )( m ? 1) n!

从而有 a n ?

( m ? n ? 1)( m ? n ) ? ( m ? 2 )( m ? 1)

?

1 ( m ? n ? 1) C m ? n
n

.

【说明】注意到 an 中各项的系数均与 n 无关,且符号正负相同,由此想到 an 与 an-1 之间必定存在着某些联系,且是递推关系. 例 3 求证: ? ( ? 1) ? 2
k k ?0 n 2n?2k

C 2 n ? k ?1 ? n ? 1 .
k

1 【分析】考虑到恒等式 C 2kn ? k ?1 ? C 2kn ? k ? C 2kn?? k ,仿例 2 解决.

【证明】令 a n ?

? ( ? 1)
k ?0

n

k

?2

2n?2k

? C 2 n ? k ?1 ,
k

1 因为, C 2kn ? k ?1 ? C 2kn ? k ? C 2kn?? k ,

所以 a n ? 2 ?2 ?

2n

?

? ( ? 1)
k ?1 n k

n

k

?2

2n?2k

C 2 n ? k ?1
k k ?1

k

2n

?

? ( ? 1)
k ?1 k

?2

2n?2k

( C 2 n ? k ?C 2 n ? k )
n k 2n?2k k ?1

? ( ? 1)
k ?0

n

?2

2n?2k

C 2 n ? k ? ? ( ? 1) ? 2
k k ?1

C 2n?k .

令 r ? k ? 1, 则

? ( ? 1)
k ?1

n

k

?2

2n?2k

C 2n?k ?

k ?1

? ( ? 1)
r?0 n ?1 r?0

n ?1

r ?1

?2
r

2 ( n ?1) ? 2 r

C 2 ( n ?1) ? r ?1
r

r

? ?

? ( ? 1)

2

2 ( n ?1) ? 2 r

C 2 ( n ?1) ? r ? 1 ? ? a n ?1 .

4

令 ? ( ? 1) ? 2
k k ?0

n

2n?2k

C 2 n ? k ? b n , 则 b n ? a n ? a n ?1
k



又 bn ? 2 ? 2

2n

? ?

? ( ? 1)
k ?1

n ?1

k

?2 ?2
j

2n?2k

C 2 n ? k ? ( ? 1)
k k

n

2n

? ( ? 1)
k ?1 n ?1 j?0

n ?1

k

2n?2k

( C 2 n ? k ? 1 ? C 2 n ? k ? 1 ) ? ( ? 1)
j

k ?1

n

? 4 a n ?1 ?

? ( ? 1)

?2

2 ( n ?1 ) ? 2 j

C 2 ( n ?1 ) ? j

? 4 a n ?1 ? b n ?1 .

于是由①式得 b n ?1 ? a n ?1 ? a n ? 2 , 从而推知 a n ? a n ?1 ? 4 a n ?1 ? a n ?1 ? a n ? 2 , 即 a n ? a n ? 2 ? 2 a n ?1 . 这说明{an}为等差数列,而 a0=1,a1=2,故公差 d=1,且 an=n+1 . 【说明】此题运用变换求和指标的方法,找出了 an,an-1,an-2 之间的线性关系式,再由 初 始条件求得 an.这种利用递推关系求组合数的方法, 在解决较复杂的计算或证明组事恒等式时 经常用到. 例 11:设 D 1 ? { A1 , A 2 , ? , A n }, D 2 ? { B 1 , B 2 , ? , B n } 是集合 M 的两个划分,又对任何 两个不变的子集 A i , B j (1 ? i , j ? n ) 有 | A i ? B j |? n , 求证: | M |? 立? 【证明】令 k ? min{| A i |, | B j |,1 ? i , j ? n} ,不妨设 | A i |? k , 因 B 1 , B 2 , ? , B n 两两不 交,故 B 1 , B 2 , ? , B n 中至多有 k 个 B j , 使 A1 ? B j ?
A1 ? B j ?
, j ? 1, 2 , ? , m , n ? k .
m

1 2

n 并说明等号能否成
2

.设

由 k 的选取知 | B j |? k ( j ? 1, 2 , ? m ), 从而 | ? B j |? mk .
j ?1

又因 故 即 所以

A1 ? B j ?

, i ? m ? 1, ? , n .

| A1 | ? | B i |? | A1 ? B i |? n , | B i |? n ? k .
n m j n j

| M |? | ? B
j ?1

|? | ? B
j ?1

|?|

?

B

j

|? mk ? ( n ? m )( n ? k )

j ? m ?1

5

? n ( n ? k ) ? m ( n ? 2 k ).

若k ?

n 2

, 因m ? k,故
n
2

| M |? n ( n ? k ) ? m ( n ? 2 k ) ? n ( n ? k ) ? k ( n ? 2 k ) ? 2 (

) ? 2(

n 2

? k)

2

?

n

2

.

2

2

若k ?

n 2

, 则 | A i |?
n
2

n 2

n

( i ? 1, 2 , ? , n ), 从而

| M |? | ? A i |?
i ?1

?

n

| Ai | ?

n

2

.

i ?1

2

下面说明 | M

|?

是可以取到的.显然这时 n 为偶数,取 n ? 4 , 则 | M |? 8 ,令

2

M ? {1, 2 ,3, 4 ,5 , 6 , 7 ,8}, 易验证 M 的两个划分.

D1={{1,2}{3,4}{5,6}{7,8}}, D2={{1,2}{3,5}{4,6}{7,8}}, 满足题目条件. 例 12:设 n 是正整数,我们说集合{1,2,?,2 n }的一个排列( x 1 , x 2 , ? x 2 n )具 有性质 P,是指在{1,2,?,2 n -1}当中至少有一个 i ,使得 | x i ? x i ?1 |? n . 求证,对于任 何 n ,具有性质 P 的排列比不具有性质 P 的排列的个数多. (1989,第 30 届 IMO 试题 6) 【证明】设 A 为不具有性质 P 的排列的集合,B 为具有性质 P 的排列的集合,显然
| A | ? | B |? ( 2 n )!. 为了证明 | A |? | B | ,只要得到 | B |?

1 2

( 2 n )! 就够了.使作容斥原理.

设 ( x 1 , x 2 , ? , x 2 n ) 中 , k 与 k ? n 相 邻 的 排 列 的 集 合 为 A k , k ? 1, 2 , ? , n . 则
| A k |? 2 x ( 2 n ? 1)! , | A k ? A j |? 2 x ( 2 n ? 2 )! ,1 ? k ? j ? n , 由容斥原理得
2

| B |?

?|A
k ?1

n

k

|?

1? k ? j ? n

?|A

k

? A j | ? n ? 2 ? ( 2 n ? 1)! ? C n ? 4 ? ( 2 n ? 2 )!
2

= ( 2 n )!? 2 n ( n ? 1) ? ( 2 n ? 2 )! ? 2 n ? n ? ( 2 n ? 2 )! ? 2 n ?

2n ? 1 2

? ( 2 n ? 2 )! ?

1 2

( 2 n )!

例 13:平面上给定 n 个点,其中任何三点不共线,任意地用线段连接某些点(这些线段 称为边) 则确保图形中出现以给定点为顶点的 m ( m ? n ) 阶完全图的条件是图形中的边的条 , 数
x ? C n ( C m ? 1) ? 1
m 2

C n?2

m?2

.

6

【证明】构造抽屉:每个抽屉里有 m 个相异点,共可得 C nm 个抽屉,又由于同一条边会
2 在 C nm??22 个抽屉里出现,根据抽屉原则知,当 x ? C nm??22 ? C nm ( C m ? 1) ? 1 时,才能确保有一个

2 2 抽屉里有 C m 条边,而这 C m 条边恰好与其中不共线的相异 m 点构成一个 m 阶完全图.

这就是说,确保图形中出现 m 阶完全图的条件是其中边的条数 x 【评述】 “完全图” ,是图论中的基本概念.(此处从略)

?

C n ( C m ? 1) ? 1
m 2

C n?2

m?2

.

2 2 2 例 14:设 x 1 , x 2 , ? , x n 为实数,满足 x 12 ? x 2 ? x 3 ? ? ? x n ? 1, 求证:对于每一整数

k ? 2 ,存在不全为零的整数 a 1 , a 2 , ? , a n , 使得 | a i |? k ? 1( i ? 1, 2 ,3, ? , n ), 并且

(1987 年第 28 届 IMO 试题 3)
| a 1 x 1 ? a 2 x 2 ? ? ? a n x n |? ( k ? 1) n k
n

?1

.

【证】由柯西不等式得
(| x 1 | ? | x 2 | ? ? ? | x n |)
2

? (1 ? 1 ? ? ? 1 )( x 1 ? x 2 ? x 3 ? ? ? x n ).
2 2 2 2 2 2 2

即 | x 1 | ? | x 2 | ? ? ? | x n |?

n.

所以,当 0 ? a i ? k ? 1 时,有
a 1 | x 1 | ? a 2 | x 2 | ? ? ? a n | x n |? ( k ? 1)(| x 1 | ? | x 2 | ? ? ? | x n |) ? ( k ? 1) n .
( k ? 1) n k
2

把区间[0, ( k ? 1) n ]等分成 k n ? 1 个小区间,每个小区间的长度 个 a i 能取 k 个整数,因此 a 1 | x 1 | ? a 2 | x 2 | ? ? ? a n | x n |

?1

,由于每

共有 k n 个正数,由抽屉原则知必有二数会落在同一小区间内,设它们分别是

? a? | x
i i ?1

n

i

| 与 ? a i?? | x i |,
i ?1

n

因此有

? ( a ? ? a ??) | x
i i i ?1

n

i

|?

( k ? 1) n k
2

?1

.



很明显,我们有

| a i? ? a i?? |? k ? 1, i ? 1, 2 , ? , n .

现在取 a i ? ?

? a i? ? a i??, 如果 x i ? 0 , ? a ?? ? a i? , 如果 x i ? 0 .

7

这里 i ? 1, 2 , ? , n , 于是①可表示为 | ? a i x i | ?
i ?1

n

( k ? 1) n k
n

?1

. 这里 a i 为整数,适合

| a i |? k ? 1, i ? 1, 2 , ? , n .

例 15:设 A 是一个有 n 个元素的集合,A 的 m 个子集 A1 , A 2 , ? , A m 两两互不包含,试 证: (1) ?
m

1 Cn
| Ai |

i ?1

? 1; (2) ? C n
i ?1

m

| Ai |

? m .
2

其中 | A i | 表示 A i 所含元素的个数, C n 表示 n 个不同元素取 | A i | 个的组合数. (1993 年,全国高中数学联赛二试第二大题) 【分析】若(1)式已证,由柯西不等式立即可得(2)式,因此,关键是证(1)式, 又据组合公式知, (1)式等价于

| Ai |

?|A
i ?1

n

i

|! (n ? | A i |)! ? n !.



所以我们用组合的方法来证明不等式①.

【证明】 (1)对于 A 的子集 A i ? { x 1 , x 2 , ? , x | A | }, 我们取补集 A i ? { y 1 , y 2 , ? , y n ? | A | },
i

i

并取 A i 的元素在前, A i 元素在后,作排列
x 1 , x 2 , ? , x | A i | , y 1 , y 2 , ? , y n ? | Ai | .

② 这样的排列共有 | A i | ( n ? | A i |)! 个.

显然,②中每一个排列,也是 A 中的一个排列,若 j ? i 时,A j 对应的排列与 A i 对庆的排列 互不相同,则 A1 , A 2 , ? , A m 所对应的排列总数便不会超过 A 中排列的总数 n ! , 现假设 A j 中 对应的某一排列 x 1 , x 2 , ? , x | A | , y 1 , y 2 , ? , y n ? | A | .
j j

?

?

?

?

?

?



与 A i( j ? i ) 中对应的某一排列②相同 (指出现的元素及元素位置都相同) 则当 | A j |? | A i | , 时, A j ? A i ;当 | A j |? | A i | 时, A j ? A i ,这都与 A1 , A 2 , ? , A m 两两互不包含,矛盾. 由于 A1 , A 2 , ? , A m 对应的排列对②互不相同,而 A 中 n 个元素的全排列有 n !个,故得

?

n

| A i |! (n ? | A i |)! ? n !.

i ?1

即?

n

1 Cn
| Ai |

? 1.

i ?1

8

(2)由上证及柯西不等式,有 ? C n| A | ? ( ? C n| A | )( ?
i i

m

m

m

1 Cn
| Ai |

i ?1

i ?1

i ?1

) ? ( ? 1)
i ?1

m

2

?m .
2

【评述】本题取自著名的 Sperner 定理: 设 Z 为 n 元素, A1 , A 2 , ? , A m 为 Z 的子集,互不包含,则 m 的最大值为 C n 2 . 例 16:设 S={0,1,2,?,N2-1},A 是 S 的一个 N 元子集.证明存在 S 的一个 N 元子 集 B,使得集合 A+B={ a ? b | a ? A , b ? B } 中的元素模 N2 的余数的数目不少于 S 中元素的一 半. (第 40 届 IMO 预选题) 【证明】设|X|为子集 X ? S 中元素的个数;又为 S ? X ,是 X 的补集;C i 是 a ? i 对 k 个参赛选手有相同的判决,证明
k a ? b ?1 2b .
[ n ]

(1998 年第 39 届 IMO 试题二) 【解】设裁判 B i ( i ? 1, 2 , ? , b ) 对参赛选手 A j ( j ? 1, 2 , ? , b ) 的判决为 d ij ,其中
?0, d ij ? ? ?1, 若 " 通过 " , 若 " 不通过 ".

则( d i , d i , ? , d i )中 B i 对 a 个参赛选手判决的记录 ( i ? 1, 2 , ? , b ) ,它是一个长度为
1 2 a

a 的(0—1)序列.

我们来考虑这 b 个序列中每两个序列的相同的项的总数 M. 一方面,由已知条件每两个序列的相同的项不超过 k 个,故
M ? Cb ? k ?
2

1 2

b ( b ? 1) k .



另一方面,设 A j 得到 b 0 个 0(通过) b 1 个 1(不通过) , ,即( d i , d i , ? , d i )的第 i 个
1 2 a

分量中 b 0 个 0, b 1 个 1,则 b 0 + b 1 = b. 由这个分量产生的序列的相同的项有
C b 0 ? C b1 ?
2 2

1 2 1 2 1 2

b 0 ( b 0 ? 1) ?
2 2

1 2

b1 ( b1 ? 1) 1 2 [( b 0 ? b1 ) ? b ]
2 2

? ?

[( b 0 ? b1 ) ? ( b 0 ? b1 )] ?
2

[( b 0 ? b1 ) ? b ? 2 b 0 b1 )] ?

1 2

( b ? b ? 2 b 0 b1 ).
2

但 b 0 ? b1 ? b 且 b 为奇数 ( b ? 3 ) ,因此
9

b 0 b1 ?

1 4

( b ? 1) ? ( b ? 1). 1 2 ( b ? 1) ?
2

故 C b2 ? C b2 ?
0 1

[ b ( b ? 1) ? 1 2

1 2

( b ? 1)( b ? 1)] 1 4 ( b ? 1) .
2

= 从而 M ? a ?

1 2 1

( b ? 1) ?

( b ? 1) .
? a ( b ? 1) ?
2


1 2 b ( b ? 1) k ,

综合①、②得

4 1
4



k a

?

b ?1 2b

.

10


赞助商链接

更多相关文章:
大学生数学竞赛辅导材料
大学生数学竞赛辅导材料 - 收集了近几年的竞赛真题和部分省市的竞赛题,对提高大学生的数学解题能力有帮助。
初二数学竞赛辅导课程1
初二数学竞赛辅导课程1 - 初二数学竞赛辅导课程 1.货车和轿车分别从甲、乙两地同时出发,沿同一公路相向而行.轿车出发 2.4h 后休息,直至与货车相遇 后,以原速度...
-初中数学竞赛辅导资料20
-初中数学竞赛辅导资料20 - 初中数学竞赛辅导资料 20 第二十课乘法公式的应用 例 1 计算: (1) (1+2) (1+22) (1+24)…(1+232)+1; (2) (19924+...
人教版七年级数学下册奥赛辅导资料
人教版七年级数学下册奥赛辅导资料_数学_初中教育_教育专区。七年级下册培优班讲义第 12 讲与相交有关概念及平行线的判定 考点·方法·破译 1.了解在平面内,两...
【初中数学竞赛辅导】2018届人教版初中数学第22章《[x]...
【初中数学竞赛辅导】2018届人教版初中数学第22章《[x]与{x}》竞赛专题复习含答案 - 2018 年初中数学竞赛辅导专题讲义 第 22 章 ? x? 与 ? x? 22.1.1...
高一数学竞赛辅导计划
高一数学竞赛辅导计划 - 高一数学竞赛辅导计划 辅导教师 陈伟 为了提升数学竞赛成绩,加强了竞赛辅导力度,使竞赛有的放矢,特作此计划: 一班级组建:以高一上期选拔的...
高中数学竞赛辅导讲座系列
高中数学竞赛辅导讲座系列 - 高中数学竞赛辅导讲座系列 高中数学竞赛基础知识 第一章 集合与简易逻辑 一、基础知识 定义 1 一般地,一组确定的、互异的、无序的...
初中数学竞赛辅导 几何变换(旋转)
初中数学竞赛辅导 几何变换(旋转)_初二数学_数学_初中教育_教育专区。初中数学竞赛辅导 几何变换(旋转) 第2 讲 几何变换——旋转典型例题 CE 为边在线段 AE 的...
全国初中数学竞赛辅导第二册
全国初中数学竞赛辅导第二册 - 全国初中数 学竞赛辅导 第二册 第一讲 因式分解(一) ......
高中数学竞赛辅导
高中数学竞赛辅导 - 唐江中学数学竞赛辅导 一. 填空题 1.设多项式 f ( x ) 满足:对于任意 x ? R ,都有 f 则 f ( x) 的 ( x ? 1 ) ?? f (...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图