数学奥赛辅导第九讲.doc

数学奥赛辅导第九讲
组合恒等式、组合不等式
知识、方法、技能
Ⅰ．组合恒等式
①

竞赛数学中的组合恒等式是以高中排列组合、二项式定理为基础，加以推广、补充而形成的一类组合问题.组合恒等式的证明要借助于高中常见的基础组合等式.例如
⑥
⑤
④
③
②

组合恒等式的证明方法有：
①恒等变形，变换求和指标；
②建立递推关系；
③数学归纳法；
④考虑组合意义；
⑤母函数.
Ⅱ．组合不等式
组事不等式以前我们见的不多，在其他一些书籍中组合不等式的著述也很少，但是近年来组合不等式的证明却出现在国内、国际大赛上.例如1993年中国高中数学联赛二试第二大题为：
设A是一个有n个元素的集合，A的m个子集A1，A2…，Am两两互不包含，试证：
（1）
（2）
其中|Ai|表示Ai所含元素的个数，表示n个不同元素取|Ai|的组合数.
再如1998年第39届国际数学奥林匹克竞赛中第二大试题为：
在某一次竞赛中，共有a个参赛选手与b个裁判，其中b≥3，且为奇数.每个裁判对每个选手的评分中只有“通过”或“不及格”两个等级，设k是满足条件的整数；任何两个裁判至多可对k个选手有完全相同的评分. 证明：

因此我们有必要研究组合不等式的证明方法.组合不等式的证明方法有：
1．在集合间建立单射，利用集合阶的不等关系
定理，设X和Y都是有限集，f为从X到Y的一个映射，
（1）若f为单射，则|X|≤|Y|；
（2）若f为满射，则|X|≥|Y|.
2．利用容斥原理
例如：设元素a属于集族{A1，A2，…，An}的k个不同集合，则在中a被计算了k次，当k≥2时，集合两两的交集共有个.由于
中至少少被计算了k－1次，这样我们得到下面的不等式：

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

赛题精讲

例1 证明：
【分析】 把，变换求和指标.
【证明】，则
所以
即 ，从而有
.
例2 求证：
证明 设，则由基本恒等式得

【说明】注意到an中各项的系数均与n无关，且符号正负相同，由此想到an与an－1之间必定存在着某些联系，且是递推关系.
例3 求证：
【分析】考虑到恒等式，仿例2解决.
【证明】令
因为，，

令 ①

于是由①式得.
这说明{an}为等差数列，而a0=1,a1=2，故公差d=1，且an=n+1 .
【说明】此题运用变换求和指标的方法，找出了an，an－1，an－2之间的线性关系式，再由 初始条件求得an.这种利用递推关系求组合数的方法，在解决较复杂的计算或证明组事恒等式时经常用到.
例11：设是集合M的两个划分，又对任何两个不变的子集有求证：并说明等号能否成立？

【证明】令，不妨设因两两不交，故中至多有个使 .设

由的选取知从而
又因
故
即
所以

若因故

若则 从而
下面说明是可以取到的.显然这时为偶数，取则，令
易验证M的两个划分.
D1={{1,2}{3,4}{5,6}{7,8}}, D2={{1,2}{3,5}{4,6}{7,8}},
满足题目条件.
例12：设是正整数，我们说集合{1，2，…，2}的一个排列（）具有性质P，是指在{1，2，…，2－1}当中至少有一个，使得求证，对于任何，具有性质P的排列比不具有性质P的排列的个数多.
（1989，第30届IMO试题6）
【证明】设A为不具有性质P的排列的集合，B为具有性质P的排列的集合，显然为了证明，只要得到就够了.使作容斥原理.
设()中,与相邻的排列的集合为则由容斥原理得

=
例13：平面上给定个点，其中任何三点不共线，任意地用线段连接某些点（这些线段称为边），则确保图形中出现以给定点为顶点的阶完全图的条件是图形中的边的条数

【证明】构造抽屉：每个抽屉里有个相异点，共可得个抽屉，又由于同一条边会在个抽屉里出现，根据抽屉原则知，当时，才能确保有一个抽屉里有条边，而这条边恰好与其中不共线的相异点构成一个阶完全图.
这就是说，确保图形中出现阶完全图的条件是其中边的条数
【评述】“完全图”，是图论中的基本概念.（此处从略）
例14：设为实数，满足求证：对于每一整数，存在不全为零的整数使得并且
（1987年第28届IMO试题3）

【证】由柯西不等式得

即
所以，当时，有

把区间[0，]等分成个小区间，每个小区间的长度，由于每个能取个整数，因此
共有个正数，由抽屉原则知必有二数会落在同一小区间内，设它们分别是
与 因此有 ①
很明显，我们有 现在取
这里于是①可表示为这里为整数，适合

例15：设A是一个有个元素的集合，A的个子集两两互不包含，试证：（1）（2）
其中表示所含元素的个数，表示个不同元素取个的组合数.
（1993年，全国高中数学联赛二试第二大题）
【分析】若（1）式已证，由柯西不等式立即可得（2）式，因此，关键是证（1）式，又据组合公式知，（1）式等价于
① 所以我们用组合的方法来证明不等式①.
【证明】（1）对于A的子集我们取补集并取的元素在前，元素在后，作排列
，. ② 这样的排列共有个.
显然,②中每一个排列,也是A中的一个排列,若时，对应的排列与对庆的排列互不相同，则所对应的排列总数便不会超过A中排列的总数现假设中对应的某一排列，. ③
与（）中对应的某一排列②相同（指出现的元素及元素位置都相同），则当时，；当时，，这都与两两互不包含，矛盾.
由于对应的排列对②互不相同，而A中个元素的全排列有！个，故得
即
（2）由上证及柯西不等式，有
【评述】本题取自著名的Sperner定理：
设Z为元素，为Z的子集，互不包含，则的最大值为.
例16：设S={0，1，2，…，N2－1}，A是S的一个N元子集.证明存在S的一个N元子集B,使得集合A+B={中的元素模N2的余数的数目不少于S中元素的一半. （第40届IMO预选题）
【证明】设|X|为子集中元素的个数；又为，是的补集；是对个参赛选手有相同的判决，证明
（1998年第39届IMO试题二）
【解】设裁判对参赛选手的判决为，其中

则（）中对个参赛选手判决的记录，它是一个长度为的（0—1）序列.
我们来考虑这个序列中每两个序列的相同的项的总数M.
一方面,由已知条件每两个序列的相同的项不超过个,故
①
另一方面，设得到个0（通过），个1（不通过），即（）的第个分量中个0，个1，则+=
由这个分量产生的序列的相同的项有

但且为奇数，因此

故
=
从而 ③
综合①、②得 即