数学奥赛辅导_第讲_组合恒等式、组合不等式.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） 【证】由柯西不等式得 即 所以，当时