1、組合數(shù)學(xué)1一概論組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。組合數(shù)學(xué)中的著名問(wèn)題 地圖著色問(wèn)題中國(guó)郵差問(wèn)題船夫過(guò)河問(wèn)題任務(wù)分配問(wèn)題2 組合數(shù)學(xué)主要研究一組離散對(duì)象滿足一定條件的安排，討論的內(nèi)容大致有四方面：1存在性：有沒(méi)有滿足條件的安排？2計(jì)數(shù)：滿足條件的安排有多少種？3構(gòu)造：給出滿足條件的安排的具體構(gòu)造。4優(yōu)化：在眾多滿足要求的安排中，按一定的標(biāo)準(zhǔn)挑出最優(yōu)的安排。3二、數(shù)學(xué)競(jìng)賽中的主要問(wèn)題1組合數(shù)學(xué)中的存在性問(wèn)題11抽屜原理 抽屜原理是一件簡(jiǎn)單明了的事實(shí)：n+1個(gè)物品放入n個(gè)抽屜中，則至少有一個(gè)抽屜，其中有兩個(gè)或更多的物品。 一般地：m個(gè)物品放入n個(gè)抽屜中，則至少有一個(gè)抽屜不少于a個(gè)，其中4抽屜原

2、理一般地：m個(gè)物品放入n個(gè)抽屜中，則至少有一個(gè)抽屜不少于a個(gè)，其中5抽屜原理的變式6例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例2平面上任給2005個(gè)點(diǎn)，其中任兩點(diǎn)距離均大于 ，求證：必有223個(gè)點(diǎn)彼此之間距離都不小于2。 解答:將平面按圖分成九個(gè)抽屜,i號(hào)小方格全體為第i個(gè)抽

3、屜.2005個(gè)點(diǎn)分放在九個(gè)抽屜中,至少有一個(gè)抽屜含有223個(gè)點(diǎn),由于2005個(gè)點(diǎn)中任兩點(diǎn)距離均大于 ,所以此223個(gè)點(diǎn)距離均大于,它們中沒(méi)有兩點(diǎn)屬于同一小方格,而同號(hào)方格又不在同一方格中的任兩點(diǎn)距離都不小于2. 1231231234564564567897897891231231234564564567897897891231231234564564567897897898本題牽扯到A的子集以及子集中各數(shù)之和兩個(gè)討論對(duì)象，分別討論它們有多少種。15元子集A的子集共個(gè) ，不空真子集共 個(gè)，真子集中各數(shù)之和S滿足 =27979，子集中各數(shù)和的種數(shù)不超過(guò)27979，將32766個(gè)子集放入27979類(lèi)

4、和（抽屜）中，至少有一類(lèi)和中含有兩個(gè)子集，即有 B與C中各數(shù)和相等。若 ，則結(jié)論成立；若 ，則以 代替B，C，結(jié)論亦成立。91012 極端原理 利用討論“極端”對(duì)象來(lái)實(shí)現(xiàn)問(wèn)題解決的解題方法稱(chēng)為用極端原理解題，常用的極端原理基于下述簡(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例5 對(duì)平面上不全共線的n個(gè)點(diǎn)，求證：必存在

5、一條恰好通過(guò)兩點(diǎn)的直線。 解答：對(duì)n個(gè)點(diǎn)中的任兩點(diǎn)作連線m，并取連線外的點(diǎn)P（必存在），考察P到m的距離d（P，m），由于點(diǎn)為有限個(gè)，連線m為有限條，組合（P，m）也只能有有限個(gè)，用極端原理設(shè)d（P，m）為最小。 下面證明，m恰通過(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è)，且AB3）名乒乓球選手單打比賽若干場(chǎng)后,任意兩名選手已賽過(guò)的對(duì)手恰好都不完全相同,求證:總可以從中去掉一名選手,使得余下的選手中,任意兩個(gè)選手已賽過(guò)的對(duì)手仍然都不完全相同. 證明:若不存在可去選手,則A不是可去選手, 去掉A后.至少存在選手B和C,他們賽

6、過(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ò).141.3 構(gòu)造法和不變性原理通過(guò)直接構(gòu)作出解答來(lái)實(shí)現(xiàn)問(wèn)題的解決稱(chēng)為用構(gòu)造法解題;對(duì)討論問(wèn)題分析其變化,找出其中不變的量、不變的關(guān)系或不變的性質(zhì)，抓住變中的“不變”以促使問(wèn)題的解決稱(chēng)為用不變性原

7、理解題。對(duì)于組合數(shù)學(xué)的存在性問(wèn)題，常用構(gòu)造法給出肯定的答案，而不變性原理常可給出否定的結(jié)論。不變性原理中最簡(jiǎn)單、最實(shí)用的是奇偶性分析。15例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è)三色三角形,最后可得某種顏色只

8、有一個(gè),可以如圖給出分劃. 16例9 能否把1，1，2，2，3，3，2005，2005這4010個(gè)數(shù)排成一列，使得兩個(gè)1之間有一個(gè)數(shù)，兩個(gè)2之間有二個(gè)數(shù)，兩個(gè)2005之間有2005個(gè)數(shù) .17證明：充分性：可用構(gòu)造法作出，如圖，正方形可剖分成6個(gè)鈍角三角形，又任一鈍角三角形總可分成兩個(gè)鈍角三角形。 必要性：先找出任意鈍角三角形剖分中不變的關(guān)系。 對(duì)剖分法的剖分點(diǎn)進(jìn)行分類(lèi)：在正方形邊界上的剖分點(diǎn)或在某一剖分三角形邊上但不是該三角形頂點(diǎn)的內(nèi)剖分點(diǎn)稱(chēng)為第一類(lèi)剖分點(diǎn)；不在三角形邊上的內(nèi)剖分點(diǎn)稱(chēng)為第二類(lèi)剖分點(diǎn)。如圖中F，G，H為第一類(lèi)剖分點(diǎn)，E為第二類(lèi)剖分點(diǎn)。1819（2）任意凸四邊形（各種情形）可剖分

9、成鈍角三角形（銳角三角形）的充要條件又各是什么？ 202組合數(shù)學(xué)中的計(jì)數(shù)問(wèn)題21 加法原理和乘法原理加法原理：設(shè)事件A有m種選取方式，事件B有n種選取方式，事件A和事件B沒(méi)有共同選取方式，則選A或選B有m+n種方式。乘法原理：設(shè)事件A有m種選取方式，事件B有n種選取方式，則選取A以后再選B共有mn種方式。 2122例12 .三個(gè)數(shù)1447、1005、1231有許多相同之處：它們都有四位數(shù)，最高位都是1，都恰有兩個(gè)相同的數(shù)字，一共有多少個(gè)這樣的數(shù)。232.2 映射與計(jì)數(shù)24例13. 在數(shù)列1，9，81，92005中刪去最高位是9的項(xiàng)，問(wèn)余下的數(shù)列有多少項(xiàng)？ 25例14. 圓周上有n個(gè)點(diǎn)每?jī)蓚€(gè)點(diǎn)連

10、一線段，假設(shè)任三條線段在圓內(nèi)不共點(diǎn)，于是三條兩兩相交的線段構(gòu)成一個(gè)三角形，試求這些三角形的個(gè)數(shù)？ 26例15. 設(shè)凸n邊形的任意3條對(duì)角線不相交于行內(nèi)一點(diǎn)，求它的對(duì)角線在行內(nèi)的交點(diǎn)總數(shù)。27例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 證明：我們將不定方程 的任意一組非負(fù)整數(shù)解 對(duì)應(yīng)于一個(gè)由n個(gè)圓圈“”，k-1個(gè)豎線“|”組成的如下排列：|，其中第一根豎線“

11、|”的左側(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ù)為 。2923容斥原理30例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é)

12、兩門(mén)課的學(xué)生有22人；同時(shí)修三門(mén)課的學(xué)生有3人。問(wèn)這個(gè)學(xué)校共有多少學(xué)生？31例19. 求a，b，c，d，e，f這六個(gè)字母的全排列中不允許出現(xiàn)ace和df圖像的排列數(shù)。3233例21. 求由a，b，c，d這4個(gè)字符構(gòu)成的n位數(shù)字串中，a，b，c至少出現(xiàn)一次的符號(hào)串的數(shù)目。3435同理3637練習(xí)題1給定2003個(gè)集合，每個(gè)集合都恰含有44個(gè)元素，并且每?jī)蓚€(gè)集合都恰有一個(gè)公共元素，試求這2003個(gè)集合的并集中有多少個(gè)元素？2平面內(nèi)給定200個(gè)不同的點(diǎn)，證明：其中距離為單位長(zhǎng)的點(diǎn)對(duì)數(shù)小于2050。3以正n邊形的頂點(diǎn)為頂點(diǎn)的梯形共有多少個(gè)？38雜 題39 例1 運(yùn)動(dòng)會(huì)開(kāi)了n天（n1）,共發(fā)出m個(gè)獎(jiǎng)牌,

13、第一天發(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)牌?404142例2.幾個(gè)人在一起,使得其中存在有相同生日的概率至少為二分之一.即23人中,至少有一對(duì)生日相同的概率超過(guò)二分之一 43例3. 甲乙二人玩，在黑板上寫(xiě)數(shù)的游戲，規(guī)則是二人輪流在黑板上寫(xiě)一個(gè)不超過(guò)p的自然數(shù)，但禁止再寫(xiě)出黑板上已有的因數(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ù)分

14、成3組：（4，5）（7，9）（8，10）無(wú)論乙寫(xiě)哪一個(gè)，甲就寫(xiě)同組的另一個(gè)。（2）考察寫(xiě)數(shù)原則相同但取數(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例4. 甲乙兩人在畫(huà)有個(gè)方格的正方形場(chǎng)地上做游戲:甲先在場(chǎng)地中央畫(huà)一個(gè)星號(hào),乙則在放有星號(hào)的格子周?chē)?個(gè)格子中任選1個(gè)方格畫(huà)一個(gè)圓圈.然后甲再在某個(gè)與已畫(huà)有標(biāo)記的格子挨著的空格中畫(huà)一個(gè)星號(hào),并一直繼續(xù)下去.如果甲成功

15、地將星號(hào)畫(huà)入場(chǎng)地四角的任何一個(gè)角上的方格中,就算他獲勝.求證:不論乙怎么做,甲總可以獲勝.45例5.在33的正方形表格中填上如圖所示的9個(gè)數(shù)字,將該表進(jìn)行如下操作:每次操作是對(duì)表中相鄰兩數(shù)同時(shí)加上一個(gè)數(shù)(相鄰是指有公共邊的兩小格),問(wèn)能否經(jīng)過(guò)若干次操作使得（1）表格中各數(shù)均為0；（2）表格中四個(gè)角的數(shù)為1,其余均為0.03267049546解答:(1) 能夠得到.事實(shí)上經(jīng)過(guò)5次操作即可.03267049501067049501067005501067000001001000000000000047(2) 考慮這種操作的一般形式:abcdefghk為此,設(shè)表格中第一行的數(shù)從左到右為a,b,c.第

16、二行的數(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)滿足題目要求的操作.abcdefghk48例6.凸n邊形的任意3條對(duì)角線不相交于形內(nèi)一點(diǎn)，求這些對(duì)角線將凸n邊形分成的區(qū)域的個(gè)數(shù). 4950515253例7.已知平面上有4條直線,其中任何兩條都相交,任何三條都不交于一點(diǎn),于是在每條直線上都交得3個(gè)交點(diǎn),它們從直線上截出兩條線段,共得到8條線段.問(wèn)這8條線段的長(zhǎng)度能否分別為 (1) 1,2,3,4,5,6,7,8? (2) 互不相同的自然數(shù)? 54（2）8條線段的長(zhǎng)度可以是互不相同的自然數(shù)，見(jiàn)圖。55例8.一袋花生共1988顆,一只猴子第一天拿走一顆花生,從第二天起,每天拿走的都是以前各天的總和.如果到某天袋里的花生少于已拿走的總數(shù)時(shí),這一天它又從拿走一顆開(kāi)始,按原定的規(guī)律進(jìn)行新的一輪.如此繼續(xù)下去,那么這袋花生被猴子拿光時(shí)是第幾天?56練習(xí)題18個(gè)小圓片分別涂有4種顏色：紅、藍(lán)、白、