高中數(shù)學(xué)競賽專題8-15

1、專題八 數(shù)學(xué)奧林匹克專題講座-素?cái)?shù) 上海市上海中學(xué) 顧濱 素?cái)?shù)是數(shù)論中核心的問題之一，因?yàn)樗財(cái)?shù)的定義如此簡單，分布卻如此不規(guī)律.關(guān)于素?cái)?shù)，我們知道的也很少，接下來我們將介紹有關(guān)素?cái)?shù)的一些核心問題，并對其中一些加以討論.一.關(guān)于素?cái)?shù)無窮多. Euclid 第一個(gè)證明了：素?cái)?shù)有無窮多個(gè).【定理1（Euclid）】：素有無窮多個(gè). 它的證明是很經(jīng)典的無窮遞推法，當(dāng)然目前也有其它證法，有興趣的同學(xué)可以參看The proof from the book一書，這里就略去了.下面我們來證明更強(qiáng)的結(jié)論：【定理2（Euler）】 （這里表示對所有的素?cái)?shù)求和，以后類同） 證明：首先證明Euler恒等式：設(shè)實(shí)數(shù)，則

2、（表示對所有的素?cái)?shù)求積，以后類同）. 我們已經(jīng)熟知當(dāng)時(shí)，上式的右邊的級(jí)數(shù)是絕對收斂的，而由于算術(shù)基本定理，若將上式左邊逐項(xiàng)展開，則對每個(gè)n，由于n恰有唯一的一種方法表為，因此恰出現(xiàn)一次，即證得Euler恒等式. 現(xiàn)將Euler恒等式化為：.兩邊取對數(shù)得.利用不等式得：.令即知，又，故成立. Euler這一證明有著很濃的解析色彩，將孤單的素?cái)?shù)與全體正整數(shù)通過式聯(lián)系起來了，我們在后面證明Dirichlet定理時(shí)將用到一樣的思想.另外利用式可以證明任取兩數(shù)互素的概率為，但這已經(jīng)離開主題較遠(yuǎn)，暫不考慮. 為了以后的需要，我們先來定義一些函數(shù)： 若，則定義函數(shù)；定義函數(shù)；以及函數(shù).以下我們一般以表示正整

3、數(shù)，表示素?cái)?shù)，表示約數(shù). 關(guān)于，我們顯然有（這里表示為對n的所有正約數(shù)求和），因此我們有： （交換和號(hào)值得注意）因此結(jié)合可知： , (這里表示至多與同階，即存在使),又因?yàn)?(這一等式詳見第二個(gè)問題)因此, ，故知.更進(jìn)一步，由于故，或者我們可記 式應(yīng)該說是關(guān)于素?cái)?shù)分布的最基本的等式之一，由它可以導(dǎo)出許多有用的結(jié)果.現(xiàn)在，我們就來證明定理2的加強(qiáng)形式:【定理3】：其中,而， (注:說明收斂)【證明】：我們有（其中在上僅在t在為素?cái)?shù)時(shí)不可微，然而當(dāng)t為素?cái)?shù)時(shí)可以形式得認(rèn)為此時(shí)；這一步運(yùn)用了Abel求和的思想）,從而利用分部積分公式可得:又因?yàn)?因此我們就得到了定理3！二.關(guān)于: 對大于2的實(shí)數(shù)x

4、，令為不大于x的素?cái)?shù)個(gè)數(shù),C.F.Gauss在一百多年前提出了著名的猜想： 【素?cái)?shù)定理】：. 我們先來簡要回顧一下素?cái)?shù)定理的提出與解決過程：1850年，Chebyshev證明：存在正常數(shù)使;1859年，Rieman在其論文中提出素?cái)?shù)定理與Rieman的函數(shù)的關(guān)系(，在復(fù)分析中可將解析開拓至全體復(fù)數(shù)s），將數(shù)論與復(fù)變函數(shù)聯(lián)系在了一起.(Euler恒等式已初步體現(xiàn)了分析思想)1896年，Hadamard和Poisson各自獨(dú)立地運(yùn)用復(fù)分析證明了素?cái)?shù)定理.（其中一個(gè)關(guān)鍵點(diǎn)是的零點(diǎn)s的實(shí)部必小于1而大于0，而Riemann猜想是說這樣的零點(diǎn)s的實(shí)部均為）;1896年，Selberg和Erdos獨(dú)立給出

5、了素?cái)?shù)定理的初等證明.我們將不會(huì)證明素?cái)?shù)定理，只因復(fù)分析直觀而艱深；初等方法復(fù)雜而難以理解.在這一節(jié)中，我們將討論Chebyshev不等式，并以此引入一些基本的解析數(shù)論技巧.【定理4(Chebyshev)】：設(shè)，則.【證明】：以,則 ,(注意pm時(shí)，M中恰含一個(gè)p)而對,代入知,也即,另一方面，,于是知 ,取，由并對較小的x作檢驗(yàn)即可得左半邊不等式;再來證右半邊，同樣由知,又,故知 , 同理考察 ,現(xiàn)在右半式對成立，而當(dāng)時(shí)遞增，故只須考慮,利用并對右半式歸納知：（經(jīng)檢驗(yàn)對均成立）若，則 若，類似可證！于是我們證明了Chebyshev不等式，也就說明了素?cái)?shù)的上密度為0.順便指出，由我們得到.考慮

6、,于是結(jié)合歸納法（具體細(xì)節(jié)略去）可知 ,這是一個(gè)很好的漸近公式，盡管我們將看到，應(yīng)有【定理5】：素?cái)?shù)定理.【證明】： ,余下只需估計(jì),事實(shí)上， 結(jié)合即知定理3.3成立！Erdos和Selberg正是通過證明才最終得到了素?cái)?shù)定理的初等證明.三.關(guān)于Dirichlet定理代數(shù)方法證明 前面圍繞“素?cái)?shù)有無窮多個(gè)”這一主題展開討論，如果考慮特殊序列中的素?cái)?shù)，問題就很不簡單了.一個(gè)最基本的問題是等差數(shù)列中素?cái)?shù)是否有無窮多個(gè)？（這和陶哲軒的定理驚人地類似，k是“素?cái)?shù)”和“等差數(shù)列”顛倒了一下）,我們有：【定理6(Dirichlet 1837)】：設(shè)中有無窮多個(gè)素?cái)?shù). 在這里，先來討論Dirichlet定理

7、的一些特殊情況，先從Euclid方法談起：【定理7】：存在無窮多個(gè)模3余2的素?cái)?shù)，也存在無窮多個(gè)模4余3的素?cái)?shù).【證明】：首先這樣的素?cái)?shù)必存在，假設(shè)有,考慮，它必含有一個(gè)模3余2的素因子，且異于，對模4余3，同樣地考慮既可！下面我們引入多項(xiàng)式方法：首先大家熟悉二次剩余的概念，我們在此引入Legrendre符號(hào)：設(shè)p為素?cái)?shù)，q為正整數(shù)，令不加證明地指出：, ,及關(guān)于奇素?cái)?shù)的二次互反律（屬于Gauss）：.【定理8】：(i)存在無窮多個(gè)模8余7的素?cái)?shù); (ii)存在無窮多個(gè)模5余4的素?cái)?shù).【證明】：(i)若有任取素?cái)?shù)有，因此又因?yàn)楣蔒必有某素因子，P異于，證畢！(ii)同理考慮. 下面我們回到.

8、Dirichlet定理,我們用代數(shù)方法加以闡釋:我們看到，定理4的證明實(shí)際上是考慮多項(xiàng)式,這一多項(xiàng)式的每個(gè)素因子均，且給出無窮多個(gè)的素?cái)?shù)，而(ii)則是考察. 類似地，考慮.現(xiàn)在我們定義:設(shè)一個(gè)模m余a的整系數(shù)多項(xiàng)式是適合下述兩個(gè)條件的多項(xiàng)式：(i) 若素?cái)?shù)p是某個(gè)的約數(shù)，則;(ii) 而且存在無窮多個(gè)這樣的,這樣的多項(xiàng)式自然能解決Dirichlet定理的一類情況，這方面我們有：【定理9(Schur 1912)】：若，則存在一個(gè)mod m余a的Euchid多項(xiàng)式，然而，這一Euclidean方法有局限；1988年，Murty證明了如下結(jié)果:【定理10(Murty)】：若，則不存在這樣的Eucl

9、id多項(xiàng)式. 這里必須指出，應(yīng)用代數(shù)數(shù)論（結(jié)合Galois理論）可以證明：（這解釋了定義(i)）對每個(gè)非常數(shù)多項(xiàng)式f，必有無窮多個(gè)，使對某個(gè)n成立)定理10的證明也要應(yīng)用深刻的代數(shù)數(shù)論技巧，這里我們不作介紹.應(yīng)用初等方法，我們可以來證明定理6的一部分，即的情況:【證明】：令為m次本原單位根，先來討論a=1的情形此時(shí)令為m階的分圓多項(xiàng)式，我們指出而（一個(gè)可考慮的證法是利用及歸納法，留給讀者）,如果素?cái)?shù)p整除某個(gè),即 我們知道： ,因此化為 ,將上面的乘積式化開，可知 其中h是關(guān)于所有的對稱多項(xiàng)式，因此h的值是一個(gè)整數(shù)（這里我們利用了所有為首一多項(xiàng)式的根及對稱多項(xiàng)式基本定理）,因此化為 現(xiàn)在（將j

10、與配對相乘）,而令，則為t次本原單位根因此 (最后一步因?yàn)?，?. 由上面的敘述，若，則而，于是由知現(xiàn)在要避免，只須考慮，此時(shí)由于的常數(shù)項(xiàng)為，故在x為整數(shù)時(shí)的值與m互素,這也就是說：的每個(gè)素因子,這樣的p有無窮多個(gè)（Enclid遞推）另外，每個(gè)均是某個(gè)的約數(shù),這是因?yàn)椋寒?dāng)時(shí)，成立，逆推可知成立,即，得證！ 我們將的情形留給大家，只提示大家考慮多項(xiàng)式（注意，指標(biāo)j與對應(yīng)的相同，但在上述乘積中只算一次）,這時(shí)，我們同樣地可知每個(gè)均是某個(gè)的約數(shù)，然而，要找一個(gè)n使卻不容易（這樣能找出）一個(gè)可行的想法是利用f的根為互異實(shí)數(shù)，因此存在開區(qū)間I，使f在I上為負(fù)，此時(shí)對于I上任意有理點(diǎn)，可證含有，之后只要再

11、取整數(shù)n，使即可知,從而具體細(xì)節(jié)請有興趣的同學(xué)補(bǔ)全. 還要提一下，若，同樣考察則可證f的素因子，反之亦然，但很難從中證明存在，只有反過來通過Dirichlet定理才能完成定理6的證明. 專題九幾何不等式 武鋼三中 周國棟幾何問題中出現(xiàn)的不等式稱為幾何不等式。求解數(shù)學(xué)競賽中出現(xiàn)的許多幾何不等式，需要熟悉幾何中有關(guān)的基本不等式和定理，還要掌握代數(shù)方法和幾何方法.一、 幾何方法 用幾何方法解決有關(guān)的幾何不等式，涉及幾何中的有關(guān)不等式和定理.例1 已知M是內(nèi)任意一點(diǎn)，求證：證明：先證一個(gè)引理. 引理：設(shè)M是凸四邊形ABCD內(nèi)一點(diǎn)，則 引理的證明：如圖，設(shè)AM交四邊形ABCD于點(diǎn)N,不妨設(shè)N在CD上，

12、回到原題. 例2 求證：圓內(nèi)接k邊形中，周長最大者必是正k邊形. 例3 托勒密定理的推廣 在四邊形ABCD中，有，等號(hào) 成立時(shí)，四邊形ABCD是圓內(nèi)接四邊形.例4 設(shè)的外接圓O與內(nèi)切圓I的半徑分別為R，r,ABBC，求證：(1) (2) 二、代數(shù)方法利用代數(shù)方法證明有關(guān)幾何不等式，一是利用有關(guān)的代數(shù)不等式，或是轉(zhuǎn)換成代數(shù)極值的問題解決. 所以（2）式成立，故原不等式成立.說明：由以上結(jié)果可得：三、三角方法 用三角方法來證明幾何不等式，即利用三角函數(shù)來反映圖形變化的規(guī)律，從而將幾何問題轉(zhuǎn)化為三角問題來解決。 專題十 共圓、共線、共點(diǎn)大連24中一、 基礎(chǔ)知識(shí)：梅涅勞斯ABC定理：設(shè)分別是的三邊BC

13、，CA，AB或其延長線上的點(diǎn)，若三點(diǎn)共線，則.逆定理：設(shè)分別是的三邊BC，CA，AB或其延長線上的點(diǎn)，若，則三點(diǎn)共線。塞瓦定理：設(shè)分別是的三邊BC，CA，AB或其延長線上的點(diǎn)，若三直線平行或共點(diǎn)，則。逆定理：設(shè)分別是的三邊BC，CA，AB或其延長線上的點(diǎn)，若，則三直線平行或共點(diǎn)。ABCD角元形式的塞瓦定理：設(shè)分別是的BC、CA、AB所在直線的點(diǎn)，則三直線平行或共點(diǎn)的充要條件是托勒密定理：圓內(nèi)接四邊形的兩組對邊乘積之和等于兩對角線的乘積。推論1（三弦定理）：如果A是圓上任意一點(diǎn)，AB，AC，AD是該圓上順次的三條弦，則推論2（四角定理）：四邊形ABCD內(nèi)接于O，則直線上的托勒密定理：若A,B,C

14、,D為一直線上依次排列的四點(diǎn)，則四邊形中的托勒密定理：設(shè)ABCD為任意凸四邊形，則當(dāng)且僅當(dāng)A，B，C，D四點(diǎn)共圓時(shí)取等號(hào)。西姆松定理及逆定理：過三角形外異于三角形頂點(diǎn)的任意一點(diǎn)作三邊的垂線，則三垂足共線的充要條件是該點(diǎn)在三角形的外接圓上。KLNMCBAPAMLAKCBNLBKC例4：例5：給出銳角ABC，以AB為直徑的圓與AB邊的高CC及其延長線交于M，N.以AC為直徑的圓與AC邊的高BB及其延長線交于:P，Q.求證：M，N，P，Q四點(diǎn)共圓.(第19屆美國數(shù)學(xué)奧林匹克) 分析：設(shè)PQ，MN交于K點(diǎn)，連接AP，AM.欲證M，N，P，Q四點(diǎn)共圓，須證MKKNPKKQ，即證(MCKC)(MC+KC)

15、(PBKB)(PB+KB)或MC2KC2=PB2KB2. 不難證明AP=AM，從而有AB2+PB2=AC2+MC2.故MC2PB2=AB2AC2=(AK2KB2)(AK2KC2) =KC2KB2. 由即得，命題得證.例6：如圖所示，菱形ABCD中，A=120，O為ABC外接圓，M為其上一點(diǎn)，連接MC交AB于E，AM交CB延長線于F。求證：D，E，F(xiàn)三點(diǎn)共線。證 如圖，連AC，DF，DE。因?yàn)镸在O上，則AMC=60=ABC=ACB，有AMCACF，得。又因?yàn)锳MC=BAC，所以AMCEAC，得。所以，又BAD=BCD=120，知CFDADE。所以ADE=DFB。因?yàn)锳DBC，所以ADF=DFB

16、=ADE，于是F，E，D三點(diǎn)共線。:例7：如圖，O、H分別是銳角ABC的外心和垂心，D是BC邊的中點(diǎn)，由H向A及其外角平分線作垂線，垂足分別是E是F.證明：D、E、F三點(diǎn)共線.證明：連結(jié)OA，OD，并延長OD交ABC的外接圓于M則ODBC，A、E、M三點(diǎn)共線AE、AF分別是ABC的A及其外角平分線，AEAF 又HEAE，HFAF 四邊形AEHF為矩形.因此AH與EF互相平分，設(shè)其交點(diǎn)為G，于是：AG AH EFEG 而OAOM，且ODAH OAMOMAMAGGEA 故EGOA (1)O、H分別是ABC的外心和垂心，且ODBCOD AHAG，因此，若連結(jié)DG，則四邊形AODG為平行四邊形 ，從而

17、DGOA (2)(1)和(2)知，D、E、G三點(diǎn)共線，但F在EG上故D、E、F三點(diǎn)共線.練習(xí)：1.已知點(diǎn) 是 的中線 上的一點(diǎn), 直線 交邊 于點(diǎn), 且 是 的外接圓的切線, 設(shè) , 試求 (用 表示)._H_O_F_G_E_D_A_B_C2如圖，是的兩條高，和分別是和的中點(diǎn)，是的外心。求證：。3.設(shè)的外接圓上的一點(diǎn)關(guān)于中點(diǎn)的對稱點(diǎn)為，為的垂心，直線交于，為直線上一點(diǎn)，求證：_I_G_H_J_F_P_M_Q_A_B_C_D_E4. 如圖在四邊形ABCD中，對角線AC平分BAD。在CD上取一點(diǎn)E，BE與AC相交于F，延長DF交BC于G。求證：GAC=EAC 第4題 第5題5. 如圖,M為ABC內(nèi)

18、一點(diǎn)，D、E、F分別為AM、BM、CM延長線上的點(diǎn)，DE分別交BC、CA于H、Q，EF分別交CA、AB于I、J，DF分別交AB、BC于P、G，若H、M、J三點(diǎn)共線，則P、M、Q三點(diǎn)共線6. 是以為直徑的半圓上的兩點(diǎn)，交于點(diǎn)，交于點(diǎn)，點(diǎn)是的外心，且，點(diǎn)分別在線段上，且滿足.求證：7. 過銳角ABC的頂點(diǎn)A、B、C的三條高分別交其對邊于點(diǎn)D、E、F. 過點(diǎn)D平行于EF的直線分別交AC、AB于點(diǎn)Q和R，EF交BC于點(diǎn)P. 證明：PQR的外接圓過BC的中點(diǎn).8. 的內(nèi)心為，三角形內(nèi)一點(diǎn)滿足，求證：，而且等號(hào)當(dāng)且僅當(dāng)時(shí)成立答案“1.證明：在 中，由Menelaus定理得因?yàn)?，所以由 ，知 ，則所以，

19、即 因此， 又 ， 故 2證明：如圖，連結(jié)和 ，又 延長交于，連結(jié) 四點(diǎn)共圓。，即又 于是，即。3.證明：設(shè)中點(diǎn)為，為的垂心， 設(shè)是關(guān)于的對稱點(diǎn)則四邊形、是平行四邊形在的外接圓上，又 為的外接圓的直徑 共圓4. 證 如圖，連接BD交AC于H，過點(diǎn)C作AB的平行線交AG的延長線于I，過點(diǎn)C作AD的平行線交AE的延長線于J。對BCD用塞瓦定理，可得 因?yàn)锳H是BAD的角平分線，由角平分線定理知。代入式得 因?yàn)镃IAB，CJAD，則，。代入式得.從而CI=CJ。又由于 ACI=180BAC=180DAC=ACJ，所以ACIACJ，故IAC=JAC，即GAC=EAC.5. 設(shè)CF交DE于K，交AB于L

20、點(diǎn)，J，M，H為直線JH與EKF的邊或延長線的交點(diǎn)，由梅涅勞斯定理可得：又J，L，B為直線AB與FEM的邊或延長線的交點(diǎn)同理，CHB截EKM，得得由ACP截FDM得CQA截DMK得得得由梅涅勞斯定理的逆定理可知：P，M，Q三點(diǎn)共線6. 證明：連求得，易知，由題意知四點(diǎn)共圓，故，所以四點(diǎn)共圓，由托勒密定理有，又因，所以， 由條件知，所以，故，所以。7. 點(diǎn)P的存在意味著ABAC. 由對稱性，可設(shè)ABAC，則P、D在射線MC上，點(diǎn)B、C、E、F共圓，因此，PBPC = PEPF. 垂足DEF的外接圓也即ABC的歐拉圓（九點(diǎn)圓）必經(jīng)BC的中點(diǎn)M.因此PEPF = PDPM.所以 PBPC = PD

21、PM.AEFABC，因此，ABC =AEF.QDEF，AEF =CQD，ABC =RBD.因而RBD =CQD.顯然BDR =QDC，故BDRQDC.DQDR = DRDC.如能證明 DBDC = DPDM，則等式DQDR = DPDM成立，也就證明了Q、R、M、P共圓.由此，證明本題就簡化為由化為.令MB = MC = a，MD = d，MP = p，則有PB = p + a，DB = a + d，PC = p a，DC = a d，DP = p d.由得(p + a) (p a) = (p d) p，即a2 = dp.由得(a + d) (a d) = (p d) d，也得a2 = dp.

22、 成立. 命題成立.8. 證明：，故，從而四點(diǎn)共圓但由內(nèi)外角平分線互相垂直知與邊上的旁切圓心共圓且是這個(gè)圓的直徑，的中點(diǎn)為圓心由于共線（的平分線），且在圓周上，故等號(hào)當(dāng)且僅當(dāng)為線段與圓周的交點(diǎn)即時(shí)成立專題十一 平面幾何常見解題方法清華附中方法一、純幾法三個(gè)重要定理：1梅涅勞斯(Menelaus)定理：在的三邊或其延長線上有點(diǎn)，則共線的充分必要條件是：2塞瓦(Seva)定理：設(shè)分別是的 邊上的點(diǎn)，則相交于一點(diǎn)的充分必要條件是：3托勒密(Ptolemy)定理：在四邊形中，恒有，四邊形內(nèi)接于一圓的充分必要條件是：以上不等式的等號(hào)成立以上三個(gè)定理，通常把充分性稱為定理，必要性稱為逆定理例1設(shè)是正內(nèi)任意

23、一點(diǎn)，關(guān)于三邊的對稱點(diǎn)分別為，求證：三線共點(diǎn)證明：設(shè)分別與相交于 ，連結(jié) 同理 ， 由塞瓦定理知：三線共點(diǎn)例2設(shè)的邊AB的中點(diǎn)為N，D是射線AC上一點(diǎn)，滿足CD=BC，P是射線DN上一點(diǎn)，且與點(diǎn)A在邊BC的同側(cè)，滿足，PC與AB交于點(diǎn)E，BC與DP交于點(diǎn)T.求表達(dá)示的值F解：如圖，延長BP交直線AC于F，于是， ，從而，故 注意到直線DTN截，應(yīng)用梅涅勞斯定理得，. 則，故 同理，由直線DNP截，得 由直線CEP截，得，所以 因此，例3設(shè)是一圓的直徑，和是圓上同側(cè)的兩點(diǎn)，且弦與相交于，于，求證：證明：延長交圓于，連結(jié) 是圓的直徑 四點(diǎn)共圓 同理，四點(diǎn)共圓 同理 是關(guān)于的對稱點(diǎn) 由托勒密定理，得

24、例4ABDEGIHJF如圖，在四邊形ABCD中，對角線AC平分BAD，在CD上取一點(diǎn)E，BE與AC相交于F，延長DF交BC于G。求證：GAC=EAC。證明：連結(jié)BD交AC于H。對BCD用塞瓦定理，可得=1C又由角平分線定理得：=，=1過點(diǎn)C作CIAB交AG的延長線于I，作CJAD交AE的延長線于J，由相似三角形知： =，=1CI=CJ又ACI=-CAB=-CAE=CAJCAICAJCAG=CAE例5過圓外一點(diǎn)P作圓的兩條切線和一條割線，切點(diǎn)為A、B。所作割線交圓于C、D兩點(diǎn)，C在P、D之間。在弦CD上取一點(diǎn)Q，使DAQ=PBC。求證：DBQ=PAC。ABCPDQ證明：連結(jié)AB，在ADQ和PBC

25、中：ADQ=ABC，DAQ=PBC=BACADQPBC故： = 即：BCAD=ABDQ又由切割線關(guān)系知：PCAPAD、PCBPBD故：=、=又： PA=PB=于是可得：ABDQ= BCAD=ACBD又由關(guān)于圓內(nèi)接四邊形ABCD的托勒密定理知： ADBC+ACBD=ABCD于是有： ABCD=2ABDQ DQ=CD=CQ =， DAB=QCB DABQCB ABD=CBQ DBQ=ABC=PAC方法二、非純幾方法-三角法方法三、非純幾方法-解析法方法四、-專題十二第十一講 組合恒等式與不等式深圳中學(xué) 鄢志俊知識(shí)與方法一、 組合恒等式知識(shí)概要數(shù)學(xué)競賽中組合數(shù)計(jì)算和組合恒等式的證明，是以高中排列、組

26、合、二項(xiàng)式定理為基礎(chǔ)，并加以推廣和補(bǔ)充而形成的一類習(xí)題，它往往會(huì)具有一定的難度且靈活性較強(qiáng)。解決這類問題常常對學(xué)生良好的運(yùn)算能力和思維的靈活性都有較高的要求。同時(shí)，此類問題的解決也有著自身特殊的解題技巧。因此，在各類數(shù)學(xué)競賽中經(jīng)常被采用。1，基本的組合恒等式簡單的組合恒等式的化簡和證明，可以直接運(yùn)用課本所學(xué)的基本組合恒等式。事實(shí)上，許多競賽中出現(xiàn)的較復(fù)雜的組合數(shù)記算或恒等式證明，也往往運(yùn)用這些基本組合恒等式，通過轉(zhuǎn)化，分解為若干個(gè)簡單的組合恒等式而加以解決?；镜慕M合恒等式有：；2，解題中組合恒等式的證明常用方法 運(yùn)用基本組合恒等式進(jìn)行變換； 運(yùn)用二項(xiàng)展開式作為輔助函數(shù)，通過比較某項(xiàng)的系數(shù)進(jìn)行

27、計(jì)算或證明； 運(yùn)用數(shù)學(xué)歸納法； 變換求和指標(biāo)； 運(yùn)用賦值法進(jìn)行證明； 建立遞推公式，由初始條件及遞推關(guān)系進(jìn)行計(jì)算和證明； 考慮組合意義；構(gòu)造合理的模型。 母函數(shù)； 概率法二、 組合不等式組合不等式以前我們見的不多，在其他一些書籍中組合不等式的著述也很少，但是近年來組合不等式的證明卻出現(xiàn)在國內(nèi)、國際大賽上.例如1993年中國高中數(shù)學(xué)聯(lián)賽二試第二大題為：設(shè)A是一個(gè)有n個(gè)元素的集合，A的m個(gè)子集A1，A2，Am兩兩互不包含，試證：（1）（2）其中|Ai|表示Ai所含元素的個(gè)數(shù)，表示n個(gè)不同元素取|Ai|的組合數(shù).再如1998年第39屆國際數(shù)學(xué)奧林匹克競賽中第二大試題為：在某一次競賽中，共有a個(gè)參賽選

28、手與b個(gè)裁判，其中b3，且為奇數(shù).每個(gè)裁判對每個(gè)選手的評分中只有“通過”或“不及格”兩個(gè)等級(jí)，設(shè)k是滿足條件的整數(shù)；任何兩個(gè)裁判至多可對k個(gè)選手有完全相同的評分. 證明：因此我們有必要研究組合不等式的證明方法.組合不等式的證明方法有：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被計(jì)算了k次，當(dāng)k2時(shí)，集合兩兩的交集共有個(gè).由于中至少少被計(jì)算了k1次，這樣我們得到下面的不等式：組合不等式（*）可由容斥公式：刪去右

29、邊第三個(gè)和式起的所有和式得到.采用這種辦法，我們可以從容斥公式得到另外一些組合不等式，只是要注意這些不等式的方向的變化.3利用抽屜原則由于抽世原則的結(jié)論本身就是組合不等式關(guān)系，所以我們利用抽屜原則，巧妙構(gòu)造抽屜的方法證明組合不等式.4利用組合分析在復(fù)雜的組合計(jì)數(shù)問題、離散極值問題等問題中，會(huì)出現(xiàn)一些組合不等式，這時(shí)可運(yùn)用組合分析方法證明之.范例選講例1，求證：.證明：根據(jù)前面提到的基本的組合恒等式第三條，可得：左邊右邊例2，（1）求和式的值?；舅悸罚簩⒏膶憺椋葘⒂煤愕仁?提取公因式，然后再將變形成為，而又可以繼續(xù)運(yùn)用上述恒等變形，這樣就使得各項(xiàng)系數(shù)中均不含有變動(dòng)指標(biāo)了。解： 例2，（2）求

30、的值。解： 。例3，設(shè)，求證：。基本思路：由兩個(gè)連續(xù)自然數(shù)與的積，聯(lián)想到可化為，進(jìn)一步運(yùn)用，反復(fù)運(yùn)用基本的組合恒等式2即可化簡。證明：例4，求證：。證明：所以，右邊。例5，求證： 基本思路1：此題若考慮用基本組合恒等式來證明是比較困難的，注意到左端各項(xiàng)恰好是二項(xiàng)展開式中各項(xiàng)系數(shù)的平方，考慮構(gòu)造兩個(gè)二項(xiàng)展開式。證明：因?yàn)椋猴@然，的展開式中，常數(shù)項(xiàng)即為所求證等式的左端。不妨設(shè)，將原式變形為：將上式展開，其中常數(shù)項(xiàng)為，由此可知，原式成立。基本思路2：注意到恒等式，要證的等式的左邊可變形為：；而等式右邊即為：，因此可以考慮建立適當(dāng)?shù)慕M合記數(shù)模型來加以證明。證明：設(shè)袋子中有個(gè)白球，個(gè)紅球，現(xiàn)從這個(gè)小球中

31、隨機(jī)抽取個(gè)小球，其方法種數(shù)為：。另一方面，可以看成次如下的取球活動(dòng)：從個(gè)白球中取出個(gè)，再從個(gè)紅球中取出個(gè)，其取法種數(shù)為：，所以符合題意的取球方法種數(shù)是：。因此原式成立。說明：本題的兩種證明方法均采用了構(gòu)造思想。構(gòu)造法是解決競賽問題的一種常用方法。例6，求證:;.證：依題意構(gòu)造概率模型: 設(shè)有100件,其中有5件次品,任取3件抽查,則被抽查的3件產(chǎn)品中恰好有件次品的事件的概率為:.為必然事件)且.即.故.依題意構(gòu)造概率模型: 設(shè)個(gè)產(chǎn)品中有個(gè)次品,個(gè)正品,從中任取個(gè)抽查,則這個(gè)被抽查的產(chǎn)品中恰有個(gè)次品的事件的概率為:.,且,.即 ,故 . 在(2)題的模型中,令,得,所以 .例7，設(shè)A是一個(gè)有個(gè)元

32、素的集合，A的個(gè)子集兩兩互不包含，試證：（1）（2）其中表示所含元素的個(gè)數(shù)，表示個(gè)不同元素取個(gè)的組合數(shù).（1993年，全國高中數(shù)學(xué)聯(lián)賽二試第二大題）【分析】若（1）式已證，由柯西不等式立即可得（2）式，因此，關(guān)鍵是證（1）式，又據(jù)組合公式知，（1）式等價(jià)于 所以我們用組合的方法來證明不等式.【證明】（1）對于A的子集我們?nèi)⊙a(bǔ)集并取的元素在前，元素在后，作排列，. 這樣的排列共有個(gè).顯然,中每一個(gè)排列,也是A中的一個(gè)排列,若時(shí)，對應(yīng)的排列與對慶的排列互不相同，則所對應(yīng)的排列總數(shù)便不會(huì)超過A中排列的總數(shù)現(xiàn)假設(shè)中對應(yīng)的某一排列，. 與（）中對應(yīng)的某一排列相同（指出現(xiàn)的元素及元素位置都相同），則當(dāng)時(shí)，

33、；當(dāng)時(shí)，這都與兩兩互不包含，矛盾.由于對應(yīng)的排列對互不相同，而A中個(gè)元素的全排列有！個(gè)，故得 即（2）由上證及柯西不等式，有【評述】本題取自著名的Sperner定理：設(shè)Z為元素，為Z的子集，互不包含，則的最大值為.例8，在某一次競賽中，共有a個(gè)參賽選手與b個(gè)裁判，其中b3，且為奇數(shù).每個(gè)裁判對每個(gè)選手的評分中只有“通過”或“不及格”兩個(gè)等級(jí)，設(shè)k是滿足條件的整數(shù)；任何兩個(gè)裁判至多可對k個(gè)選手有完全相同的評分. 證明：【解】設(shè)裁判對參賽選手的判決為，其中 則（）中對個(gè)參賽選手判決的記錄，它是一個(gè)長度為的（01）序列.我們來考慮這個(gè)序列中每兩個(gè)序列的相同的項(xiàng)的總數(shù)M.一方面,由已知條件每兩個(gè)序列的

34、相同的項(xiàng)不超過個(gè),故 另一方面，設(shè)得到個(gè)0（通過），個(gè)1（不通過），即（）的第個(gè)分量中個(gè)0，個(gè)1，則+=由這個(gè)分量產(chǎn)生的序列的相同的項(xiàng)有但且為奇數(shù)，因此故 =從而 綜合、得 即例9，設(shè)是正整數(shù)，我們說集合1，2，2的一個(gè)排列（）具有性質(zhì)P，是指在1，2，21當(dāng)中至少有一個(gè)，使得求證，對于任何，具有性質(zhì)P的排列比不具有性質(zhì)P的排列的個(gè)數(shù)多.（1989，第30屆IMO試題6）【證明】設(shè)A為不具有性質(zhì)P的排列的集合，B為具有性質(zhì)P的排列的集合，顯然為了證明，只要得到就夠了.使作容斥原理.設(shè)()中,與相鄰的排列的集合為則由容斥原理得 = 訓(xùn)練題1. 求證： （范德蒙恒等式）2. 證明： （n2）3.

35、求證：4. 求證：5.證明6. 平面上給定個(gè)點(diǎn)，其中任何三點(diǎn)不共線，任意地用線段連接某些點(diǎn)（這些線段稱為邊），則確保圖形中出現(xiàn)以給定點(diǎn)為頂點(diǎn)的階完全圖的條件是圖形中的邊的條數(shù) 訓(xùn)練題答案1. 分析：本題注意到等式左邊各項(xiàng)恰是二項(xiàng)展開式中各項(xiàng)二項(xiàng)式系數(shù)的平方，考慮二項(xiàng)展開式 = 和 這兩個(gè)展開式乘積中常數(shù)項(xiàng)式是 證： 又比較兩邊的常數(shù)項(xiàng)，左邊常數(shù)項(xiàng)為右邊的常數(shù)項(xiàng)為，根據(jù)二項(xiàng)展開式中對應(yīng)項(xiàng)的唯一性，得此方法關(guān)鍵是適當(dāng)?shù)剡x擇一個(gè)已知的恒等式，然后比較兩邊x同次冪的系數(shù)。當(dāng)然，已知恒等式的選擇不是唯一的，也可以選擇已知恒等式 ，只須比較恒等式中兩邊含有的系數(shù)即可得證。2. 證：算右邊，假設(shè)有2n個(gè)球，

36、現(xiàn)要在2n個(gè)球中任取出（n1）個(gè)，取法有 種，算左邊，把2n個(gè)球分成兩堆，每堆個(gè)n個(gè)，現(xiàn)要 在2n個(gè)球在中取出（n1）個(gè)，取法是，在第一堆取0個(gè)，第二堆?。╪1）個(gè)，或第一堆取1個(gè)，第二堆 取（n2）個(gè)，或或第一堆取（n1）個(gè)，第二堆 取0.再根據(jù)加法原理總的取法有 又因?yàn)樗裕笥覂蛇叾际窃?n個(gè)球中取出（n1）個(gè)球，因此有， （n2）技巧：用組合分析法證明組合恒等式的步驟是：選指出式子的一邊是某個(gè)問題的解，然后應(yīng)用加法原理和乘法原理等去證明式子的另一邊也是該組合問題的解。3. 證明 設(shè)，則由基本恒等式得 【說明】注意到an中各項(xiàng)的系數(shù)均與n無關(guān)，且符號(hào)正負(fù)相同，由此想到an與an1之間必定

37、存在著某些聯(lián)系，且是遞推關(guān)系.4.【分析】考慮到恒等式，仿3解決.【證明】令因?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)常用到.5.證明分析：注意到，可設(shè)一個(gè)班有個(gè)男生與個(gè)女生，在這個(gè)學(xué)生中選個(gè)同學(xué)（至少有名男生）組成一個(gè)代表團(tuán)，并指定其中一名男生為團(tuán)長，按選出的男生人數(shù)分類，這一類有種選法原式右邊的組合意義是明顯的，即直接在個(gè)男生中選一名團(tuán)長，有種選法，再從剩下的人中

38、選出人為團(tuán)員，共有種選法6. 證明: 構(gòu)造抽屜：每個(gè)抽屜里有個(gè)相異點(diǎn)，共可得個(gè)抽屜，又由于同一條邊會(huì)在個(gè)抽屜里出現(xiàn)，根據(jù)抽屜原則知，當(dāng)時(shí)，才能確保有一個(gè)抽屜里有條邊，而這條邊恰好與其中不共線的相異點(diǎn)構(gòu)成一個(gè)階完全圖.這就是說，確保圖形中出現(xiàn)階完全圖的條件是其中邊的條數(shù)專題十三 調(diào)整與操作問題 青島二中 鄒明在國內(nèi)外各級(jí)數(shù)學(xué)競賽中，常常有調(diào)整和操作變換問題，調(diào)整是組合構(gòu)造的一種常用手段，我們所構(gòu)造的對象，常常需要同時(shí)滿足多個(gè)條件，此時(shí)可先構(gòu)造一個(gè)初胚，使之滿足部分條件，進(jìn)而對其中一些元素進(jìn)行適當(dāng)調(diào)整，使之逐步滿足題設(shè)的所有條件。 操作變換問題的操作過程實(shí)際上是一個(gè)變換過程，但是操作規(guī)則通常無法表

39、達(dá)為明顯的遞推公式，使得操作變換問題往往不需要太多的數(shù)學(xué)知識(shí)，但靈活性、技巧性又很高，對開拓解題思路，增強(qiáng)思維能力有很大的幫助。下面我們研究幾個(gè)具體實(shí)例。例1.A,B兩人做一個(gè)游戲,規(guī)則如下: A,B輪流從左到右在一個(gè)六位數(shù)位上寫上一個(gè)數(shù)碼,A先寫第一位數(shù)(不是0),且六個(gè)數(shù)嗎各不相同.若最后寫下的六位數(shù)能被2,3,5之一整除,則A獲勝,否則B獲勝.證明: A存在必勝策略.證明:設(shè)A,B寫下的數(shù)嗎分別為a1,a2,a3和b1,b2,b3,則最后寫下的六位數(shù)是,其中a10,且六個(gè)數(shù)嗎各不相同. 令M=0,2,4,6,8,5,N=1,3,7,9.首先,B寫的最后一個(gè)數(shù)b30,2,4,6,8,5時(shí),

40、他才可能獲勝.所以,b3N.A獲勝六個(gè)數(shù)之和能被3整除. A獲勝的策略是: A前兩個(gè)數(shù)選N中的數(shù),迫使B的前兩個(gè)必選M中的數(shù). A前兩個(gè)數(shù)選a1=3,a2=9,此時(shí)必有 b1,b2M,b31(mod3).(1)若b1+b20(mod3),則a1+a2+a3+b1+b2+b31+a3(mod3),此時(shí),A的第三個(gè)數(shù)a3取2,5,8中的一個(gè),則A獲勝.(2)若b1+b21(mod3),則a1+a2+a3+b1+b2+b32+a3(mod3),此時(shí),A的第三個(gè)數(shù)a3取1,則A獲勝.(3)若b1+b22(mod3),則a1+a2+a3+b1+b2+b3a3(mod3),此時(shí),0,6中必有一個(gè)數(shù)沒有被B

41、選走,則A的第三個(gè)數(shù)a3就取這個(gè)數(shù),則A獲勝.綜上知,A存在必勝策略.例2.兩只蜘蛛同處在一個(gè)正方體的一個(gè)頂點(diǎn),而一只蒼蠅正處在這個(gè)頂點(diǎn)的體對頂點(diǎn)上.如果蜘蛛和蒼蠅均以同樣的速度沿著正方體的棱移動(dòng)(可來回移動(dòng)),且任何時(shí)刻它們都知道彼此的位置.若一只蜘蛛和蒼蠅同時(shí)到達(dá)同一頂點(diǎn),則認(rèn)為蒼蠅被蜘蛛捉到.證明:如果這兩只蜘蛛足夠聰明,則它們必可捉住蒼蠅.ABCDEFGHMNP證明:如圖,設(shè)最初兩只蜘蛛在頂點(diǎn)A,蒼蠅在頂點(diǎn)G.M,N,P分別為棱GC,GF,GH的中點(diǎn).蜘蛛捉住蒼蠅策略如下:首先,第一只蜘蛛保持與蒼蠅關(guān)于體中心對稱的方向運(yùn)動(dòng),直到蒼蠅到達(dá)M,N,P中某一點(diǎn)(注:蒼蠅也可曾未到達(dá)這三點(diǎn)).

42、(1)若蒼蠅到達(dá)了M,N,P之一(不妨設(shè)M),則這只蜘蛛保持與蒼蠅關(guān)于平面GCBDFHBDHF對稱方向運(yùn)動(dòng).若蒼蠅到達(dá)了B,D,F,H之一,則第一只蜘蛛在此捉住蒼蠅.(2)如果蒼蠅在右圖所示區(qū)域內(nèi)來回運(yùn)動(dòng),則第二只蜘蛛先運(yùn)動(dòng)到G點(diǎn),因右圖無環(huán)路,所以,只要第二只蜘蛛緊跟在蒼蠅后面,兩只蜘蛛必可捉住蒼蠅.例3.在一張mn的方格表中,每一個(gè)方格填上一個(gè)字母A或B,使得相鄰的方格(有公共邊的)字母不同.規(guī)定可按如下法則進(jìn)行操作:每一步操作先選兩個(gè)相鄰的方格,再把其中的字母各進(jìn)行一次替換: A 換成B,B換成C,C換成A.求所有m和n的值,使得經(jīng)若干步操作之后,原來填A(yù)的方格均換成了B,原來填B的方格

43、均換成了A.解:設(shè)最初在mn方格表中,填A(yù)的方格a個(gè),填B的方格b個(gè),則a+b=mn.因?qū)ο噜彿礁?A,B)(B,C)(C,A)(A,B)(B,C)(C,A),所以,若最初填A(yù)的第i個(gè)方格在所有操作結(jié)束后換成了B,則這個(gè)方格必經(jīng)歷了3ki+1(kiN)次操作.若最初填B的第j個(gè)方格在所有操作結(jié)束后換成了A,則這個(gè)方格必經(jīng)歷了3tj+2(tjN)次操作.因最初時(shí)每個(gè)A均與B相鄰,所以,即,3|a-2b=a+b-3b, 從而3|a+b=mn,即m,n至少一個(gè)能被3整除.另一方面,若m,n至少一個(gè)能被3整除,則mn方格表可劃分成若干個(gè)13或31的方格表,在每一個(gè)這樣的方格表中可進(jìn)行如下操作:(1),

44、(2).這表明經(jīng)若干步操作之后可將mn方格表中的A,B互換.綜上可知,至少有一個(gè)能被3整除的m,n為所求.例4.對寫在黑板上的一些正數(shù)進(jìn)行如下操作:選定一個(gè)數(shù)r把它擦掉,再寫上一對數(shù)a,b使得2r2=ab.假定開始時(shí)黑板上只有一個(gè)正數(shù)r,在進(jìn)行k2-1次操作后,黑板上有k2個(gè)數(shù)(可以有相同的).求證:黑板上存在一個(gè)不超過kr的數(shù).證明:由知,經(jīng)n次操作后黑板上各數(shù)倒數(shù)的平方和數(shù)列sn不減,即,設(shè)s為k2-1次操作后黑板上的最小數(shù),則有,所以,skr.例5.兩名選手在一棋盤上做游戲,該棋盤由m+1條水平線和m條垂直線及其P(a,0)(0,a)QR(m+1-a,m+1)S(m+1,m+1-a)(a

45、,1)m(m+1)個(gè)交點(diǎn)構(gòu)成.規(guī)則是:先在其中一個(gè)交點(diǎn)處放一粒石子,然后,兩名選手交替將這粒石子沿著邊移到相鄰的交點(diǎn)上,但不允許再走任何一方之前已經(jīng)走過的邊.如果某選手不能再移動(dòng)石子,則失敗.證明:對于先走選手,如果最初將石子放在了最下面的水平線上,則他存在必勝策略.證明:設(shè)A=(x,y)|x,y=1,2,m為所有格點(diǎn)的集合,設(shè)石子最初位置P(a,0).設(shè)Q(0,a),R(m+1-a,m+1),S(m+1,m+1-a),記直線PQ,QR,RS,SP圍成矩形區(qū)域內(nèi)部及邊界上的A中所有格點(diǎn)所構(gòu)成集合為X.先走選手第一步從P(a,0)到(0,a).將每個(gè)格點(diǎn)如果按如下方式染色:若x+y-a為偶數(shù),則將格點(diǎn)染紅,否則染藍(lán).則先走選手每次都是在紅點(diǎn)處選擇下一步的去向,另一名選手每次都是在藍(lán)點(diǎn)處選擇.對于區(qū)域X來說.X中的每一個(gè)藍(lán)點(diǎn)都不與X外部的點(diǎn)相鄰,每一個(gè)紅點(diǎn)都與X中的偶數(shù)個(gè)藍(lán)點(diǎn)相鄰,因此,只要保持石子在X中,那么,先走選手總有X中奇數(shù)條兩人都未走過的邊可選擇.因游戲必有終止,故先走選手有必勝策略.例6.對放置于點(diǎn)A1,A2,An(n3)及點(diǎn)O處的卡片做如下操作:(1)若某Ai處卡片不少于3張,則從中取3張,在Ai-1,Ai+1,O各放一張(An+i=Ai);(2)若O處的卡片不少于n張,則從中取出n張,在A1,A2,An各放一張.證明:只要放置在這n+1個(gè)點(diǎn)