1組合數(shù)學(xué)西北工業(yè)大學(xué)從屬中學(xué)焦和平第1頁(yè)2一．概論組合數(shù)學(xué)是一個(gè)古老而又年輕數(shù)學(xué)分支。組合數(shù)學(xué)中著名問(wèn)題

地圖著色問(wèn)題

中國(guó)郵差問(wèn)題船夫過(guò)河問(wèn)題任務(wù)分配問(wèn)題第2頁(yè)3

組合數(shù)學(xué)主要研究一組離散對(duì)象滿足一定條件安排，討論內(nèi)容大致有四方面：1．存在性：有沒(méi)有滿足條件安排？2．計(jì)數(shù)：滿足條件安排有多少種？3．結(jié)構(gòu)：給出滿足條件安排詳細(xì)結(jié)構(gòu)。4．優(yōu)化：在眾多滿足要求安排中，按一定標(biāo)準(zhǔn)挑出最優(yōu)安排。第3頁(yè)4二、數(shù)學(xué)競(jìng)賽中主要問(wèn)題1．組合數(shù)學(xué)中存在性問(wèn)題1．1抽屜原理抽屜原理是一件簡(jiǎn)單明了事實(shí)：n+1個(gè)物品放入n個(gè)抽屜中，則最少有一個(gè)抽屜，其中有兩個(gè)或更多物品。普通地：m個(gè)物品放入n個(gè)抽屜中，則最少有一個(gè)抽屜不少于a個(gè)，其中第4頁(yè)5抽屜原理普通地：m個(gè)物品放入n個(gè)抽屜中，則最少有一個(gè)抽屜不少于a個(gè)，其中第5頁(yè)6抽屜原理變式第6頁(yè)7例1．單位圓內(nèi)任意投放六點(diǎn)，求證最少有兩點(diǎn)距離小于1。解答：取六點(diǎn)中一點(diǎn)A，

若A為單位圓圓心，

結(jié)論顯然成立。

若A不是圓心O，則如圖將

單位圓劃分為六個(gè)中心角為60度扇形,若陰影部分內(nèi)還有六點(diǎn)中另一點(diǎn),則結(jié)論成立.若陰影部分內(nèi)沒(méi)有六點(diǎn)中除A點(diǎn)外點(diǎn),則另五點(diǎn)(物品)在其余四個(gè)扇形(抽屜)中,由抽屜原理,必有某個(gè)扇形(抽屜)含有最少兩個(gè)(物品),故結(jié)論成立.第7頁(yè)8例2．平面上任給個(gè)點(diǎn)，其中任兩點(diǎn)距離均大于，求證：必有223個(gè)點(diǎn)彼此之間距離都大于2。

解答:將平面按圖分成九個(gè)抽屜,i號(hào)小方格全體為第i個(gè)抽屜.個(gè)點(diǎn)分放在九個(gè)抽屜中,最少有一個(gè)抽屜含有223個(gè)點(diǎn),因?yàn)閭€(gè)點(diǎn)中任兩點(diǎn)距離均大于,所以此223個(gè)點(diǎn)距離均大于,它們中沒(méi)有兩點(diǎn)屬于同一小方格,而同號(hào)方格又不在同一方格中任兩點(diǎn)距離都大于2.

123123123456456456789789789123123123456456456789789789123123123456456456789789789第8頁(yè)9本題牽扯到A子集以及子集中各數(shù)之和兩個(gè)討論對(duì)象，分別討論它們有多少種。15元子集A子集共個(gè)，不空真子集共個(gè)，真子集中各數(shù)之和S滿足=27979，子集中各數(shù)和種數(shù)不超出27979，將32766個(gè)子集放入27979類(lèi)和（抽屜）中，最少有一類(lèi)和中含有兩個(gè)子集，即有B與C中各數(shù)和相等。若，則結(jié)論成立；若，則以代替B，C，結(jié)論亦成立。第9頁(yè)10第10頁(yè)111．2極端原理

利用討論“極端”對(duì)象來(lái)實(shí)現(xiàn)問(wèn)題處理解題方法稱為用極端原了解題，慣用極端原理基于下述簡(jiǎn)單事實(shí)：

1）由實(shí)數(shù)組成有限集合，必有一個(gè)最大數(shù)，也有一個(gè)最小數(shù)。

2）由自然數(shù)組成任何非空集合中，必有一個(gè)最小自然數(shù)。為了必定或否定組合數(shù)學(xué)問(wèn)題存在性，極端原理有著重大作用。考查極端情況，討論極端對(duì)象，無(wú)形中給問(wèn)題討論增加了一個(gè)條件，所以更有利于問(wèn)題處理；用反證法時(shí)，討論極端情況，使矛盾更輕易暴露。第11頁(yè)12例5．對(duì)平面上不全共線n個(gè)點(diǎn)，求證：必存在一條恰好經(jīng)過(guò)兩點(diǎn)直線。

解答：對(duì)n個(gè)點(diǎn)中任兩點(diǎn)作連線m，

并取連線外點(diǎn)P（必存在），

考查P到m距離d（P，m），

因?yàn)辄c(diǎn)為有限個(gè)，連線m為有限條，

組合（P，m）也只能有有限個(gè)，用極端原理設(shè)d（P，m）為最小。下面證實(shí)，m恰經(jīng)過(guò)n點(diǎn)中2點(diǎn)：過(guò)點(diǎn)P作m垂線，設(shè)垂足為A.若m上最少有n點(diǎn)中3點(diǎn)，則最少有2點(diǎn)在A同側(cè)，設(shè)B，C在A同側(cè)，且AB<AC,則d(B,PC)=d(P,m),矛盾.

第12頁(yè)13例6．一組砝碼含有以下性質(zhì)：

（1）其中有5個(gè)砝碼質(zhì)量各不相同；

（2）對(duì)于任何2個(gè)砝碼，都能夠找到另外2個(gè)砝碼，它們質(zhì)量之和相等。問(wèn)這組砝碼最少有多少個(gè)？解答:設(shè)A是其中最重砝碼,B是次重砝碼,則質(zhì)量組{A,B}質(zhì)量之和只能與質(zhì)量分別與它們相等兩個(gè)砝碼質(zhì)量之和相等.所以至少有兩組這樣砝碼.又砝碼{A,A}質(zhì)量之和又只能與質(zhì)量分別與它們相等兩個(gè)砝碼質(zhì)量之和相等,所以最重砝碼至少有4個(gè),次重砝碼至少有2個(gè).

同理最輕砝碼至少有4個(gè),次輕砝碼至少有2個(gè).因?yàn)橛?個(gè)質(zhì)量各不相同砝碼,至少還有另一種質(zhì)量砝碼,所以砝碼個(gè)數(shù)至少有4+4+2+2+1=13個(gè).

其次,質(zhì)量分別為{1,1,1,1,2,2,3,4,4,5,5,5,5}13個(gè)砝碼滿足題給條件.第13頁(yè)14例7．n（n>3）名乒乓球選手單打比賽若干場(chǎng)后,任意兩名選手已勝過(guò)對(duì)手恰好都不完全相同,

求證:總能夠從中去掉一名選手,使得余下選手中,任意兩個(gè)選手已勝過(guò)對(duì)手依然都不完全相同.

證實(shí):若不存在可去選手,則A不是可去選手,去掉A后.最少存在選手B和C,他們勝過(guò)對(duì)手完全相同,故B和C一定沒(méi)有勝過(guò);B和C中恰有一人(不妨設(shè)為B)與A勝過(guò)(不然B和C在未去掉A時(shí)勝過(guò)對(duì)手完全相同),如圖:

同時(shí)C也不是可去選手,C代替A,

如上述討論可知,有D和E,其中D和C勝過(guò),

E和C未勝過(guò),去掉C后,D和E勝過(guò)對(duì)手

相同.D不會(huì)是A,B(因A,B與C未勝過(guò)),D與B

勝過(guò)(因D和C勝過(guò),去掉A后,B,C對(duì)手相同).

去掉C后,D和E勝過(guò)對(duì)手相同.所以E與B也勝過(guò).第14頁(yè)151.3結(jié)構(gòu)法和不變性原理經(jīng)過(guò)直接構(gòu)作出解答來(lái)實(shí)現(xiàn)問(wèn)題處理稱為用結(jié)構(gòu)法解題;對(duì)討論問(wèn)題分析其改變,找出其中不變量、不變關(guān)系或不變性質(zhì)，抓住變中“不變”以促使問(wèn)題處理稱為用不變性原了解題。對(duì)于組合數(shù)學(xué)存在性問(wèn)題，慣用結(jié)構(gòu)法給出必定答案，而不變性原理常可給出否定結(jié)論。不變性原理中最簡(jiǎn)單、最實(shí)用是奇偶性分析。第15頁(yè)16例8．有一個(gè)凸n邊形（n4）全部頂點(diǎn)用紅綠藍(lán)三色染色，三種顏色都出現(xiàn)，且任意兩相鄰頂點(diǎn)不一樣色，求證：可用在n邊形內(nèi)不交對(duì)角線將多邊形分成n-2個(gè)三角形，使每個(gè)三角形三頂點(diǎn)都不一樣色。

解答:若某種顏色點(diǎn)只有一個(gè),則易知結(jié)論成立.若每種顏色頂點(diǎn)最少有二個(gè),且相鄰頂點(diǎn)顏色不一樣,則必有連續(xù)三個(gè)頂點(diǎn)k,k+1,k+2恰為三色,將此三角形從凸n邊形中割下,

那么余下是規(guī)模更小凸多邊形,

若依然每種顏色頂點(diǎn)最少有二個(gè),

可繼續(xù)割去一個(gè)三色三角形,…,

最終可得某種顏色只有一個(gè),

能夠如圖給出分劃.

第16頁(yè)17例9．能否把1，1，2，2，3，3，…，，這4010個(gè)數(shù)排成一列，使得兩個(gè)1之間有一個(gè)數(shù)，兩個(gè)2之間有二個(gè)數(shù)，…，兩個(gè)之間有個(gè)數(shù).第17頁(yè)18證實(shí)：充分性：可用結(jié)構(gòu)法作出，如圖，正方形可剖分成6個(gè)鈍角三角形，又任一鈍角三角形總可分成兩個(gè)鈍角三角形。必要性：先找出任意鈍角三角形剖分中不變關(guān)系。對(duì)剖分法剖分點(diǎn)進(jìn)行分類(lèi)：在正方形邊界上剖分點(diǎn)或在某一剖分三角形邊上但不是該

三角形頂點(diǎn)內(nèi)剖分點(diǎn)稱為第一類(lèi)

剖分點(diǎn)；不在三角形邊上內(nèi)剖分點(diǎn)

稱為第二類(lèi)剖分點(diǎn)。如圖中F，G，H

為第一類(lèi)剖分點(diǎn)，E為第二類(lèi)剖分點(diǎn)。第18頁(yè)19第19頁(yè)20（2）任意凸四邊形（各種情形）可剖分成鈍角三角形（銳角三角形）充要條件又各是什么？第20頁(yè)212．組合數(shù)學(xué)中計(jì)數(shù)問(wèn)題2．1加法原理和乘法原理加法原理：設(shè)事件A有m種選取方式，事件B有n種選取方式，事件A和事件B沒(méi)有共同選取方式，則選A或選B有m+n種方式。乘法原理：設(shè)事件A有m種選取方式，事件B有n種選取方式，則選取A以后再選B共有mn種方式。

第21頁(yè)22第22頁(yè)23例12.三個(gè)數(shù)1447、1005、1231有許多相同之處：它們都有四位數(shù)，最高位都是1，都恰有兩個(gè)相同數(shù)字，一共有多少個(gè)這么數(shù)。第23頁(yè)242.2映射與計(jì)數(shù)第24頁(yè)25例13.在數(shù)列1，9，81，…，9中刪去最高位是9項(xiàng)，問(wèn)余下數(shù)列有多少項(xiàng)？

第25頁(yè)26例14.圓周上有n個(gè)點(diǎn)每?jī)蓚€(gè)點(diǎn)連一線段，假設(shè)任三條線段在圓內(nèi)不共點(diǎn)，于是三條兩兩相交線段組成一個(gè)三角形，試求這些三角形個(gè)數(shù)？

第26頁(yè)27例15.設(shè)凸n邊形任意3條對(duì)角線不相交于行內(nèi)一點(diǎn)，求它對(duì)角線在行內(nèi)交點(diǎn)總數(shù)。第27頁(yè)28例16.今有編號(hào)為1，2，…，10鑰匙與編號(hào)為1，2，…，10箱子，每把鑰匙只能打開(kāi)與之號(hào)數(shù)相同箱子，現(xiàn)將全部鑰匙都放進(jìn)這些箱子中，每只箱子放一把，然后鎖上，那么最少有多少種不一樣放法，使得最少要撬開(kāi)兩只箱子才能將箱子全部打開(kāi)？若恰撬開(kāi)兩只箱子才能將箱子全部打開(kāi)，又有多少放法？

第28頁(yè)29

證實(shí)：我們將不定方程任意一組非負(fù)整數(shù)解對(duì)應(yīng)于一個(gè)由n個(gè)圓圈“О”，k-1個(gè)豎線“|”組成以下排列：О…О|О…О|…|О…О，其中第一根豎線“|”左側(cè)恰有x1個(gè)圓圈“О”；第i-1根豎線“|”與第i根豎線“|”之間恰有xi個(gè)圓圈“О”；第i-1根豎線“|”右側(cè)恰有xk個(gè)圓圈“О”。顯然，不定方程不一樣解對(duì)應(yīng)于不一樣排列，且每一個(gè)這么對(duì)應(yīng)于不定方程一組非負(fù)整數(shù)解，所以，我們建立對(duì)應(yīng)是一個(gè)雙射。又因?yàn)橛蒼個(gè)圓圈“О”及k-1根豎線“|”組成n+k-1個(gè)元素全排列數(shù)為，所以，不定方程一組非負(fù)整數(shù)解組組數(shù)為。第29頁(yè)302．3容斥原理第30頁(yè)31例18.一個(gè)學(xué)校只有3門(mén)課程：數(shù)學(xué)、物理、化學(xué)，已知修這3門(mén)課程學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門(mén)課學(xué)生有45人；同時(shí)修數(shù)學(xué)、化學(xué)兩門(mén)課學(xué)生有20人；同時(shí)修物理、化學(xué)兩門(mén)課學(xué)生有22人；同時(shí)修三門(mén)課學(xué)生有3人。問(wèn)這個(gè)學(xué)校共有多少學(xué)生？第31頁(yè)32例19.

求a，b，c，d，e，f這六個(gè)字母全排列中不允許出現(xiàn)ace和df圖像排列數(shù)。第32頁(yè)33第33頁(yè)34例21.求由a，b，c，d這4個(gè)字符組成n位數(shù)字串中，a，b，c最少出現(xiàn)一次符號(hào)串?dāng)?shù)目。第34頁(yè)35第35頁(yè)36同理第36頁(yè)37第37頁(yè)38練習(xí)題1．給定個(gè)集合，每個(gè)集合都恰含有44個(gè)元素，而且每?jī)蓚€(gè)集合都恰有一個(gè)公共元素，試求這個(gè)集合并集中有多少個(gè)元素？2．平面內(nèi)給定200個(gè)不一樣點(diǎn)，證實(shí)：其中距離為單位長(zhǎng)點(diǎn)對(duì)數(shù)小于2050。3．以正n邊形頂點(diǎn)為頂點(diǎn)梯形共有多少個(gè)？第38頁(yè)39雜題第39頁(yè)40

例1

運(yùn)動(dòng)會(huì)開(kāi)了n天（n>1）,共發(fā)出m個(gè)獎(jiǎng)牌,第一天發(fā)出1個(gè)加余下獎(jiǎng)牌,第二天發(fā)出2個(gè)加余下獎(jiǎng)牌,如此繼續(xù)下去,最終,第n天發(fā)出n個(gè)獎(jiǎng)牌恰無(wú)剩下.問(wèn)運(yùn)動(dòng)會(huì)共開(kāi)了幾天?共發(fā)出多少個(gè)獎(jiǎng)牌?第40頁(yè)41第41頁(yè)42第42頁(yè)43例2.幾個(gè)人在一起,使得其中存在有相同生日概率最少為二分之一.即23人中,最少有一對(duì)生日相同概率超出二分之一

第43頁(yè)44例3.甲乙二人玩，在黑板上寫(xiě)數(shù)游戲，規(guī)則是二人輪番在黑板上寫(xiě)一個(gè)不超出p自然數(shù)，但禁止再寫(xiě)出黑板上已經(jīng)有因數(shù)。甲先開(kāi)始寫(xiě)，輪到誰(shuí)寫(xiě)而無(wú)法寫(xiě)出時(shí)就告負(fù)。

（1）當(dāng)p=10時(shí)，游戲者中誰(shuí)有獲勝策略？

（2）當(dāng)p=1000時(shí)，游戲者中誰(shuí)有獲勝策略？

解答：（1）甲有獲勝策略，他能夠先寫(xiě)6，于是按規(guī)則不能再寫(xiě)1，2，3。其余6個(gè)數(shù)分成3組：（4，5）（7，9）（8，10）不論乙寫(xiě)哪一個(gè)，甲就寫(xiě)同組另一個(gè)。

（2）考查寫(xiě)數(shù)標(biāo)準(zhǔn)相同但取數(shù)范圍不是由1到1000而是由2到1000這個(gè)游戲。假如這個(gè)游戲先寫(xiě)者有必勝策略，那么甲對(duì)原來(lái)游戲只要照搬就行了。因?yàn)榧讓?xiě)下一個(gè)自然數(shù)后，乙是不能寫(xiě)1。假如新游戲先寫(xiě)數(shù)人沒(méi)有獲勝策略，即他只能告負(fù)，那么甲在原游戲中能夠先寫(xiě)1，從而將失敗留給了乙。可見(jiàn)，甲總有獲勝策略。第44頁(yè)45例4.

甲乙兩人在畫(huà)有個(gè)方格正方形場(chǎng)地上做游戲:甲先在場(chǎng)地中央畫(huà)一個(gè)星號(hào),乙則在放有星號(hào)格子周?chē)?個(gè)格子中任選1個(gè)方格畫(huà)一個(gè)圓圈.然后甲再在某個(gè)與已畫(huà)有標(biāo)識(shí)格子挨著空格中畫(huà)一個(gè)星號(hào),并一直繼續(xù)下去.假如甲成功地將星號(hào)畫(huà)入場(chǎng)地四角任何一個(gè)角上方格中,就算他獲勝.求證:不論乙怎么做,甲總能夠獲勝.第45頁(yè)46例5.在3×3正方形表格中填上如圖所表示9個(gè)數(shù)字,將該表進(jìn)行以下操作:

每次操作是對(duì)表中相鄰兩數(shù)同時(shí)加上一個(gè)數(shù)(相鄰是指有公共邊兩小格),問(wèn)能否經(jīng)過(guò)若干次操作使得（1）表格中各數(shù)均為0；（2）表格中四個(gè)角數(shù)為1,其余均為0.032670495第46頁(yè)47解答:(1)能夠得到.實(shí)際上經(jīng)過(guò)5次操作即可.032670495010670495010670055010670000010010000000000000→→→→→第47頁(yè)48(2)考慮這種操作普通形式:abcdefghk為此,設(shè)表格中第一行數(shù)從左到右為a,b,c.

第二行數(shù)從左到右為d,e,f.第三行數(shù)從左到右為g,h,k.按操作規(guī)則,任意相鄰數(shù)都加同一個(gè)數(shù),所以操作每一步均不改變S=(a+c+e+g+k)-(b+d+h+f)值.而表格初始狀態(tài)S值為

S=(0+2+7+4+5)-(3+6+9+0)=0要到達(dá)狀態(tài)S值為S=(1+1+0+1+1)-(0+0+0+0)=4所以不能實(shí)現(xiàn)滿足題目要求操作.abcdefghk第48頁(yè)49例6.凸n邊形任意3條對(duì)角線不相交于形內(nèi)一點(diǎn)，求這些對(duì)角線將凸n邊形分成區(qū)域個(gè)數(shù).

第49頁(yè)50第50頁(yè)51第51頁(yè)52第52頁(yè)53第53頁(yè)54例7.已知平面上有4條直線,其中任何兩條都相交,任何三條都不交于一點(diǎn),于是在每條直線上都交得3個(gè)交點(diǎn),它們從直線上截出兩條線段,共得到8條線段.

問(wèn)這8