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

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

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

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

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

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

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

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

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

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

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

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

12、回到原題. 例2 求證：圓內(nèi)接k邊形中，周長最大者必是正k邊形. 例3 托勒密定理的推廣 在四邊形ABCD中，有，等號 成立時，四邊形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)化為三角問題來解決。 專題十 共圓、共線、共點大連24中一、 基礎(chǔ)知識：梅涅勞斯ABC定理：設(shè)分別是的三邊BC

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

14、,D為一直線上依次排列的四點，則四邊形中的托勒密定理：設(shè)ABCD為任意凸四邊形，則當且僅當A，B，C，D四點共圓時取等號。西姆松定理及逆定理：過三角形外異于三角形頂點的任意一點作三邊的垂線，則三垂足共線的充要條件是該點在三角形的外接圓上。KLNMCBAPAMLAKCBNLBKC例4：例5：給出銳角ABC，以AB為直徑的圓與AB邊的高CC及其延長線交于M，N.以AC為直徑的圓與AC邊的高BB及其延長線交于:P，Q.求證：M，N，P，Q四點共圓.(第19屆美國數(shù)學奧林匹克) 分析：設(shè)PQ，MN交于K點，連接AP，AM.欲證M，N，P，Q四點共圓，須證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為其上一點，連接MC交AB于E，AM交CB延長線于F。求證：D，E，F(xiàn)三點共線。證 如圖，連AC，DF，DE。因為M在O上，則AMC=60=ABC=ACB，有AMCACF，得。又因為AMC=BAC，所以AMCEAC，得。所以，又BAD=BCD=120，知CFDADE。所以ADE=DFB。因為ADBC，所以ADF=DFB

16、=ADE，于是F，E，D三點共線。:例7：如圖，O、H分別是銳角ABC的外心和垂心，D是BC邊的中點，由H向A及其外角平分線作垂線，垂足分別是E是F.證明：D、E、F三點共線.證明：連結(jié)OA，OD，并延長OD交ABC的外接圓于M則ODBC，A、E、M三點共線AE、AF分別是ABC的A及其外角平分線，AEAF 又HEAE，HFAF 四邊形AEHF為矩形.因此AH與EF互相平分，設(shè)其交點為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三點共線，但F在EG上故D、E、F三點共線.練習：1.已知點 是 的中線 上的一點, 直線 交邊 于點, 且 是 的外接圓的切線, 設(shè) , 試求 (用 表示)._H_O_F_G_E_D_A_B_C2如圖，是的兩條高，和分別是和的中點，是的外心。求證：。3.設(shè)的外接圓上的一點關(guān)于中點的對稱點為，為的垂心，直線交于，為直線上一點，求證：_I_G_H_J_F_P_M_Q_A_B_C_D_E4. 如圖在四邊形ABCD中，對角線AC平分BAD。在CD上取一點E，BE與AC相交于F，延長DF交BC于G。求證：GAC=EAC 第4題 第5題5. 如圖,M為ABC內(nèi)

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

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

20、點，J，M，H為直線JH與EKF的邊或延長線的交點，由梅涅勞斯定理可得：又J，L，B為直線AB與FEM的邊或延長線的交點同理，CHB截EKM，得得由ACP截FDM得CQA截DMK得得得由梅涅勞斯定理的逆定理可知：P，M，Q三點共線6. 證明：連求得，易知，由題意知四點共圓，故，所以四點共圓，由托勒密定理有，又因，所以， 由條件知，所以，故，所以。7. 點P的存在意味著ABAC. 由對稱性，可設(shè)ABAC，則P、D在射線MC上，點B、C、E、F共圓，因此，PBPC = PEPF. 垂足DEF的外接圓也即ABC的歐拉圓（九點圓）必經(jīng)BC的中點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. 證明：，故，從而四點共圓但由內(nèi)外角平分線互相垂直知與邊上的旁切圓心共圓且是這個圓的直徑，的中點為圓心由于共線（的平分線），且在圓周上，故等號當且僅當為線段與圓周的交點即時成立專題十一 平面幾何常見解題方法清華附中方法一、純幾法三個重要定理：1梅涅勞斯(Menelaus)定理：在的三邊或其延長線上有點，則共線的充分必要條件是：2塞瓦(Seva)定理：設(shè)分別是的 邊上的點，則相交于一點的充分必要條件是：3托勒密(Ptolemy)定理：在四邊形中，恒有，四邊形內(nèi)接于一圓的充分必要條件是：以上不等式的等號成立以上三個定理，通常把充分性稱為定理，必要性稱為逆定理例1設(shè)是正內(nèi)任意

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

24、例4ABDEGIHJF如圖，在四邊形ABCD中，對角線AC平分BAD，在CD上取一點E，BE與AC相交于F，延長DF交BC于G。求證：GAC=EAC。證明：連結(jié)BD交AC于H。對BCD用塞瓦定理，可得=1C又由角平分線定理得：=，=1過點C作CIAB交AG的延長線于I，作CJAD交AE的延長線于J，由相似三角形知： =，=1CI=CJ又ACI=-CAB=-CAE=CAJCAICAJCAG=CAE例5過圓外一點P作圓的兩條切線和一條割線，切點為A、B。所作割線交圓于C、D兩點，C在P、D之間。在弦CD上取一點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方法二、非純幾方法-三角法方法三、非純幾方法-解析法方法四、-專題十二第十一講 組合恒等式與不等式深圳中學 鄢志俊知識與方法一、 組合恒等式知識概要數(shù)學競賽中組合數(shù)計算和組合恒等式的證明，是以高中排列、組

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

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

28、手與b個裁判，其中b3，且為奇數(shù).每個裁判對每個選手的評分中只有“通過”或“不及格”兩個等級，設(shè)k是滿足條件的整數(shù)；任何兩個裁判至多可對k個選手有完全相同的評分. 證明：因此我們有必要研究組合不等式的證明方法.組合不等式的證明方法有：1在集合間建立單射，利用集合階的不等關(guān)系定理，設(shè)X和Y都是有限集，f為從X到Y(jié)的一個映射，（1）若f為單射，則|X|Y|；（2）若f為滿射，則|X|Y|.2利用容斥原理例如：設(shè)元素a屬于集族A1，A2，An的k個不同集合，則在中a被計算了k次，當k2時，集合兩兩的交集共有個.由于中至少少被計算了k1次，這樣我們得到下面的不等式：組合不等式（*）可由容斥公式：刪去右

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

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

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

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

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

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

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

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

37、存在著某些聯(lián)系，且是遞推關(guān)系.4.【分析】考慮到恒等式，仿3解決.【證明】令因為，令 于是由式得.這說明an為等差數(shù)列，而a0=1,a1=2，故公差d=1，且an=n+1 .【說明】此題運用變換求和指標的方法，找出了an，an1，an2之間的線性關(guān)系式，再由 初始條件求得an.這種利用遞推關(guān)系求組合數(shù)的方法，在解決較復雜的計算或證明組事恒等式時經(jīng)常用到.5.證明分析：注意到，可設(shè)一個班有個男生與個女生，在這個學生中選個同學（至少有名男生）組成一個代表團，并指定其中一名男生為團長，按選出的男生人數(shù)分類，這一類有種選法原式右邊的組合意義是明顯的，即直接在個男生中選一名團長，有種選法，再從剩下的人中

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

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

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

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

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

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

44、(2).這表明經(jīng)若干步操作之后可將mn方格表中的A,B互換.綜上可知,至少有一個能被3整除的m,n為所求.例4.對寫在黑板上的一些正數(shù)進行如下操作:選定一個數(shù)r把它擦掉,再寫上一對數(shù)a,b使得2r2=ab.假定開始時黑板上只有一個正數(shù)r,在進行k2-1次操作后,黑板上有k2個數(shù)(可以有相同的).求證:黑板上存在一個不超過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òu)成.規(guī)則是:先在其中一個交點處放一粒石子,然后,兩名選手交替將這粒石子沿著邊移到相鄰的交點上,但不允許再走任何一方之前已經(jīng)走過的邊.如果某選手不能再移動石子,則失敗.證明:對于先走選手,如果最初將石子放在了最下面的水平線上,則他存在必勝策略.證明:設(shè)A=(x,y)|x,y=1,2,m為所有格點的集合,設(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中所有格點所構(gòu)成集合為X.先走選手第一步從P(a,0)到(0,a).將每個格點如果按如下方式染色:若x+y-a為偶數(shù),則將格點染紅,否則染藍.則先走選手每次都是在紅點處選擇下一步的去向,另一名選手每次都是在藍點處選擇.對于區(qū)域X來說.X中的每一個藍點都不與X外部的點相鄰,每一個紅點都與X中的偶數(shù)個藍點相鄰,因此,只要保持石子在X中,那么,先走選手總有X中奇數(shù)條兩人都未走過的邊可選擇.因游戲必有終止,故先走選手有必勝策略.例6.對放置于點A1,A2,An(n3)及點O處的卡片做如下操作:(1)若某Ai處卡片不少于3張,則從中取3張,在Ai-1,Ai+1,O各放一張(An+i=Ai);(2)若O處的卡片不少于n張,則從中取出n張,在A1,A2,An各放一張.證明:只要放置在這n+1個點