【4-組合】7.組合構(gòu)造【講師版】

1、 課程類(lèi)型數(shù)學(xué)組合構(gòu)造+組合復(fù)習(xí)”講義編號(hào)：學(xué)員：年級(jí)：授課日期：講師：授課方式（在線(xiàn)或線(xiàn)下）：（線(xiàn)下填）授課教學(xué)點(diǎn)：知識(shí)定位*組合構(gòu)造雖然需要一定天分和幸運(yùn)的成分，但也有規(guī)律可循。本節(jié)主要介紹兩種構(gòu)造方法。然后進(jìn)行組合數(shù)學(xué)的習(xí)題課。知識(shí)梳理字典排序法在我小的時(shí)候，還沒(méi)有手機(jī)這種東西（同學(xué)們聽(tīng)過(guò)傳呼機(jī)么？），網(wǎng)絡(luò)也并不發(fā)達(dá)和廣泛。所以那時(shí)候我們遇到生字都要查字典。其實(shí)字典里將漢字排列是遵循一定規(guī)律的。我們知道英文字典排序都是按照權(quán)重abcd.z來(lái)排列的。漢語(yǔ)字典也是這樣，首先按照拼音排序，當(dāng)兩個(gè)漢字拼音一樣時(shí)，按照筆畫(huà)多少排序，當(dāng)筆畫(huà)也一樣時(shí)，就按照偏旁部首的下筆順序來(lái)排列。在遇到數(shù)學(xué)問(wèn)題時(shí)，

2、我們?cè)谧雒杜e舉例時(shí)，同學(xué)們也可以按照這樣的規(guī)律來(lái)進(jìn)行枚舉：將參與的元素賦予權(quán)重，然后按照權(quán)重來(lái)枚舉，這樣可以保證不重不漏。如將由A、B、C三個(gè)字符組成的全排列枚舉出來(lái)：ABC、ACB、BAC、BCA、CAB、CBA輪換排序法輪換排序法特別適合有一定規(guī)律的枚舉，將參與排序的元素按照輪換順序轉(zhuǎn)一圈，這種方法相對(duì)于字典排序法，優(yōu)勢(shì)在于枚舉時(shí)省力氣，但卻不能有效保證不重不漏，需要枚舉后加以驗(yàn)證。如將由A、B、C三個(gè)字符組成的全排列枚舉出來(lái)：（ABC,BCA，CAB），（CBA，BAC，ACB）例1將7X7的點(diǎn)陣中的某些點(diǎn)染上紅色，當(dāng)由某四個(gè)頂點(diǎn)組成的底和高分別平行于點(diǎn)陣的底和高矩形四個(gè)頂點(diǎn)都是紅色時(shí)，

3、我們稱(chēng)這個(gè)矩形為紅點(diǎn)矩形。求：最多能將點(diǎn)陣中的都少個(gè)點(diǎn)染色，使得不存在紅點(diǎn)矩形？【解答】21個(gè)首先證明至多21個(gè)紅點(diǎn)。設(shè)第i行有x,個(gè)紅點(diǎn)，設(shè)x+x+.+x=x為所求的紅點(diǎn)數(shù)。i127我們把每行的每?jī)蓚€(gè)紅點(diǎn)所在的列記成數(shù)對(duì)形式，如若某兩個(gè)同行的紅點(diǎn)所在的列分別為3、7，則記存在數(shù)對(duì)（3,7），顯然同行紅點(diǎn)組成的點(diǎn)對(duì)不同。則不存在紅點(diǎn)矩陣等價(jià)于所有紅點(diǎn)組成的點(diǎn)對(duì)沒(méi)有重復(fù)的。又由17組成的點(diǎn)對(duì)共C2二21個(gè)，故有C2C2二21TOC o 1-5 h z7xi7i=1X2+X2+.+X2(x+X+.+X)1271271277故-X-420，解得14X21。接下來(lái)證明21個(gè)是可以的。這就涉及到構(gòu)造方法

4、，首先我們用字典構(gòu)造法輪換構(gòu)造法：故21能取到，證畢。例2某乒乓球培訓(xùn)班共有n位學(xué)員，在班內(nèi)雙打訓(xùn)練賽期間，每?jī)擅麑W(xué)員都作為搭檔恰好參加過(guò)一場(chǎng)雙打比賽。試確定n的所有可能值并分別給出對(duì)應(yīng)的一種安排比賽的方案?！窘獯稹考僭O(shè)比賽了K場(chǎng)，那么由題目假設(shè)，一場(chǎng)比賽出現(xiàn)了2對(duì)隊(duì)友，所以C2=2k，也就是說(shuō)4k=n(n-l),那么得到nn=4l或者41+1,期中1eN,下邊證明，對(duì)于任意的n=41,或者41+1,其中l(wèi)eN,都可以構(gòu)造出滿(mǎn)足要求的比賽：n=41+1,的時(shí)候，對(duì)于L使用數(shù)學(xué)歸納法：當(dāng)L=1的時(shí)候，N=5，此時(shí)假設(shè)這5名選手為A,B,C,D,E,那么如下安排比賽即可，AB-CD,AC-BE,B

5、C-DE,AE-BD,AD-CE.設(shè)當(dāng)L=M時(shí)結(jié)論成立，則L=M+1時(shí)，設(shè)4M+5選手為A,B,C,D,EF1,F2,F1,F2.,F1,F2,由歸納11222m2mF1,F2,F1,F2,F1,F2假設(shè)，可以安排E,11222m2m之間的比賽，使得他們之間每?jī)晌贿x手的作為隊(duì)友恰好只參加F1,F2,F1,F2過(guò)一次比賽，還剩下A,B,C,D,E,相互的比賽和A,B,C,D與112m2m之間的比賽，A,B,C，D與112m2m之間的比賽安排如下：AF1與BF2,AF2與BF1,CF1與DF2,CF2與DF滿(mǎn)足要求。LLLLLLLL最后將這些比賽總計(jì)起來(lái)，就是滿(mǎn)足要求的4M+5位選手之間的的比賽了

6、。由數(shù)學(xué)歸納法得證，N=4L時(shí)，對(duì)L使用數(shù)學(xué)歸納法，可以類(lèi)似方法證明(略)綜上所述，N的所有可能取值是N=4L或4L+1，其中LeN.例3能否將正整數(shù)集合N+分劃為兩個(gè)不相交的集合A和B,滿(mǎn)足:A中任意三個(gè)數(shù)不成等差數(shù)列不能由B中的元素組成一個(gè)非常數(shù)的無(wú)窮等差數(shù)列【解答】1t1!*2*3)r則A中任意三個(gè)數(shù)不國(guó)難的為了使B=M”1滿(mǎn)足條件(燈反沖=*4r.p-y-“T-；坷為若二4)及Ii=-丸滿(mǎn)廣成等差數(shù)列則“一C故只要口tP:威茅差數(shù)列*耍構(gòu)造這樣的A是只要滿(mǎn)足對(duì)任意宀dEI等差至少有_項(xiàng)屬于A*I解法一將首項(xiàng)為s公差為的無(wú)窮等差數(shù)列用心表示易將所有總數(shù)無(wú)窮等差數(shù)列(非常數(shù)列廠排序如下：(

7、1(匚2).(2,1).1.;2,2).(3-!)*-排序的規(guī)律是:先看&+的大小+小者排肘-口-山卜的心較小的排前申按下列方式構(gòu)造數(shù)列血、如，設(shè)4=X如血，H.4已瑕出側(cè)在第+i個(gè)等差數(shù)列中取大于汕的某一頊為卄B令八=a2，知人則因2a,r(n=I*2+)故A中任阿個(gè)數(shù)不成等差數(shù)列再令B=N+A則因?yàn)槿魏握麛?shù)的非常數(shù)列的無(wú)卜是飯列都有一項(xiàng)屬F兒故B中沒(méi)育非常數(shù)列的無(wú)窮等差數(shù)列于是存在満足題H條件的集合A和乩llfl$分析二同分析知易構(gòu)造滿(mǎn)足條件的兒為門(mén)吏JBwNA瀟足條件只須滿(mǎn)足對(duì)任意-dEN-無(wú)窮等塗數(shù)列厶+哼崟2*中老1閃witUR研*th*前UL$只娶af1陽(yáng)個(gè)數(shù)【q成比=曲斗口的降

8、式使1次取列心的fdiL存亦棊個(gè)籌寸f-m1町沁4tocrtz*Nh氏門(mén)尢1?r,魁任意d的怙蹴這只要A中皆有無(wú)騎多個(gè)形如|&為尤窮尊蠱數(shù)a的它!的數(shù)即氐存（ll.lM-k山td取瑪解袪二1111札州IM：UU幾UJ（:中幾M!小6!1+1JtA：r!+h氓卜訃（我中Hi.tr(h1Jf.乃=A,則將數(shù)從小01大排列時(shí)從第二項(xiàng)趙*誓一壩大于前面一項(xiàng)的2倍.故A中任彳數(shù)彳成等挖數(shù)列丫其次卅中粒有非常數(shù)列的無(wú)窮辱差數(shù)列.,:則胡！4汕；弋lZ足中_個(gè)非常數(shù)列的無(wú)窮等普數(shù)fftA的構(gòu)造知存在無(wú)窮多令mt打匚*jtfktfi筋*町見(jiàn)存在薦足條件門(mén)M2的集合A與魚(yú)試題演練1）證明：能將不同的完全平方數(shù)填

9、滿(mǎn)mn的矩形方格表中的每一個(gè)小方格，使得每行、每列的和也是完全平方數(shù)?！敬鸢浮?）對(duì)任意正整數(shù)n在平面內(nèi)是否存在n個(gè)不在同一直線(xiàn)上的點(diǎn)，使得任意兩點(diǎn)間的距離都為正整數(shù)?【答案】3）對(duì)任意正整數(shù)n,平面內(nèi)是否存在一個(gè)有限點(diǎn)集M,使得對(duì)任一點(diǎn)pM，在M中恰有n個(gè)到p的距離都等于1的點(diǎn)?！敬鸢浮靠?I時(shí)取M為長(zhǎng)度等于1的線(xiàn)段的兩個(gè)端點(diǎn)符合要求設(shè)軒=缸弍(I在有限點(diǎn)集/VL使對(duì)任意PCM,M中恰有k個(gè)到p的距離等于1的點(diǎn).那時(shí).以M中處個(gè)點(diǎn)為圓心J為半桂作同*再將頂I心耳該圜上的每卜工占連一線(xiàn)段以及在M中每?jī)牲c(diǎn)連一線(xiàn)段由于所連線(xiàn)段數(shù)有限故平血內(nèi)存4丿向f與上述所連的每一條線(xiàn)段都不平行將點(diǎn)集沿/方向平移一個(gè)怕位氏得到直集“*鳳!門(mén)血=0于墨對(duì)任意p：MJMf在MJMf中恰有昏十1個(gè)點(diǎn)到P的膽鴇等于1故n-k+1時(shí)MUM滿(mǎn)足題目要求*駛對(duì)也種歷*存住滿(mǎn)足題目要球的點(diǎn)集必講師評(píng)價(jià)知識(shí)點(diǎn)課后掌握情況所需習(xí)題編號(hào)是否需要課時(shí)加強(qiáng)課后掌握情況評(píng)分：1對(duì)本知識(shí)點(diǎn)毫無(wú)所知，聞所未聞。2了解該知識(shí)點(diǎn)，能完成簡(jiǎn)單的識(shí)記題。3理解該知識(shí)點(diǎn)，能運(yùn)用其分析解答簡(jiǎn)單問(wèn)題。4把握知識(shí)的意義，但缺乏練習(xí)與手感，解答稍難的題目速度慢。5深刻了解知識(shí)