高一數(shù)學聯(lián)賽輔導5179寒假講義上

第一講組合計數(shù)的學科.解決競賽中的組合數(shù)學問題往往不需要太多專門的知識求深刻的洞察能力和強大的化歸、轉化能力.IMO中，最后的勝者往往是成功從本講開，用七講對組合學做一大的勾勒.通這七講學習，到以下的：1掌握聯(lián)賽一二試組合問題的特點與解法；2、對組合數(shù)學這門學科有一個初步的認識，為進一步學習打下基礎；3七講內(nèi)容分別為：一、組合計數(shù)（1）比高考略難的基本計數(shù)問題 1n1n類分別有m1m2mnnn法，則總共完成這件事有mim1m2mn種方法n1n步分別有m1m2mnnn完成這件事有mim1m2mn種方法.易于計數(shù)2

nn(n1(n2...21nnnnmAm（部Pm，由乘法原理得到nnnAmn

(n

n(n1)...(nmnn n(n1)...(nm (nm)!Cn(nm)! nm個元素排成一列，不同的排列種數(shù)有nm有限個重復元素的全排列：設n個元素由ka1a2akn1n2nk（nn...

n，那么這n個元素的全排列數(shù)

n!n!...n nmnm（i）（ii）（iii）同或者元素雖然相同，但元間的順序不同，才是不同的圓排列．AmAAa1a2a3an}的nmnm板塊一本的加法、乘法原理，以及枚舉方法來計數(shù).這主要是考慮到有一部分參加聯(lián)賽的同學并過專業(yè)的競賽訓練.雖然如此，這部分計數(shù)問題枚舉起來往往分類復雜，需要仔細.【例1 C. （2）B前排中間的3個座位不能坐，有排法A2，其中相鄰的分三類，排的其中的4個座位有3A2；則符合 件的排法種數(shù)中A23A23A211A2=346，故選 11A2=11011346【例2（1）36【解析】（1）900003前四位除以3余21,4,7931749630000-17496=12504個（2）顯然全部子集數(shù)為2100個，不包含任何奇數(shù)的子集即{24,6,...,98,100}的子集共有250個，故所求子集個數(shù)為2100250個.(n元集合子集數(shù)為2n個)【例3ABCDEFA處，它每次可隨意地跳到相鄰兩頂點之一．若5D5D5次也停止跳動，那么這只青蛙從開始到停止，可能出現(xiàn)的不同跳法共種1，2,4次到達D點，于是青蛙的跳法只有以下兩種：3D253次有232種，后兩次有222426種跳法注1997【例4】從給定的六種不同顏色中選用若干種顏色，將一個正方體的六個面染色，每面恰染一種顏色，每兩個具有公共棱的面染成不同的顏色。則不同的染色方法共有 種（注：如果我們5555種6565種顏色有C5種方法，這時必有一組對面同色.565取一種顏色染一組對面，并將它們朝上和朝下，有C14種顏色染四個側面（45顏色的鏈排列）13！種方法.所以不同的染色方案有C5C113!90種 56644余兩種顏色染四個側面且使兩組對面同色（應是兩種不同顏色的鏈排列1種方法.所以不同的染色方案有C4C2190種. 6363種顏色有C3661種方法.所以不同的染色方案有C3120種.6注本題為1996年聯(lián)賽試題是來一試計數(shù)問題中最復雜的一道其背景與群論計數(shù)原理有關，【例5】將24個名額分配給3個學校，則每校至少有一個名額且各校名額互不相同的分配方法共 ||43||||若把每個“”與每個“|”都視為一個位置，由于左右兩端必須是“｜”，故不同的分配方法相當于24226個位置（兩端不在內(nèi)）2個“｜”占領的一種“占位法“每校至少有一個名額的分法”24個”232個空隙插入“｜”C2253C又在“每校至少有一個名額的分法”中“至少有兩個學校的名額數(shù)相同”31種．253－31＝222種． x1x2x324x1x2x321321個元素的可HCHC

又在“每校至少有一個名額的分法”中“至少有兩個學校的名額數(shù)相同”31種．253－31＝222種2008【例6】將2個a和2個b共4個字母填在44方格表內(nèi)，每個小方格內(nèi)至多填1個字母，若使相同字 b72種；2a1bC1A2=16×72722?72?16×72=396016200712【例7】設三位數(shù)nabc，若以a，b，c為三條邊的長可以構成一個等腰（含等邊）三角形，則這樣的三位數(shù)n有（ A.45 B.81 C.165 D.216a，b，c0。即a,bc{1nnC19 99必須滿足ba2ba987654321b1111203同時，每個數(shù)碼組（a，b）中的二個數(shù)碼填上三個數(shù)位，有C23nC2(2C2206(C210156。nnn165 2004板塊二

N.N的元素個數(shù).【例8】（1）試用對應方法證明可重組合：從n個不同元素中，任意可重復地選取m個元素，稱nm（2）xx

n（k,n為正整數(shù)）的非負整數(shù)解組數(shù)為

【解析】（1）設n個元素為12n，并設取出的m個元素為1a1a2amn，于是1a10a21amm1nm1(a1a2ama10a21amm1后者為從nm1m

（2）nk-1個豎線排成一排，k-1n個圓圈依次分成k個部分：x1x2xk，n+k-1k-1個的全排列數(shù)為列數(shù)為

，故得證】【解析】任一形內(nèi)交點對應兩條對角線l,m;P,P（l,m）2頂點，n4頂點即可唯一確定兩對角線，于P(lm)(A,B,C,D)nn注本題為組合數(shù)學一個重要分支——組合幾何中的非常重要的一個結論，可以利用它解決一些高難度的n個元素排成一行依次為為12nk個元素為1i1i2ikn，顯然有2ij1ij(j12k1；

1i1i21i32ikk1nk1(i1i21i32,...,ikk11,2，n-k+1中的一個嚴格上升的序列作對應(i1i2,...,ik)(i1i21i32,...,ikk1，易證明它為一一對應，且后者的種數(shù)為從nk1個元素中取k

16（1）100631C1C B．C1C6 6

D．D．（2）從4名男生和3名中選出4人參加某個座談會，若這4人中必須既有男生又有，A.140 C35 【解析】（1）C3件產(chǎn)品有C3種方法，其中無次品有C31件次品的方法數(shù)為

C3

（2）D既有又有男生，可以分類表示，三男一女有C3C1種選法，二男二女有C2C2種 4一男三女有C1C3種選法，則總的不同的選法有C3C1C3C2C1C3=34( 由三個數(shù)字12、3組成的5位數(shù)中,1、2、3都至少出現(xiàn)1 【解析】在5位數(shù)中,若1只出現(xiàn)1

C1(C1C2C370 若1

C2(C1C260若1只出現(xiàn)3

C3C1

15015055對ab的個數(shù)為 D. 【答】 1b【解析】由5xa0xa；6xb0xb。要使ABN2,3,4，則 ， 4 6b20a

。所以數(shù)對ab共有C1C130

66 aT,

2005

5

6

5p p

6

1

0

1

0 【解析】用

]k位p進制數(shù)，將集合M中的每個數(shù)乘以74M{a73a72a7a|aT,i1,2,3,4}{[aaaa]|aT,i1,2,3, 1234 M中的最大數(shù)為[6666]72400]10而

,將此數(shù)除以74M1

0

4.C2005A={a1,a2,…,a100}B={b1,b2,…,b50}ABfB中每個元素

C50

50

49CC

49CCb1<b2<…<b50A中元素a1a2,a10050f：A→B，i組的元素在fbi(i=1,2,…,50)，易知這樣的f滿足題設要求，每個這樣的分fA50組的CCA的分法數(shù)為C49，則這樣的映射共有C49D 注本題為2002 聯(lián)賽試在賽前，F(xiàn)國為了A1,A2,…,A7這七名，準備讓他們在三場訓練比賽(每場90分鐘)A1,A2,A3,A4每人上場 7|xi(1≤i≤4)13|xj(5≤j≤7)下的正整數(shù)解的級數(shù)。 xi xj ∴m,n 在條件m≥4且n≥3下的一組正整數(shù)解 10∵7(m-4)+13(n-令m′=m n′=n3 m≥4n≥3 即 n0=203是③的整數(shù)m′=406 n′= 令 n′≥0,解得 20mn

mn

mnmn

m

mn

xi=7yi(i=1,2,3,4)，于是由不定方程y1+y2+y3+y4=33有

34960∴此時①有滿足條件的C3=4960 y1+y2+y3+y4=20，有C3y5+y6+y7=10，有C2 ∴此時①有滿足條件的C3C2=34884 由y1+y2+y3+y4=7，有C3組正整數(shù)解；以及y5+y6+y7=17，有C2組正整數(shù)解 40 5020028

第二講組合計數(shù) 二項式定理(xy)nCkxnkyk(1x)nCkxk，其中nN特征方程與數(shù)列通項

k

kaaa,...為數(shù)列{a}

qan1x2pxq

（1）當有兩互異實根時，數(shù)列通項為anxx （2）當有二等根時，數(shù)列通項為ann)1n1其中板塊一算兩次是一種非常重要的思想方法，在代數(shù)、組合、幾何中都有涉及.組合問題中，組合極值、組合不等式也常常涉及到算兩次.組合計數(shù)中，在直接計算非常復雜甚至無從入手時，我們常常利用算兩次方我們就得到一個等式，當為估計式時，我們就得到一個不等式.事實上，數(shù)學中有相當大一部分定理就是 【例11】a1a2,…an1，2，…，nfk是集合aiaiak,ikgk是集合aiaiak,ik元素的個數(shù)（k12,…n，證明fkgk k k 【解析】考慮集合S(aiakaiak,ikS。一方面，固定k先對i求和，然后再對k

fk；另一方面，固定i先對k求和，然后再對i

gigkn kn 所以得fkgk

kk k注本題只是為了說明算兩次的基本思想和方法，這里的計數(shù)是抽象的，這種方法相當于考慮各個分量對【例12】nn（1）S，Sn=8S28C2，于是猜想對一般情形總有SC2n 本題構造了一種巧妙的對應，使原來無法下手的問題變得有章可循.事實上，組合問題，特別是算兩次【解析】設一共連有l(wèi)k個三角形 一方面，所得k個三角形的內(nèi)角和為k

個內(nèi)點及

，從而算得k3k條邊，另一方面，每條線段是兩個三角形的公共邊，1次，共2l4條邊，從而2l43k，得到l3001注本題的背景是計算機圖形學中著名的三角面片分劃問題，這類問題在馮的有限元中也有應用.【例14】（選講）1,1,2,2,3,3，…，1986,1986112219861986【解析】設能將上述數(shù)字排成一行滿足題設，這是每一個數(shù)i(1i1986可賦予它一對有序實數(shù)(xi,yi)作為坐標，這里坐標值分別為它第一次與第二次出現(xiàn)的位置序號.yixii1.

k

k1986(219861i，兩坐標和為2xii1 為奇數(shù) 本題為第二屆冬令營的一道很難的問題,方法較多，上面給出的方法是一個很巧妙的解法，利用奇偶性板塊二當所計數(shù)對象按從1到n有規(guī)律出現(xiàn)時，可視之為一個數(shù)列并其相鄰項之間關系，得到遞推關系【例15】（Fibonacci）假設一對兔子每隔一月生一對小兔，每對小兔兩個月后也逐月生一對小兔，ann個月初的小兔對數(shù)，易得到a11a22a3一般地，第nn-1n個月初出生的小兔對數(shù)，即得到遞推式anan1an2，由特征方程的結論及初值，可得到a13377a

5

1

( 【例16】1,2,3n1【解析】設有an個，顯然a13a28141232an2個，得到遞推式an2an12an2n314an

3)n2

3)n2注板塊三n【例17】rst為整數(shù)，集合{a|a2r2s2t,0tsr中的數(shù)由小到大組成數(shù)列{an

2rst為整數(shù)且0tsrr2，此時符合條件的數(shù)有C223r3st可在0,1,2中取，符合條件有的數(shù)有C234r4時，符合條件有的數(shù)有C245r5時，符合條件有的數(shù)有C256r6時，符合條件有的數(shù)有C267r7時，符合條件有的數(shù)有C27a36r7

20

27注本題為2005年 預賽題，事實上此題源自2003年高考理科試卷壓軸題，用二進制方法求解最 《2003年高考理科數(shù)學壓軸題的一種巧妙解法及其推廣》中學教研2003.12【例18】如果自然數(shù)a的各位數(shù)字之和等于7，那么稱a為“吉祥數(shù)”.將所有“吉祥數(shù)”從小到大排成一列a1,a2,a3,,若an2005,則a5n .mk∵方程x1x2xkm的非負整數(shù)解的個數(shù)為Cm .而使x11,xi0(imk數(shù)為數(shù)為

m7kP(k)C6.kk∵2005是形如2abcP(1)C61P(2)C67,P(3)C6 對于四位“吉祥數(shù)”1abc，其個數(shù)為滿足abc6的非負整數(shù)解個數(shù)，即∴20051+7+28+28+1＝65a652005從而n65,5n

P(4C684P(5

210而P(k5 5

k32552000，即a5n注1、本題為2005年聯(lián)賽試mx1x2xnmmx1x2xnm的正整數(shù)解的組數(shù)為Cn1

nm1【例19】若四位數(shù)nabcd的各位數(shù)碼a,bcd中，任三個數(shù)碼皆可構成一個三角形的三條邊長，則稱稱(a,b,c,d)為n的數(shù)碼組，則a,b,c,dM{1,2, ,9}.當數(shù)碼組只含一個值，為(a,a,a,a),a1, ,9，共得9個n值當數(shù)碼組恰含二個值a,b（ab9①數(shù)碼組為(a,a,a,b)型，則任取三個數(shù)碼皆可構成三角形，對于每個a ,9}，b可取a9個值，則數(shù)碼組個數(shù)為(a136(aaa,b)b4種占位方式，于是這種n364144②數(shù)碼組為(a,b,b,b型（ab，據(jù)構成三角形條件，有ba2bb123456789b Ma012343210共得16個數(shù)碼組，對于每組(a,b,b,ba有4種占位方式，于是這種n有164644③數(shù)碼組為(aa,b,b型（abba2b，同上得16個數(shù)碼組，對于每組(aa,b,b)，兩個a有C26種占位方式，于是這種n有16696個．4以上共計1446496304當數(shù)碼組恰含三個值a,b,c(abc①數(shù)碼組為(a,b,c,c型，據(jù)構成三角形條件，則有cba2c，這種(a,b,c,c有144a,bA212種占位方式，于是這種n有141216844②數(shù)碼組為(a,b,b,c)型，cbabc，此條件等價于M{1,2, 角形的方法數(shù)，有34組，每組中a,b有A212種占位方式，于是這種n有3412408個．44③數(shù)碼組為(aa,bccbabc，同情況②，有34A2408個n4以上共計168408408984個na,bcddcbacd，這種a,bcd有16組，每組有4得164384個n綜上，全部四位三角形數(shù)n的個數(shù)為93049843841681注教師備注 k分的有bk個（1k100Ma1a2anNb1b2b100，M,N的大小關系為？1k，于是得證.【解析】M.和為180x度，于是我們得到：180 901985又每個三角形都有三條邊，共有39723條邊，另一方面，每剪一次產(chǎn)生兩條三角形的邊，而四y2y+4條邊，由397232y4y140？4（3S1，因此S181；另一方面，14S1141或11的個數(shù)為偶數(shù)，由于12m,8m,6種顏色的11m2都是單色的,每種顏色的地磚都足夠多),要求相鄰(即有公共邊的)的兩塊地磚顏色不同,那么所有的不A.308

30257

30207

30217AB【解析】鋪第一列(兩塊地磚)有30種方法；其次鋪第二列．設第一列的兩格鋪了AAB兩色(如圖)，那么，第二列的上格不能鋪A色．若鋪B色，則有(6

鋪B

(6

種方法.于是第二列上共有21都有21種鋪法．因此，共有注2005

30

一次競賽有n(n2名選手參加，每天選手的得分恰好組成集合{12n}k天末，52分，求出使這件事成立的所有數(shù)對(nk)nn【解析】一方面，kkl

l1kn(n125226n，從而k(n152n3對.注本題為一個簡單的算兩次問題

11,a

3，

na

，

， （A）100個 （B）120個 （C）160個 （D）200個【解析】設三位數(shù)為abc，對a,b,c的可能取值進行分析abccba100(ac10(bb(acac不進位，則和數(shù)的十位數(shù)必為偶數(shù)，不符合題意，所以ac11，13，15，17.2211＝9＋2＝8＋3＝7＋4＝6＋5，所以ac取值有4A2種可能；13＝9＋4＝8＋5＝7＋6，所以ac取值有3A2種可能；22215＝9＋6＝8＋7，所以ac取值有2A22217＝9＋8，所以acA22由于bb不能進位，所以b 因此，滿足條件的數(shù)共有5(4A23A22A2A2)100 注本題為2007年廣西預賽試題.對于新定義題準確理解概念是關鍵本題以ac的可能取值為突破口，

的恒等式.事實上，歷史上出現(xiàn)過數(shù)以千計的組合恒等式，直到現(xiàn)在仍然有新的恒等式出現(xiàn).在大小叢(a(ab)C b(n knknk

Cranrbr(0rn它是展開式的第r+1項nnnCr(0rnnn（1）CkCnk(0knnnn

Ck1(0kn 若n是偶數(shù)，有C0C1 C2,C2 Cn1Cn，即中間一項的二項式系數(shù)C2最大

若n是奇數(shù)，有C0C1 C2,C

C2,C

Cn1CnnnnC2和

n

相等且最大C0C1C2Cn C0C2C4C1C3C5 kCknCk1或

nCk

CkCmCmCkm (mk

Cn

Cn1

nkn以上組合恒等式（是指組合數(shù)Cm滿足的恒等式）是證明一些較復雜的組合恒等式的基本工具n 例20】Ck2n(1)kCk02kCknknk knn【解析】由二項式定理(ab)nCkankbk(nnk

(1x)nCkxknknx【例21【例21】證明：（1）kCn nkCn

Cn1

nk 【解析】（1）由kCknCk1可 kCk nCk1n Ck1n

k

k

k

k

Cn1(Cn1C Cn1(Cn1Cn1)(Cn1Cn1) (Cn1Cn1) . CC

【例22【例22】kCnn nk【解析】首先求【解析】首先求k（k1)Cknk （n（n Cl

n(n1)2n2kn

k

nln又kCkn2n1nknn注類似地，我們還可以求得k3Cknn1)(nnnnC【例23】Ck

k22n12 k

Ckk0

Ckkn1

22nCkk

C2njC

Cnk

kn于是Ck1(22nCn22n1(n2 2k

2【例24】已知數(shù)列a0a1a2,(a00滿足ai1ai12ai(i1,2,3,p(x)aC0(1x)naC1x(1x)n1aC2x2(1x)n2 Cn1xn1(1x)aCn0 1 2

n1 nx的一次多項式或零次多項式ai1ai12ai知{anaiai1da0id(i1,2,p(x表示成a0和d的表達式，再化簡即可.因為ai1ai12ai(i1,2,3,,所以數(shù)列{an為等差數(shù)列，設其公差為有aia0id(i1,2,3,) 從P(x)aC0(1x)n(ad)C1x(1x)n1(a2d)C2x2(1x)n2(and)Cn0 a[C0(1x)nC1x(1x)n1Cnxn]d[1C1x(1x)n12C2x2(1x)n2nCnxn C0(1x)nC1x(1x)n1C2x2(1x)n2Cnxn[(1x)x]n n又因為kCkkn

k!(nk)!

n

(n(k1)![(n1)(k

從而C1x(1x)n12C2x21x)n2nCn nx[(1x)n1C1x(1x)n2xn1

P(x)a0當d0時P(x)為x的一次多項式，當d0時P(x)為零次多項式本題有一定的難度，運算量也很大，需要對二項式定理及常用組合恒等式相當熟練.建議選擇講授.n（1）n k （2）CkCt k(1)k(Ck)2 k【解析】考慮(1x)m1x)nxt一方面xt的系數(shù)即(1x)mn的系數(shù)，即另一方面，利用二項式定理將(1x)m1x)nxt的系數(shù)即為（2）式左邊，從而（2）式得證；在此式中令mnt即得（1）式.下證（3：利用(1x)n的展開式，考慮(1x)2n1x)2nx2n的系數(shù)：一方面(1x22nx2n另一方面(1x)2n1x)2nx2n注本題使用的方法即母函數(shù)方法，但母函數(shù)方法在聯(lián)賽中不要求，我們只舉此兩例，以供有的同學【例26】設nm，證明 Cmk

2nm kn一方面，先選定正式代表，有Cmn-m人中選列席代表，有2nmnn2nmCmnm+k人k0,12nm),k有Cmk

種選法，從而選法總數(shù)為Cmk

注本題采用了構造組合模型的方法.事實上，近年來組合恒等式內(nèi)容非常淺，聯(lián)賽中不會涉及到利用n 【例27】7CkCp2nn k n【解析】注意到CkCpCpCnk，于是CkCpCpCnkCp

2npCp n

np np kp kp l0【例28】（1）試求(xx2x3x46x15器，打算安排5個崗位配備這些新式，要求第一個和最后一個崗位不配備新式，且每相鄰5個崗位至少有一個崗位配備新式，相鄰兩個崗位不同時配備新式，問共有多少種配【解析】（1）由(xx2x3x46x61xx2x36x61x)61x26，知只須求(1x)61x26x9的系數(shù)。又(1x)6(1x2)6(16x15x220x315x46x5x6(16x215x420x615x86x10x9的系數(shù)為6×15＋20×20＋6×15＝1，2，…x1a1x2a2a1x3a3a2x4a4a3x5a5a4x620a5

其中2

x1x2x3x4x5x6

ykxk1(k1,2,3,4,5y6x6y1y2y3y4y5y6

問題（**）的解數(shù)等于(xx2x3x46x152005備選題備選題 求證：(1) 2nk

nk【分析】考慮到恒等式

2解決 【證明】令

(1) (1) ,2nk，k，

(1) (1) 2nkkn)22n(1)k22n2k)

k1k (1)k22n2kCkk令rk1

(1)k22n2kCk1kn(1)k22n2kCkn

(1)r122(n1)2rCr

k

r(1)

2(n1)rr2(n1)2r2(n1)r

rn令(1)k22n2kn

b,則

a k

(1) (1) k22n (1)k22n2k

Ck

)k2(n1)2(n1)

2nk

2nk

(1)j22(n1)2jCjj04an1于是由①式得bn1an1an2,從而推知anan14an1an1an2,即anan22an1.數(shù)碼a1,a2,a3 ,a2006中有奇數(shù)個9的2007位十進制數(shù) a2006的個數(shù)2

2

102006

102006

【答 【解析】（B）9A

92003 C20059

又由于(91)2006k

92006k以及(91)2006Ckk

(1)k92006kA

92005

nCkCn1knn k【解析】考慮(1x)n1x)nxn1xn1的系數(shù)即(1x)2n的系數(shù)，即Cn1另一方面，利用二項式定理將(1x)n1x)nxn1的系數(shù)即為原式左邊，從而得證；注6（2）的特例nnk

k

k C nCn(1)k k

k

Cnk數(shù)列

}

3an1(n2)，求 n的初值猜想an的特點與an2n=1時，a1=3a3a133274623a3

3273463(34

，因此

,

an4m3mN

n=k

4m3,mNn=k+1

34m3(4C

4m34T14(T1)

所以對任意正整數(shù)n，an4m3(m于是

故a2001注本題中利用初值得到規(guī)律進而猜想an4m3是問題解決的關鍵.已知a00a11an18anan1n

{an15【解析】數(shù)列

}x28x10

4

4

1所以anA(41

15)nB(4

a由00a

,B

則

[(4

15)n(4121212nn2k(k121212n12a12

[2C1n

4

T

本講講述組合數(shù)學中一個非常簡單卻又十分重要，應用十分廣泛的一個原理，即抽屜原理.然后給出與抽屜原理內(nèi)涵相通的幾個變形，即平均值原理與圖形原理.事實上這個原理用來證存在性題的有工之一，當我們還以利用原理反證法數(shù)學歸納法、算兩次、計數(shù)方法和構造法等等來加以證明.本講我們主要講述利用平均值原理（其在整數(shù)和圖形范內(nèi)的形分別為屜原理圖形原來證存在性題略舉數(shù)說明其方法在證m第一抽屜原理：若將m個物件放入n個抽屜中，則必有一個抽屜內(nèi)至少有 ]1個物件nm第二抽屜原理：若將m個物件放入n個抽屜中，則必有一個抽屜內(nèi)至多有 ]個物件n1：設aaaAa1a2...an，則aaa中必有一個不小于 也必有一個不大于2：設a1a2an為正實數(shù)，且G也必有一個不大于

na1a2...na1a2...圖 原理把面積為S1,S2,...,Sn的n個平面圖形以任意方式放入一個面積為S的平面圖形A內(nèi)S1S2SnSS1S2SnS，則必有一點不屬于上述n可以發(fā)現(xiàn)，上述三組原理都是性原則在不同場合的具體表現(xiàn)形式.性法則是處理組合數(shù)學中分割圖形、利用剩余類等等.與抽屜原理相關的試題中，聯(lián)賽中的題目往往利用抽屜原理是解題的關鍵，1995，并且每一個三角形的三個頂點同色。BiBjBk，于是BiBjBkAiAjAk即為所求注本題為1995年聯(lián)賽第4Si，Sj（i＜j，則100|SJSi100|ai1ai2...aj.命題得證。注本題所采用的這種利用連續(xù)項構造和式的方法非常經(jīng)典【例31】1-10051兩個數(shù)屬于同一個抽屜，即屬于（1）-（25）25注【例32】10AB，注【例33】試求最小的正整數(shù)n使得對于任何n77n13。對每個非負整數(shù)a稱如下10個數(shù)所構成的集合:Aa{10a,10a 10a9}為一“基本段akak連續(xù)數(shù)屬于三個基本段Aa1AaAaakakakak

akak

a1(a06)是屬于同一個基本段的7 aiai ai677

所求的最小值為n20051.5 25,791,10，49周周周周周周周1**2**3**4**5**B、C、D、E、FB、C、DB、CA、B、C 科學 2個B6之間的連線只染有黃藍兩色。B2，B3，B4，之間無黃線，則△B2，B3，B4，必為藍色三角形，命題仍然成立。 【解析】189023357,設給定自然數(shù)為aaa99個抽屜，必有兩9整除，不妨設為9|a10 同理可得到7|a8a75|a6a53|a4a3，最后，若a1a2中有一個為偶，那么2|a1a22|a2a15內(nèi)不能安排該球隊的客場比賽。如果4能夠完成全部比賽，求n的最大值。6**容易驗證，按照表中的安排，66**

E

i,發(fā)生

i

i,j{12,34,5}，SiSjABC或DEF，必有SiSjSj所以，n注本題為第一屆東南數(shù)學第7題.本題是一道組合極值問題組合極值的構造與論證難度一般都

此時，旋轉圓2，其中有50次與點A顏色相同，任取其中一點B,固定圓2，再旋轉圓3，如此下 次，共出現(xiàn)同色四點組(A,B,C,D)有 50個，

12.5根據(jù)平均值原理，必在某次旋轉后存在n12.5n13條射線，它們中每一條穿過四點同色（a1，2，a3a2，3，a4a3，4，a5…,（a9，10a1）,（10，1，a2）11.2121于.2(1BC△ABC，P，M△ABC（包括邊界）PMPAB、BCMACP、Q、N，那么BC≥AB，所以∠A≥∠C，則∠QNP≥∠PQN，而∠QMP≥∠QNP≥∠PQN（三角形的外角大于不相鄰的內(nèi)角，所以PQ≥PM。顯然BC≥PQBC≥PM.12整除6p，只須證明：34pa，b，c，d3a，b，c，d23a，b3b-a3a，bc，db-a為偶數(shù)，d-c4可整除(b-a)(d-c)4p.8【解析】在一條直線上取點OO78814，15

第五講容斥原理與性原計數(shù)來實現(xiàn)對整體的計數(shù)是一種明智的選擇.XA1，A2，…AnXA1A2An.集合A1A2,An}X全）劃分.如XX的計數(shù)可通過熟知的加法|X||A1||A2||A3||An進行，但是，要找到一個劃分并且其中所有子集易于計數(shù)的有時并非易事.相對補集：稱屬于ABB對A的相對補集或差集，記作A-AAnA1A2An1Ai(i1,2,n)為有限集,nn|n

||Ai|

|Ai

i|(1)n1|Ai

n 定理 設Ai(i1,2,,n)為有限集I的子集，則|Ai||Ai||I||Ai

n|I||Ai|n

|Ai

i|(1)n|Ai

而性原理則是一種非常重要的數(shù)學思想.從問題的情況考慮，對于數(shù)值問題來說，就是指取板塊一【解析】（1）設S1＝{a∣1≤3≤120,2∣a}；S2＝{b∣1≤b≤120,3∣b}；S3＝{c∣1≤3≤120,5∣c}；S4={d∣([n]n的整數(shù)部分，例如[2,4]＝2，…)card(S1∩S4)－card(S2∩S3)－card(S2∩S4)－card(S3∩S4)＋card(S1∩S2∩S3)＋card(S1∩S2∩S4)＋card(S1∩S3∩S4)＋card(S2∩S3∩S4)－card(S1∩S2∩S3∩S4)＝(60＋40＋24＋∵2，3，5，712089card(A)AA 則|A|=21|B|=194148人之間。411310512人之間。注對于基礎較好的同學，此題可不講ABABC。最后再說明有A、B、CDA、B、C、D就是找的人了。證明：一個人AB.即C與A和B均合作過 分別表示與A、B合作過的人的集合。同樣地。所以存在。則A、B、C、D就是所求，證畢。注本題為一道典型的圖論問題，我們用容斥原理的方法來解決它【解析】首先計算S12,...,105}105Aim|mSi|m}是 A7105105][是 A7105

]48 57 35710548105互素，而1000482040，所以a1000a40，a48104a47103101,97,94,92,89,88,86知a1000a40=861994【例43】一個人寫了nnn封信都裝錯了信封，問這樣的裝法n1，2，…，nn個不同元素的排列1°i(i=1，2，…，n)iii2°n個不同元素的一個錯排(若每個元素都在原位則稱為按照上面約定，“裝錯信封問題”n個不同元素的錯排問題，則可構建“裝錯信封問題”的數(shù)學模型n個不同元素的全排列中，有多少種不同的錯排？SAjj在原位的所有排列所構成的集合，|S|=n|Ai|=(n－1)|Ai∩Aj|=(n－2)…，AA|j AniD|S||A|| n!C1(n1)!C2(n2)!C3(n3)!...(1)nCn( n!(1 ... 注本題為“裝錯信封問題”，是由著名數(shù)學家·(JohannBernoulli，1667－1748)的兒子·伯努利(DanidBernoulli，1700－1782)提出來的，是一道典型的利用容斥原理或遞推方法來解決的問題. ,x2n)具有性質P是指：存在屬于集合{1,2,....,2n1}使得|xixi1|n。求證，對于任何nPP的排.P的排列的集合，顯然|A||B|1為了|A||B|

|B

2

(x1x2 ,x2nkk

Akk

|Ak|22n1（kknAk2n1個元素的全排列，另外kkn可互換位置。即得|Ak|22n1同理|AA|222n2)!,1k,jnkn nn則|B||Ak||n

k 【例45】8×816464個數(shù)。問：是否一定能夠找到兩個相鄰4？【解析】考慮這個方格棋盤的左上角、右上角及右下角內(nèi)的數(shù)A，B，S設存在一個填數(shù)方案，使任意相鄰兩格中的數(shù)的差不大于4，考慮最大和最?。ˋ=1，S=644，的位置上。顯然，164164之間的距離更近了，更要導致如上的矛44。A，B，C，使得AB，BC，C【解析】從情況觀察入手，設B是勝的次數(shù)最多的一個選手，但因B沒獲全勝，故必有選手A勝B。BAC，否則，ABB是A，B，C，使得AB，BC，C勝A3（假設認識是相互的）33nA，他認識其他兩所學校中某一所學校的人數(shù)是最多的，這個最大值為kn.Ak3

n1k1An-kc認識第一所學校的學生人數(shù)至少為n1(nk)k1，此與k的最大性假同H為可去選手。我們的問題就是要證明存在可去選手。A一個（C）A賽過。C不是可去選手，故存在選手D，E，其中DCECEEC賽過，因而選手EA。AED1A是已賽過對手最多的選手。 A3 A3 6!C125!C2224!C3233!=240 【解析 A333,333200,配備新式的方案？12…20 設置的序號為ak(k1,2,3,4,5)x1a1x2a2a1x3a3a2x4a4a3x5a5a4x620a5其中2

x1x2x3x4x5x6

y1y2y3y4y5y6

A為不定方程（2）Ak(k1,2,3,4,5,6A

yi4y

4，

（2，

Ak6 6