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

高二数学竞赛班讲义 第四讲 组合不等式


高二数学竞赛班二试 第四讲

组合不等式(一)
班级 姓名

一、知识要点:
组合不等式问题是数学竞赛中的热点问题, 通常也是教学竞赛中难度很大的 问题, 同时也是针对学生思维考测的典型问题. 组合不等式问题的内容非常广泛, 涉及到代数、几何、数论等多个分支。组合不等式问题有:组合数不等式、组合 计数不等式、组合最值、组

合几何不等式、组合数论不等式等. 下面就从几个典型的组合不等式问题的研究,提高我们的思维能力.

二、经典例题
n n 例 1:对 n≥2,证明(1) 2 n ? C 2 n ? 4 n ; (2) C 2 n ?1 ? 4 n ?1
2 例 1:证明: (1)当 n=2 时, 2 2 ? 6 ? C 2?2 ? 4 2 不等式成立

k 设 2 k ? C 2 k ? 4 k 成立,则 n ? k ? 1 时
k k 1 k k 由 C 2 n ? C 2 k?? 2 ? 2C 2 k ?1 ? 2C 2 k ? 2 ? 2 k ? 2 k ?1 ? 2 n

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

2k ? 1 k k k C 2 k ? 2 ? 2C 2 k ? 4C 2 k ? 4 ? 4 k ? 4 k ?1 ? 4 n k ?1

知不等式成立
n 由归纳原理,对 n≥2 不等式 2 n ? C 2 n ? 4 n 恒成立

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

n ?1 1 2 n ?1 1 2 n ?1 k k n ?1 n ?2 ? ? C 2 n ?1 ? ? C 2 n ?1 ? 2C 2 n ?1 ? C 2 n ?1 2 2 k ?0 k ?0

1 例 2: S ? ? ,2,?,10?,A1 , A2 ,? , Ak 都是 S 的子集且满足 设 (1)Ai ? 5, i ? 1,2, ? , k ;

(2) Ai ? A j ? 2,1 ? i ? j ? k .求 k 的最大值. 例 2:解:设 k 有个子集满足题中条件(1)和(2) ,并设 i 属于这 k 子集中的 x i 个集合,i=1,2,…,10.若 i ? A j ,i ? Ak , j ? k ,则称 i 为一个重复数对.于 是由数 i 导致的重复数对有 C x2i 个.由 S 中的 10 个元素所导致的重复数对的总数
2 为 C x21 ? C x22 ? ? ? C x10 , x1 ? x 2 ? ? ? x10 ? 5k .

另一方面,每两个子集间至多有两个重复数对,所以 k 个子集之间至多有
1

2C k2 个得复数对.因而有
2 2 2 C x1 ? C x2 ? ? ? C x10 ? 2C k2



由柯西不等式有
1 ?x1 ?x1 ? 1? ? x2 ?x2 ? 1? ? ? ? x10 ?x10 ? 1?? 2 1 1 1 5 2 2 2 2 ? x12 ? x2 ? ? ? x10 ? ?x1 ? x2 ? ? ? x10 ? ? ? x12 ? x2 ? ? x10 ? ? k 2 2 2 2 1 ② ?5k ?2 ? 5 k ? 5 k ?k ? 2? ? 20 2 4 5 由①和②得到 ?k ? 2 ? ? k ? 1 ③ 4 由③解得 k ? 6 .这表明至多有 6 个子集. 构造:
2 2 2 C x1 ? C x2 ? ? ? C x10 ?

?

?

?1, 2,3, 4,5? , ?4,5,6,7,8? , ?7,8,9,1, 2? ,?9,10,1, 4, 6? , ?10, 2,3, 6, 7? , ?3,5,8,9,10?
例 3:设 P1 , P2 ,?, P2 n ?3 为平面上的 2n ? 3 个点,其中任何 3 点都不共线,任何 4 点都不共圆.过其中 3 点作圆,使其余 2n 个点在圆内和圆外各有 n 个点,这种 1 2 圆的个数为 K,求证 K ? C 2 n ?3 . ? 例 3:证明:首先证明对任意两点 Pi , Pj ,一定存在第 3 点 Pk ,使得过 Pi , Pj ,
Pk 3 点的圆满足题中的要求.为此,不妨设直线 Pi Pj 的上方的点数 m ? n ? 1 .因

为任何 3 点不共线,任何 4 点不共圆,故可将直线上方的 m 点按对线段 Pi Pj 的 张角从小到大排列为 Pk1 , Pk 2 ,… Pkm ,即有
0? ? ?Pi Pk1 Pj ? ?Pi Pk2 Pj ? ? ? ?Pi Pkm Pj ? 180 ?

由此可知,过 Pi , Pj , Pk 3 点的圆内的点数不多于 n.若两圆中有一圆内恰 有 n 个点, 则它就满足要求. 否则, 前者内部点数大于 n, 后者内部点数小于 n. 而 当顺次考察过 Pi , Pj , Pkh (h=1,2,…,m)3 点的圆时,圆内给定点的个数每次恰 减少 1 个.故知其中必有 1 个圆满足题中要求. 这样一来,对于 ?P1 , P2 ,?, P2 n ?3 ?中的任意两点都可以作出 1 个圆满足题中要 求.于是共可得到 C 22n ?3 个圆.但在这个计数过程中,每个圆可被计数 3 次,故 得

2

1 2 1 2 K ? C 2 n ?3 ? C 2 n ?3 . 3 ?

例 4:10 人到书店去买书,已知(1)每人都买了 3 种书; (2)任何两人所买的 书中, 都至少有一种相同. 问购买人数最多的一种书最少有几个人购买?说明理 由. 例 4:解:右图中,由正五边形的中心和两个相领顶点构成的三角形 共有 5 个, 由正五边形的 3 个不全相连的顶点构成的三角形也共有 5 个.不难看出,这 10 个三角形中的任何两个都至少有一个公共顶 点.将这些三角形的顶点号码组写出来并让 10 人所买的书号依次为 这 10 个三角形的顶点号码组: (123) , (134) , (145) , (156) , (162) , (245) , (356) , (426) , (523) , (634) . 显然,每种书都有人购买.故知所求的最小值示超过 5. 设所求的最小值为 4, 人共买了 n 种书且第 i 种书有 mi 人购买, 10 于是 mi ? 4 且 m1 ? m2 ? ? ? mn ? 30 .当两人买同一种书时,称之为一个“书对”.由已知,
2 每两人之间至少有 1 个书对, 于是至少共有 C10 ? 45 个书对. 另一方面, 由第 i 种
2 2 2 2 书形成的书对有 C mi 个,共有 C m1 ? C m2 ? ? ? C mn 个书对.从而有

2 2 2 C m1 ? C m2 ? ? ? C mn ? 45
2 2 因为 C 4 ? 6 , C 32 ? 3 , C 2 ? 1 ,故又有



2 2 2 2 2 C m1 ? C m2 ? ? ? C mn ? 7C 4 ? C 2 ? 43



由于①与②矛盾,故知所求的最小值为 5. 例 5:在 1980× 1981 的方格表的每个方格中都写有+1,-1 和 0 之一,且表中所 有数之和等于 0. 试证存在两行和两列,使得位于它们交点处的 4 个数之和为 0. 例 5:证明:若不然,则任何一个边在网格线上的矩形的 4 个角格中的 4 数之和 均不为零. (1) 考察数表中 0 的个数. 设表中 1981 列中 0 的个数依次为 k1 , k 2 ,?, k1981 . 因 为不能有两行两列之交的 4 个方格中同时为 0,故有

3

1981 i ?1

?C

2 ki

2 ? C1980 ? 990 ? 1979 .



2 C2 因为 C 45 ? 990 , 44 ? 946 , 故表中 0 的个数不超过 1980× 个. 45 1980× 1936,

故-1 的个数与+1 的个数都不少于 1980× 968. 若有某行中有 1015 个-1,则因有+1 最多的一行至少有 968 个+1,故必 有两个-1 与两个+1 同列,此与反证假设矛盾,故知每行中-1 的个数和+1 的个数均不超过 1014. 设第 i 行有 ni 个-1, mi 个+1,i ? 1,2,?,1980 .因为不能有两行两列之交的 4 格中的数之和为 0,故必有
1980 i ?1

?nm
i

i

2 ? C1981 ? 1981? 990 ,



其中 ? ni ? 1980 ? 968 , ? mi ? 1980 ? 968 ,ni ,mi ? 1014 ,i ? 1,2,?,1980 .
i ?1 i ?1

1980

1980

由排序不等式知在②式中可设 ? ni ? 递增而 ?mi ? 递减且在容许条件下前面的
mi 尽可能大,前面的 ni 尽可能地小.从而有 ? ni mi ? 1980 ?1014
i ?1 1980



③与②矛盾,这就完成了反证法的证明. 例 6:在某项竞赛中,共有 a 名参赛选手与 b 位裁判员,其中 b ? 3 为奇数,每位 裁判对每名选手的评分都只有“合格”与“不合格”两种,设 k ? N ,任何两位裁判 k b ?1 至多可对 k 名选手有完全相同的评分,求证: ? . a 2b 例 6:证明:当两位裁判对一名选手的评分相同时,称之为一个“相同评分对”下 面对相同评分对的个数进行换序求和. 一方面,每名运动员都获得 b 位裁判的各一个评分.设第 i 名选手获得 xi 个 合格与 b ? xi 个不合格, 于是由第 i 名选手产生的相同评分对的个数为 C x2i ? C b2? xi ,
i ? 1,2,?, a .从而所有相同评分对的个数为

? ?C
a i ?1

2 xi

2 2 ? Cb2? xi ? a C m?1 ? C m ?

? ?

?

a ?m?m ? 1? ? m?m ? 1?? ? am2 , 2

其中 b ? 2m ? 1, m ? N . 另一方面, 任何两位裁判所产生的相同评分对至多 k 对,故所有相同评分对

4

的个数不超过 k Cb2 .
2 结合起来,得到 kCb2 ? ? C xi ? Cb2? xi ? am2 , i ?1 a

?

?

1 k ? b?b ? 1? ? am2 , 2

kb ? am ? a ?

b ?1 , 2

k b ?1 . ? a 2b

例 7:n 个平面最多可以将空间分成多少个部分区域? 例 7:解:为求这个最大值,我们先证如下的引理,平面上的 n 条直线,最多可
2 以把平面分成 C n ?1 ? 1 个部分. 显然,当这 n 条直线两两相交且任何三条都不共点时,把平面分成的部分最多.

设平面被 k 条直线分成的部分数的最大值为 mk ,然后加入第 k ? 1 条直线, 它与前 k 条直线中的每一条都相交,共得到 k 个交点,这 k 个点将第 k ? 1 条直线 分成 k ? 1 段,其中每一段都把它所穿过的区域一分为二.故知由于第 k ? 1 条直 线的加入而新增加的小区域数与第 k ? 1 .这样,我们得到递推公式
mk ?1 ? mk ? k ? 1

由此递推即得 mn ? mn?1 ? n ? n ? n ? 1 ? mn?2
1 ? n ? n ? 1 ? ? ? 2 ? m1 ? n ? n ? 1 ? ? ? 2 ? 1 ? 1 ? C n?1 ? 1

这就完成了引理的证明,下面利用引理来解原题. 设空间中的 k 个平面最多能把空间分成 vk 个区域, 然后考察当第 k ? 1 个平面 加入时,新增加的小区域的个数.这时,第 k ? 1 个平面与前 k 个平面中的每个平 面都交于 1 条直线,在第 k ? 1 号平面上共得到 k 条直线.由引理知,这 k 条直线 最多能把平面分成 C k2?1 ? 1 个部分,其中每部分都把它所穿过的区域一分为二, 故得递推关系式 vk ?1 ? vk ? mk 由此递推即得
3 2 2 2 ? n ? mn?1 ? mn?2 ? ? ? m1 ? ?1 ? C n ? C n?1 ? ? ? C 2 ? ?n ? 1? ? 2 ? C n ?1 ? n ? 1 , 3 即空间中的 n 个平面最多可以把空间分成 C n ?1 ? n ? 1 个部分,这个最大值当

任何 3 个平面都共点,任何四个平面都不共点时取得.
1 例 8:设 S ? ? ,2,3,4?, n 项的数列 a1 , a 2 ,?, a n 具有下列性质:对于 S 的任何一个非

空子集 B (集 B 的元数记为 B ) 在该数列中都有相邻的 B 项恰好组成集合 B. , 求
5

项数 n 的最小值. 例:解:对于每个 i ? S ,它都可以与 S 中的另外 3 个元素各组成一个二元子集, 即共有 3 个含 i 的二元子集,若 i 在数列中仅出现 1 次,则含 i 的相邻两项组至多 两个,所以 i 在数列中至少出现两次,由于 1,2,3,4 都至少出现两次,故数列 至少有 8 项,即 n ? 8 . 另一方面,容易验证,8 项数列 3,1,2,3,4,1,2,4 满足题中条件. 综上可知,数列项数 n 的最小值为 8. 例 9: A 是一个 n 元集合, 的 m 个子集 A1 , A2 ,?, Am 两两互不包含, 设 A 试证 (1)

?C
i ?1

m

1
Ai n

A ? 1; (2) ? Cn i ? m 2 , i ?1

m

其中 Ai 表示 Ai 所含元素的个数 例 9:证:按定义有
1 Cn i
A

?

Ai !? n ? Ai ? ! n!



由此可见,为证(1) ,只须证明等价不等式

? A !?n ? A ?!? n!.
m i ?1 i i



对于每个 Ai , 利用 Ai 构造集 A 中的 n 个元素的排列如下: Ai 个位置是 Ai 前 中的所有元素的一个排列, ?n ? Ai ?个位置是 Ai 的补集 Ai 中的所有元素的一个 后 排列,这样的排列称之为从属于 Ai 的排列,按乘法定理知,这样的排列数是
Ai !?n ? Ai ?! .

当 j ? i 时,不妨设 A j ? Ai ,如果有一个 A 的元素的排列既从属于 Ai ,又 从属于 A j ,则其中的前 Ai 个元素都属于 Ai ,前 A j 个元素都属于 Ai ,从而有
Ai ? A j ,此与已知矛盾,这表明从属于不同子集的任何两个排列互不相同,因

为 A 中 n 个元素的所有排列总数为 n! ,故得不等式①. 对于任何 m 个正数 a1 , a 2, ? a m ,由柯西不等式有

6

m ? m 1 ? ?? ? ? ?? 1 ? m ? ? ai ? a ? i ?1 a ? ? i ?1 i i ? ? 2

2

?? m ? ?? ? ai ? . ? ?? i ?1 ?



在②中令 a i ? C n

Ai

, i ? 1,2,?, m ,由已证的不等式(1)即得

? m 1 m2 ? ? ? A ? i ?1 C i n ?

m ?? m ?? ? Cn Ai ? ? ? Cn Ai ? ?? i ?1 ? i ?1 ?

例 10:设 D1 ? { A1 , A2 ,?, An }, D2 ? {B1 , B2 ,?, Bn } 是集合 M 的两个划分,又对任何两 个不交的子集 Ai , B j (1 ? i, j ? n) 有 | Ai ? B j |? n, 求证: | M |? 立? 例 10: 【证明】令 k ? min{| Ai |, | B j |,1 ? i, j ? n} ,不妨设 | A1 |? k , 因 B1 , B2 , ? , Bn 两两 不交,故 B1 , B2 , ? , Bn 中至多有 k 个 B j , 使 A1 ? B j ? ? ,设

1 2 n 并说明等号能否成 2

A1 ? B j ? ? , j ? 1, 2, ???, m, m ? k
由 k 的选取知 | B j |? k ( j ? 1,2, ? m), 从而 | 又因 故 即 所以

?B
j ?1

m

j

|? mk .

A1 ? B j ?

, i ? m ? 1,?, n.

| A1 | ? | Bi |?| A1 ? Bi |? n,
| Bi |? n ? k .
| M |?| ? B j |?| ? B j | ? |
j ?1 j ?1 n m j ? m ?1

?B

n

j

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

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

n , 因 m ? k, 故 2
n2 n n2 ) ? 2( ? k ) 2 ? . 2 2 2

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

n n n n n2 , 则 | Ai |? (i ? 1,2,?, n), 从而 | M |?| ? Ai |? ? | Ai | ? . 2 2 2 i ?1 i ?1
2

下面说明 | M |? n 是可以取到的.显然这时 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}},

7

满足题目条件. 例 11:设 n 是正整数,我们说集合{1,2,?,2 n }的一个排列( x1 , x 2 ,? x 2 n )具有性质 P, 是指在{1,2,?,2 n }当中至少有一个 i ,使得 | xi ? xi ?1 |? n 。求证,对于任何 n ,具有 性质 P 的排列比不具有性质 P 的排列的个数多. (1989,第 30 届 IMO 试题 6) 例 11: 【证明】设 A 为不具有性质 P 的排列的集合,B 为具有性质 P 的排列的集合,显然

| A | ? | B |? (2n)!. 为了证明 | A |?| B | ,只要得到 | B |?

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

设 ( x1 , x2 ,?, x2 n ) 中 , k 与 k ? n 相 邻 的 排 列 的 集 合 为 Ak , k ? 1,2, ?, n. 则

| Ak |? 2 ? (2n ? 1)!, | Ak ? Aj |? 22 ? (2n ? 2)!,1 ? k ? j ? n ,由容斥原理得
| B |? ? | Ak | ?
k ?1 n 1? k ? j ? n

?

2 | Ak ? Aj | ? n ? 2 ? (2n ? 1)!? Cn ? 4 ? (2n ? 2)!

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

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

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

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

m?2

一个抽屉里有 C m 条边,而这 C m 条边恰好与其中不共线的相异 m 点构成一个 m 阶完全图.
m 2 这就是说,确保图形中出现 m 阶完全图的条件是其中边的条数 x ? C n (C m ? 1) ? 1 . m C n ??22

2

2

【评述】 “完全图” ,是图论中的基本概念.(此处从略)

8


相关文章:
高二数学竞赛班讲义 第四讲 组合不等式
高二数学竞赛班二试 第四讲 组合不等式(一)班级 姓名 一、知识要点:组合不等式问题是数学竞赛中的热点问题, 通常也是教学竞赛中难度很大的 问题, 同时也是针对...
高二数学竞赛班讲义 组合
高二数学竞赛班讲义 组合_高二数学_数学_高中教育_教育专区。高二数学竞赛讲义...第五讲 柯西不等式 12页 5下载券 高二数学竞赛班二试讲义... 9页 5下载...
高二数学竞赛班讲义 第五讲 组合恒等式
高二数学竞赛班讲义 第四讲... 暂无评价 8页 免费 数学竞赛辅导讲座:组合恒....的展开式中,常数项即为所求证等式的左端。不妨设 x ? 0 ,将原 ? x? n...
高二数学竞赛班二试平面几何讲义.第十讲 几何不等式doc3
高二数学竞赛班二试平面几何讲义.第十讲 几何不等式doc3_学科竞赛_高中教育_教育专区。高二数学竞赛班二试平面几何讲义第十讲 几何不等式班级 姓名 一、知识要点:...
第四讲:基本不等式(两节)
第四讲:基本不等式(两节)_数学_高中教育_教育专区。基本不等式 一、基本不等式:⒈定理 1: 若a、b ? R,则a 2 ? b 2 ? 2ab ,当且仅当 a ? b 时...
第四讲 基本不等式习题
第四讲 基本不等式习题_高二数学_数学_高中教育_教育专区。第四讲 基本不等式 2015.08.04 1. 若 a, b ? R,且 ab ? 0 ,则下列不等式中,恒成立的是(...
【暑假预习】2015年初高中数学衔接教材讲义:第四讲 不等式
【暑假预习】2015年初高中数学衔接教材讲义:第四讲 不等式_数学_高中教育_教育专区。第四讲 不 等式 初中阶段已经学习了一元一次不等式和一元一次不等式组的解法...
高中数学竞赛第四讲
高中数学竞赛平面几何讲座... 4页 10财富值 高中数学竞赛辅导讲义第四... 12...并能利用这些性质快捷地比较两个数值的 大小或解有关不等式.具体解题时,若绘...
高中数学奥赛讲义:竞赛中常用的重要不等式
高中数学奥赛讲义:竞赛中常用的重要不等式_学科竞赛_...而且,不论是几何、数论、函数或组合数 学中的许多...竞赛中常用的重要不等式【内容综述】 本讲重点介绍...
高中数学总复习专题一第四讲不等式
高中数学总复习专题一第四讲不等式 隐藏>> 第四讲①若 a b ? 0 , b ? a ,则 1 a 不等式 一、选择题 1.a,b,c∈R,下列结论成立的是 A.a>b,则...
更多相关标签:
一元一次不等式讲义 | 不等式讲义 | 基本不等式讲义 | 高二不等式 | 高二数学不等式知识点 | 高中数学竞赛不等式 | 高二数学必修5不等式 | 高二数学不等式 |