數(shù)學(xué)競賽之組合數(shù)學(xué)選講市公開課一等獎百校聯(lián)賽特等獎?wù)n件

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

地圖著色問題

中國郵差問題船夫過河問題任務(wù)分配問題第2頁3

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

若A為單位圓圓心，

結(jié)論顯然成立。

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

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

解答:將平面按圖分成九個抽屜,i號小方格全體為第i個抽屜.個點分放在九個抽屜中,最少有一個抽屜含有223個點,因為個點中任兩點距離均大于,所以此223個點距離均大于,它們中沒有兩點屬于同一小方格,而同號方格又不在同一方格中任兩點距離都大于2.

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

利用討論“極端”對象來實現(xiàn)問題處理解題方法稱為用極端原了解題，慣用極端原理基于下述簡單事實：

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

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

解答：對n個點中任兩點作連線m，

并取連線外點P（必存在），

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

因為點為有限個，連線m為有限條，

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

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

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

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

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

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

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

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

同時C也不是可去選手,C代替A,

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

E和C未勝過,去掉C后,D和E勝過對手

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

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

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

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

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

若依然每種顏色頂點最少有二個,

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

最終可得某種顏色只有一個,

能夠如圖給出分劃.

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

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

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

稱為第二類剖分點。如圖中F，G，H

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

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

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

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

第28頁29

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

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

例1

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

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

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

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

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

（2）考查寫數(shù)標準相同但取數(shù)范圍不是由1到1000而是由2到1000這個游戲。假如這個游戲先寫者有必勝策略，那么甲對原來游戲只要照搬就行了。因為甲寫下一個自然數(shù)后，乙是不能寫1。假如新游戲先寫數(shù)人沒有獲勝策略，即他只能告負，那么甲在原游戲中能夠先寫1，從而將失敗留給了乙?？梢?，甲總有獲勝策略。第44頁45例4.

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

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

第二行數(shù)從左到右為d,e,f.第三行數(shù)從左到右為g,h,k.按操作規(guī)則,任意相鄰數(shù)都加同一個數(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要到達狀態(tài)S值為S=(1+1+0+1+1)-(0+0+0+0)=4所以不能實現(xiàn)滿足題目要求操作.abcdefghk第48頁49例6.凸n邊形任意3條對角線不相交于形內(nèi)一點，求這些對角線將凸n邊形分成區(qū)域個數(shù).

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

問這8