上海中學(xué)顧濱

數(shù)學(xué)競(jìng)賽專題講座―組合雜題初步上海中學(xué)(200231)

顧濱組合問(wèn)題是數(shù)學(xué)競(jìng)賽中的熱點(diǎn)問(wèn)題，通常也是難度很高的問(wèn)題．組合問(wèn)題內(nèi)容非常廣泛，涉及代數(shù)，幾何以及數(shù)論等多個(gè)數(shù)學(xué)分支．組合問(wèn)題中常見(jiàn)的問(wèn)題有：組合計(jì)數(shù)；組合最值；組合幾何；組合數(shù)論，圖論等，其用到的重要原理一般有：抽屜原理；容斥原理；算二次原理；平均數(shù)原理；最大(小)數(shù)原理．組合計(jì)數(shù)問(wèn)題常見(jiàn)處理方法有：枚舉法；映射法；算二次法；遞推法；母函數(shù)法等；組合最值問(wèn)題常見(jiàn)處理方法：估計(jì)法；組合分析法；局部調(diào)整法；歸納法；計(jì)數(shù)法等；組合幾何問(wèn)題常見(jiàn)處理方法：利用凸集；染色賦值法；利用海萊定理,圖蘭定理等；利用覆蓋和嵌入法等．下面，我們來(lái)看幾個(gè)組合問(wèn)題中典型問(wèn)題：有兩位棋手在一個(gè)無(wú)限大的平面上對(duì)局，棋子共有51個(gè)，其中只有1匹狼，50只羊.第一位棋手開(kāi)局移動(dòng)狼，然后第二位棋手移動(dòng)一只羊，接著第一位棋手再移動(dòng)狼，然后第二位棋手再移動(dòng)羊，如此下去.若規(guī)定狼和羊每次移動(dòng)可沿任意方向且距離不超過(guò)1米，試問(wèn)：是否有一種初始擺法，使得狼永遠(yuǎn)抓不住羊？解：有.在平面上，以米為單位，建立直角坐標(biāo)系xoy，把50只羊分別放于50條直線：y=3,y=6,y=9,…,y=3x50上，使得每條直線上僅有一只羊，而且開(kāi)始時(shí)，沒(méi)有一只羊距離狼的距離在1米之內(nèi).由于狼一步至多移動(dòng)1米，但是任意兩只羊之間的距離都大于等于3米，從而，在同一時(shí)刻，狼至多只威脅到一只羊，在一對(duì)一的情況下，羊沿著直線運(yùn)動(dòng)，那么狼不可能抓住羊.是否存在空間中的5個(gè)點(diǎn)，使得對(duì)所有的ne{1,2,…,10}，存在兩個(gè)點(diǎn)，它們之間的距離等于n?解：不存在.假設(shè)存在這樣滿足題意的空間5個(gè)點(diǎn)，那么它們之間有 C2=10個(gè)距離，且距離值51,2,..?10僅出現(xiàn)一次，設(shè)XY=1,且Z是任意一點(diǎn)，不失一般性，有XZ>YZ(等號(hào)不可能取到，上面已經(jīng)說(shuō)明)，因此在AXYZ中，由三邊關(guān)系：XZ<XY+YZn0<XZ-YZ<XY=1，因?yàn)閄Z,YZ都是整數(shù)，所以XZ=YZ+1，由此可得X,YZ三點(diǎn)共線，進(jìn)而推得這樣的5個(gè)點(diǎn)，如果存在，必定共線.接下去，不失一般性，若存在5個(gè)點(diǎn)共線，依次為A,B,C,D,E，且AE=10,則這10個(gè)距離是：S=AB+(AB+BC)+(AB+BC+CD)+10+BC+(BC+CD)+(10—AB)+CD+(10—AB—BC)+(10—AB—BC—CD)=40+2BC+2CD所以，S為偶數(shù)，但是1+2+…+10=55為奇數(shù)，矛盾！故不存在.24是否存在兩個(gè)無(wú)差別的骰子，使得這兩個(gè)骰子點(diǎn)數(shù)之和j(2<j<⑵的出現(xiàn)概率是(三，土)之間的3333數(shù)？解：設(shè)a是第一個(gè)骰子出現(xiàn)n的概率，其中ne{1,2,…6};b是第二個(gè)骰子出現(xiàn)n的概率，其中nnne{1,2,…6};s是兩個(gè)骰子之和出現(xiàn)n的概率，其中ne{1,2,…6}.n24若ab+ab>2ab，則s>2s，這與s,s在(—,)矛盾！所以有0<ab+ab<2ab①；16 61 11 7 2 2 7 3333 16 61 1124若ab+ab>2ab，則s>2s，這與s,s在(—,)矛盾！所以有0<ab+ab<2ab②；16 61 66 7 12 7 12 3333 16 61 66由①X②可得(ab+ab)2<4ababo(ab-ab)2<0，這是不可能的?故不存在這樣的兩個(gè)骰子1661116616612/7滿足題意.設(shè)n是能夠被4整除的正整數(shù)，在集合｛1,2,…,n｝上，計(jì)算雙射f的個(gè)數(shù)，使得f(j)+f1(j)=n1,j…2.,n解：假設(shè)j=f(x)，則f(f(x))=n+t(注意既然n為偶數(shù)，則f(x)工x)，所以存在y=f(x)，在我們用函數(shù)迭代時(shí)候，4個(gè)數(shù)將形成循環(huán)：x,y,n+1-x,n+1-y，x,y,n+1-x,n+1-y,…，在每個(gè)循環(huán)中，這4個(gè)數(shù)均不同且恰有2個(gè)在集合｛1,2,…，n｝中,所以共有(--1)(--3)…3-1種方法構(gòu)成數(shù)222n組(x,y)且每一組數(shù)將導(dǎo)致2個(gè)循環(huán)：(x,y,n+1-x,n+1-y)或者(x,n+1-y,n+1-x,y)，因而原問(wèn)4題結(jié)果為[(-1)( 題結(jié)果為[(-1)( -3)…3-1]-2422nn由于(一—1)( -3)…3-1=22nn(一)！ ()!丄故化簡(jiǎn)后值為丄

nn()!()!44n24.設(shè)F是所有下列函數(shù)f構(gòu)成的集合：f:P(S)TR，使得對(duì)所有的X,Y匸P(S)f(XcY)=minfXCfY，這里S是一個(gè)有限集，P(S)是S的子集族，試求：max|lm(f)|，其中Im(f)表示f的像集.定義f如下:對(duì)每一個(gè)A匸S，若n纟A，n解：max|lm(f)|=n+1定義f如下:對(duì)每一個(gè)A匸S，若n纟A，nnfeF則令f(A)則令f(A)=1n+1若neA而n一1纟A，貝I」令f(A)=丄；n一般地，若n,n-1,…，keA，而k-1纟A，則令f(A)=，則f是P(S)tR的一個(gè)映射，且對(duì)kX,YeP(S)，設(shè)n,n-1…， E Xc，而k-1纟(XcY) (k=1,2,…,n+1)，貝有n,n-1…，E X且,Y-1不同時(shí)屬于X,Y，于是，由f的定義方式知：f(X),f(Y)>1至少有一個(gè)取kTOC\o"1-5"\h\z等號(hào)，而 f(x c Y)=丄，故f( Xc Y= mi nf( X( f, Y現(xiàn)在有Imf(|=)n + ，1即kma|kmf(|=)n+ . 1fEF設(shè)邊長(zhǎng)為1的正六邊形的六個(gè)頂點(diǎn)為P,P，…,P，在其形內(nèi)(包括邊界)任放置兩個(gè)不同的點(diǎn)P,P，1 2 6 7 8求：minPP的最小值.1<i<j<81 7解：如圖所示.可以以P為圓心，x為半徑作圓弧，則在形內(nèi)將圍成一

P1個(gè)曲邊六邊形ABCDEF.當(dāng)x于曲邊六邊形"直徑”BE相等時(shí)，有P1x+2'x2—(丄)2仝，解得x二E一'；3.若把x+2'x2x<1，所以minPP=衛(wèi)=?若否,Zx<1，所以minPP=衛(wèi)=?若否,Zj1<i<j<8存在P,P，使得minPP>x，從而PP>x，因?yàn)榍匒BCDEF直徑7 8 ij1<i<j<8為x,所以，P,P中，至少有一個(gè)，不妨設(shè)為P，不在曲邊六邊形形內(nèi)，但P在正六邊形P,P，…,P形TOC\o"1-5"\h\z7 8 7 7 1 2 6內(nèi)或者邊界上.所以P必在以P(i=1,2,…』)為圓心，x為半徑的某個(gè)圓P內(nèi)，不妨設(shè)P在圓P內(nèi)，則7 i i 7 1有PP<x與minPP〉x矛盾！1 7 ij31<i<j<83綜上所述,minPP1<i<j<87.設(shè)集合S={1,2,…,50}，X是S的任意子集，且|X|二n.求最小的正整數(shù)n,使得X中必有三個(gè)數(shù)為直角三角形的三邊長(zhǎng).解：設(shè)直角三角形三邊長(zhǎng)分別為x,y,z，有x2+y2=z2，其正整數(shù)解可表示為：x=k(a2—b2)，y=2kab，z=k(a2+b2)①，其中a,b,keN*,(a,b)=1,a>b，則x,y,z中必有一個(gè)為5的倍數(shù).若否，則a,b,c都是5m土1,5m土2型的數(shù)，meN，所以有a2三土1(mod5);b2三土1(mod5)，c2三土1(mod5)，而c2=a2+b2三0,土2，矛盾！令集合A={S中所有與5互質(zhì)的數(shù)}，則|a|=40,若以10,15,25,40,45分別作直角三角形的某邊長(zhǎng),則由①知A中找到相應(yīng)的邊構(gòu)成如下直角三角形：(10,8,6);(26,24,10);(15,12,9);(42,27,36);(39,36,15);(25,24,7);(40,32,24);(41,40,9);(42,27,36)，此外，A中再?zèng)]有能與10,15,25,40,45構(gòu)成直角三角形的三條邊.令M=Au{10,15,25,40,45}\{8,9,24,36}，則|m|=41，有上知A中數(shù)不能夠成直角三角形，故n>42。下面我們來(lái)構(gòu)造例子：由①知B={3,4,5;15,17,18;29,21,20;25,24,7;34,16,30;37,35,12;50,48,14;41,40,9;45,36,27}可滿足，所以B=27，|s\B=50-27=23，在S中任取42個(gè)數(shù)，由于42-23=19，所取42個(gè)數(shù)中必有含有B中的19個(gè)數(shù)，所以，B中至少有B中一組數(shù)，出現(xiàn)在所選的42個(gè)數(shù)中，即任取42個(gè)數(shù)，滿足題意。綜上所述,n=42.min把一個(gè)nxn的正方形分割成n2個(gè)小正方形.若可選出n個(gè)1x1的小正方形予以標(biāo)號(hào)，使得對(duì)一個(gè)

解：n =7例子如下：maxpxq(pq>n)的矩形(其邊界或?yàn)樵叫蔚倪吔缁驗(yàn)榉指罹€)內(nèi)至少包含一個(gè)標(biāo)號(hào)的1x解：n =7例子如下：max下面假設(shè)n>8.考察每一行的1xn矩形，由題意知每行中至少包含一個(gè)含標(biāo)號(hào)的方格，又總方格數(shù)為n,故每行中恰有一個(gè)含標(biāo)號(hào)的方格，每列亦同.設(shè)第1行的標(biāo)號(hào)方格位于第k列(1<k<n),由于可將方格翻折，故可設(shè)k<"+1—k即k<?.下面分兩種情況22討論：Yr . n+ 1 一(1)若n=2m(m>4)而k<nk<m?設(shè)第k+1列的標(biāo)號(hào)2方格位于第j行(1<j<2m).若j<m，則第m+1行到第2m行及第k列第k+1列構(gòu)成的2xm矩形中無(wú)標(biāo)號(hào)方格(已證每行每列恰有1個(gè)方格),矛盾！;若j>m+2，則考察第2行到第n+1行及第k列第k+1列的2xm矩形，同理可知矛盾！故必有j=m+1.再設(shè)，第k+2列的標(biāo)號(hào)方格位于第l行，因?yàn)閙>4，所以k+2<m+2<2m?若l<m+1，則第m+2到2m行及第k列到第k+2列的3xm矩形中，無(wú)標(biāo)號(hào)方格，而m>4時(shí)3x(m一1)>2m，矛盾！若l>m+1，同理考察第2行到第m行及第k列到第k+2列知矛盾！綜上，n>8得偶數(shù)不符合題意;n+1(2)若n=2m+1(m>4),而k< =m+1，同理定義j,l可知j=m+1或m+2(考察2x(m+1)2的矩形，進(jìn)一-步考察3x(m-1)的矩形，由l知矛盾！)且當(dāng)m>4時(shí)，有3(m-1)>2m，因此n>9為奇數(shù)也不符合題意。綜上所述，由(1)(2)知n>8的正整數(shù)均不符合題意，故n =7?max求滿足如下條件的最小正整數(shù)n:在圓O的圓周上任取個(gè)點(diǎn)A,A, ,A，則在C2個(gè)角1 2 n nZAOA(1<i<j<n)中，至少有2007個(gè)角不超過(guò)120。ij解首先，當(dāng)n=90時(shí)，如圖，設(shè)AB是00的直徑，在點(diǎn)A和B的附近分別取45個(gè)點(diǎn)?此時(shí)只有2C2=198045個(gè)角不超過(guò)120°,所以不滿足題意;當(dāng)n=91時(shí)，下面證明至少有2007個(gè)角不超過(guò)120。.對(duì)圓周上的91個(gè)點(diǎn)，若則連.這樣就得到一個(gè)圓?設(shè)圓中條邊，因?yàn)閆AOA>120。，ZAOA<120。時(shí)，ZAOA<1200，所以圓G中沒(méi)有三角形.ij ik ik

若e=0,則有C2=4095>2007個(gè)角不超過(guò)120，命題得證；91若e》，不妨設(shè)A]、A2之間有邊相連，因?yàn)閳D中沒(méi)有三角形，所以對(duì)于點(diǎn)A(3<i<91)，它至多于ApiA中的一個(gè)有邊相連，所以，d(A)+d(A)<89+2=91，其中d(A)表示從A處引出的邊數(shù).212因?yàn)閐(A)+d(A+??d(A=),2而對(duì)圖G中每一條邊的兩個(gè)頂點(diǎn)A,A，都有TOC\o"1-5"\h\z1 2 91 ijd(A)+dA<) ,9于是上式對(duì)每一條邊求和可得ij(d(A))2+(d(A))2+…+(d(A))2<91e，1 2 91由柯西不等式可得：91[(d(A))2+(d(A))2+…+(d(A))2]>[d(A)+d(A)+…+d(A)]2=4e2，1 2 91 1 2 914e2 912所以<(d(A))2+(d(A))2+…+(d(A))2=91e，即e< <200791 1 2 91 4故91個(gè)頂點(diǎn)中，至少有C2-2071=2024>2007個(gè)點(diǎn)對(duì)，它們之間沒(méi)有邊相連，從而對(duì)應(yīng)的頂點(diǎn)91所對(duì)應(yīng)的角不超過(guò)120°.綜上所述，n的最小值為91.另解：前面部分相同，下僅證明n=91.不妨設(shè)x<y<z.如圖所示，下面分情況討論:y個(gè)點(diǎn)①y個(gè)點(diǎn)①若x=0，1則滿足：不超過(guò)120°的角1至少有C2+C2=y2+z2y+zy卡z291-91，所以，由柯西不等式得yz2222(y+z)291C2+C2>=2024.75>2007；yz42② 若x>1，則AAAA中，ZAOA,ZAOA,ZAOA中必有一個(gè)ijk ij ik jk角不超過(guò)120。(平均數(shù)原理)，而A,A分別取遍各自區(qū)域段中的點(diǎn)，故ij這樣產(chǎn)生的不超過(guò)120°的角至少有C2+C2+C2(x(x+y+z)2391最后一行- =2714.8>2007最后一行2的不等式成立是因?yàn)榭挛鞑坏仁?，故?dāng)n>91時(shí)，總可滿足題意，從而n的最小值為91練習(xí)題1.能否將正整數(shù)1至20022填寫到一個(gè)2002x2002的方格表中，使得對(duì)任何一個(gè)方格，或者可以從它所在的行中，或者可以從它所在的列中找出三個(gè)數(shù)，其中兩個(gè)數(shù)的乘積等于第三個(gè)數(shù)？解：不能.理由如下：數(shù)1至2001至多分布在2001行和2001列中，因此必可找到一行和一列，其中所填的數(shù)全都不小于2002.于是該行(該列)的任何兩數(shù)的乘積都大于20022，從而對(duì)于位于該行與該列相交處的方格，題中的條件不可能滿足.2.設(shè)x,x,…，xeR+，且滿足￡x2=n,￡x>s>0.對(duì)于0<X<1證明：這n個(gè)數(shù)中至少有1 2 n i ii=1 i=1[s2(i)2]個(gè)數(shù)大于z.n證明：定義A={j九s1<j<n.xkjn}，A為A中元素的個(gè)數(shù)，由柯西不等式得：證明：定義A={j九s1<j<n.xkjn}，A為A中元素的個(gè)數(shù)，由柯西不等式得：，所以a|>s2(1")2，故原命題成立.max{AA}3.平面上n(n不為平方數(shù))個(gè)點(diǎn)A,A，…,A，設(shè)X= 」12n min{AA}ij求證：X>2證明：固定d=max{A,A}.不妨設(shè)AA=d，分別過(guò)A,A作半徑為dij 1 2 1 2的圓，再過(guò)A,A分別作切線l,l，則存在A,A，…,A均在l,l之間.再1