數(shù)學(xué)奧賽輔導(dǎo)第九講

1、數(shù)學(xué)奧賽輔導(dǎo)第九講 組合恒等式、組合不等式知識(shí)、方法、技能組合恒等式競(jìng)賽數(shù)學(xué)中的組合恒等式是以高中排列組合、二項(xiàng)式定理為基礎(chǔ)，加以推廣、補(bǔ)充而形成的一類組合問題.組合恒等式的證明要借助于高中常見的基礎(chǔ)組合等式.例如組合恒等式的證明方法有：恒等變形，變換求和指標(biāo)；建立遞推關(guān)系；數(shù)學(xué)歸納法；考慮組合意義；母函數(shù).組合不等式組事不等式以前我們見的不多，在其他一些書籍中組合不等式的著述也很少，但是近年來組合不等式的證明卻出現(xiàn)在國(guó)內(nèi)、國(guó)際大賽上.例如1993年中國(guó)高中數(shù)學(xué)聯(lián)賽二試第二大題為：設(shè)A是一個(gè)有n個(gè)元素的集合，A的m個(gè)子集A1，A2，Am兩兩互不包含，試證：（1）（2）其中|Ai|表示Ai所含元

2、素的個(gè)數(shù)，表示n個(gè)不同元素取|Ai|的組合數(shù).再如1998年第39屆國(guó)際數(shù)學(xué)奧林匹克競(jìng)賽中第二大試題為：在某一次競(jìng)賽中，共有a個(gè)參賽選手與b個(gè)裁判，其中b3，且為奇數(shù).每個(gè)裁判對(duì)每個(gè)選手的評(píng)分中只有“通過”或“不及格”兩個(gè)等級(jí)，設(shè)k是滿足條件的整數(shù)；任何兩個(gè)裁判至多可對(duì)k個(gè)選手有完全相同的評(píng)分. 證明：因此我們有必要研究組合不等式的證明方法.組合不等式的證明方法有：1在集合間建立單射，利用集合階的不等關(guān)系定理，設(shè)X和Y都是有限集，f為從X到Y(jié)的一個(gè)映射，（1）若f為單射，則|X|Y|；（2）若f為滿射，則|X|Y|.2利用容斥原理例如：設(shè)元素a屬于集族A1，A2，An的k個(gè)不同集合，則在中a被

3、計(jì)算了k次，當(dāng)k2時(shí)，集合兩兩的交集共有個(gè).由于中至少少被計(jì)算了k1次，這樣我們得到下面的不等式：組合不等式（*）可由容斥公式：刪去右邊第三個(gè)和式起的所有和式得到.采用這種辦法，我們可以從容斥公式得到另外一些組合不等式，只是要注意這些不等式的方向的變化.3利用抽屜原則由于抽世原則的結(jié)論本身就是組合不等式關(guān)系，所以我們利用抽屜原則，巧妙構(gòu)造抽屜的方法證明組合不等式.4利用組合分析在復(fù)雜的組合計(jì)數(shù)問題、離散極值問題等問題中，會(huì)出現(xiàn)一些組合不等式，這時(shí)可運(yùn)用組合分析方法證明之.賽題精講例1 證明：【分析】 把，變換求和指標(biāo).【證明】，則所以即 ，從而有.例2 求證：證明 設(shè)，則由基本恒等式得 【說明

4、】注意到an中各項(xiàng)的系數(shù)均與n無關(guān)，且符號(hào)正負(fù)相同，由此想到an與an1之間必定存在著某些聯(lián)系，且是遞推關(guān)系.例3 求證：【分析】考慮到恒等式，仿例2解決.【證明】令因?yàn)?，?于是由式得.這說明an為等差數(shù)列，而a0=1,a1=2，故公差d=1，且an=n+1 .【說明】此題運(yùn)用變換求和指標(biāo)的方法，找出了an，an1，an2之間的線性關(guān)系式，再由 初始條件求得an.這種利用遞推關(guān)系求組合數(shù)的方法，在解決較復(fù)雜的計(jì)算或證明組事恒等式時(shí)經(jīng)常用到.例11：設(shè)是集合M的兩個(gè)劃分，又對(duì)任何兩個(gè)不變的子集有求證：并說明等號(hào)能否成立？【證明】令，不妨設(shè)因兩兩不交，故中至多有個(gè)使 .設(shè) 由的選取知從而 又因

5、故 即 所以 若因故若則 從而 下面說明是可以取到的.顯然這時(shí)為偶數(shù)，取則，令易驗(yàn)證M的兩個(gè)劃分.D1=1,23,45,67,8, D2=1,23,54,67,8,滿足題目條件.例12：設(shè)是正整數(shù)，我們說集合1，2，2的一個(gè)排列（）具有性質(zhì)P，是指在1，2，21當(dāng)中至少有一個(gè)，使得求證，對(duì)于任何，具有性質(zhì)P的排列比不具有性質(zhì)P的排列的個(gè)數(shù)多.（1989，第30屆IMO試題6）【證明】設(shè)A為不具有性質(zhì)P的排列的集合，B為具有性質(zhì)P的排列的集合，顯然為了證明，只要得到就夠了.使作容斥原理.設(shè)()中,與相鄰的排列的集合為則由容斥原理得 = 例13：平面上給定個(gè)點(diǎn)，其中任何三點(diǎn)不共線，任意地用線段連接

6、某些點(diǎn)（這些線段稱為邊），則確保圖形中出現(xiàn)以給定點(diǎn)為頂點(diǎn)的階完全圖的條件是圖形中的邊的條數(shù)【證明】構(gòu)造抽屜：每個(gè)抽屜里有個(gè)相異點(diǎn)，共可得個(gè)抽屜，又由于同一條邊會(huì)在個(gè)抽屜里出現(xiàn)，根據(jù)抽屜原則知，當(dāng)時(shí)，才能確保有一個(gè)抽屜里有條邊，而這條邊恰好與其中不共線的相異點(diǎn)構(gòu)成一個(gè)階完全圖.這就是說，確保圖形中出現(xiàn)階完全圖的條件是其中邊的條數(shù)【評(píng)述】“完全圖”，是圖論中的基本概念.（此處從略）例14：設(shè)為實(shí)數(shù)，滿足求證：對(duì)于每一整數(shù)，存在不全為零的整數(shù)使得并且（1987年第28屆IMO試題3）【證】由柯西不等式得 即所以，當(dāng)時(shí)，有把區(qū)間0，等分成個(gè)小區(qū)間，每個(gè)小區(qū)間的長(zhǎng)度，由于每個(gè)能取個(gè)整數(shù)，因此共有個(gè)正數(shù)，

7、由抽屜原則知必有二數(shù)會(huì)落在同一小區(qū)間內(nèi)，設(shè)它們分別是 與 因此有 很明顯，我們有 現(xiàn)在取這里于是可表示為這里為整數(shù)，適合例15：設(shè)A是一個(gè)有個(gè)元素的集合，A的個(gè)子集兩兩互不包含，試證：（1）（2）其中表示所含元素的個(gè)數(shù)，表示個(gè)不同元素取個(gè)的組合數(shù).（1993年，全國(guó)高中數(shù)學(xué)聯(lián)賽二試第二大題）【分析】若（1）式已證，由柯西不等式立即可得（2）式，因此，關(guān)鍵是證（1）式，又據(jù)組合公式知，（1）式等價(jià)于 所以我們用組合的方法來證明不等式.【證明】（1）對(duì)于A的子集我們?nèi)⊙a(bǔ)集并取的元素在前，元素在后，作排列，. 這樣的排列共有個(gè).顯然,中每一個(gè)排列,也是A中的一個(gè)排列,若時(shí)，對(duì)應(yīng)的排列與對(duì)慶的排列互不

8、相同，則所對(duì)應(yīng)的排列總數(shù)便不會(huì)超過A中排列的總數(shù)現(xiàn)假設(shè)中對(duì)應(yīng)的某一排列，. 與（）中對(duì)應(yīng)的某一排列相同（指出現(xiàn)的元素及元素位置都相同），則當(dāng)時(shí)，；當(dāng)時(shí)，這都與兩兩互不包含，矛盾.由于對(duì)應(yīng)的排列對(duì)互不相同，而A中個(gè)元素的全排列有！個(gè)，故得 即（2）由上證及柯西不等式，有【評(píng)述】本題取自著名的Sperner定理：設(shè)Z為元素，為Z的子集，互不包含，則的最大值為.例16：設(shè)S=0，1，2，N21，A是S的一個(gè)N元子集.證明存在S的一個(gè)N元子集B,使得集合A+B=中的元素模N2的余數(shù)的數(shù)目不少于S中元素的一半. （第40屆IMO預(yù)選題）【證明】設(shè)|X|為子集中元素的個(gè)數(shù)；又為，是的補(bǔ)集；是對(duì)個(gè)參賽選手有相同的判決，證明 （1998年第39屆IMO試題二）【解】設(shè)裁判對(duì)參賽選手的判決為，其中 則（）中對(duì)個(gè)參賽選手判決的記錄，它是一個(gè)長(zhǎng)度為的（01）序