13高三畢業(yè)班數學課本知識點整理歸納之十三 第十三章 排列組合與概率.doc

2010-2011年高三畢業(yè)班數學課本知識點整理歸納之十三第十三章 排列組合與概率一、基礎知識1加法原理：做一件事有n類辦法，在第1類辦法中有m1種不同的方法，在第2類辦法中有m2種不同的方法，在第n類辦法中有mn種不同的方法，那么完成這件事一共有n=m1+m2+mn種不同的方法。2乘法原理：做一件事，完成它需要分n個步驟，第1步有m1種不同的方法，第2步有m2種不同的方法，第n步有mn種不同的方法，那么完成這件事共有n=m1m2mn種不同的方法。3排列與排列數：從n個不同元素中，任取m(mn)個元素，按照一定順序排成一列，叫做從n個不同元素中取出m個元素的一個排列，從n個不同元素中取出m個(mn)元素的所有排列個數，叫做從n個不同元素中取出m個元素的排列數，用表示，=n(n-1)(n-m+1)=,其中m,nn,mn,注：一般地=1，0！=1，=n!。4n個不同元素的圓周排列數為=(n-1)!。5組合與組合數：一般地，從n個不同元素中，任取m(mn)個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合，即從n個不同元素中不計順序地取出m個構成原集合的一個子集。從n個不同元素中取出m(mn)個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數，用表示：6組合數的基本性質：（1）；（2）；（3）；（4）；（5）；（6）。7定理1：不定方程x1+x2+xn=r的正整數解的個數為。證明將r個相同的小球裝入n個不同的盒子的裝法構成的集合為a，不定方程x1+x2+xn=r的正整數解構成的集合為b，a的每個裝法對應b的唯一一個解，因而構成映射，不同的裝法對應的解也不同，因此為單射。反之b中每一個解(x1,x2,xn),將xi作為第i個盒子中球的個數，i=1,2,n，便得到a的一個裝法，因此為滿射，所以是一一映射，將r個小球從左到右排成一列，每種裝法相當于從r-1個空格中選n-1個，將球分n份，共有種。故定理得證。推論1 不定方程x1+x2+xn=r的非負整數解的個數為推論2 從n個不同元素中任取m個允許元素重復出現的組合叫做n個不同元素的m可重組合，其組合數為8二項式定理：若nn+,則(a+b)n=.其中第r+1項tr+1=叫二項式系數。9隨機事件：在一定條件下可能發(fā)生也可能不發(fā)生的事件叫隨機事件。在大量重復進行同一試驗時，事件a發(fā)生的頻率總是接近于某個常數，在它附近擺動，這個常數叫做事件a發(fā)生的概率，記作p(a),0p(a)1.10.等可能事件的概率，如果一次試驗中共有n種等可能出現的結果，其中事件a包含的結果有m種，那么事件a的概率為p(a)=11.互斥事件：不可能同時發(fā)生的兩個事件，叫做互斥事件，也叫不相容事件。如果事件a1，a2，an彼此互斥，那么a1，a2，an中至少有一個發(fā)生的概率為p(a1+a2+an)= p(a1)+p(a2)+p(an).12對立事件：事件a，b為互斥事件，且必有一個發(fā)生，則a，b叫對立事件，記a的對立事件為。由定義知p(a)+p()=1.13相互獨立事件：事件a（或b）是否發(fā)生對事件b（或a）發(fā)生的概率沒有影響，這樣的兩個事件叫做相互獨立事件。14相互獨立事件同時發(fā)生的概率：兩個相互獨立事件同時發(fā)生的概率，等于每個事件發(fā)生的概率的積。即p(ab)=p(a)p(b).若事件a1，a2，an相互獨立,那么這n個事件同時發(fā)生的概率為p(a1a2 an)=p(a1)p(a2) p(an).15.獨立重復試驗:若n次重復試驗中,每次試驗結果的概率都不依賴于其他各次試驗的結果,則稱這n次試驗是獨立的.16.獨立重復試驗的概率:如果在一次試驗中,某事件發(fā)生的概率為p,那么在n次獨立重復試驗中,這個事件恰好發(fā)生k次的概率為pn(k)=pk(1-p)n-k.17離散型隨機為量的分布列：如果隨機試驗的結果可以用一個變量來表示，那么這樣的變量叫隨機變量，例如一次射擊命中的環(huán)數就是一個隨機變量，可以取的值有0,1,2,10。如果隨機變量的可能取值可以一一列出，這樣的隨機變量叫離散型隨機變量。一般地，設離散型隨機變量可能取的值為x1,x2,xi,取每一個值xi(i=1,2,)的概率p(=xi)=pi，則稱表x1x2x3xipp1p2p3pi為隨機變量的概率分布，簡稱的分布列，稱e=x1p1+x2p2+xnpn+為的數學期望或平均值、均值、簡稱期望，稱d=(x1-e)2p1+(x2-e)2p2+(xn-e)2pn+為的均方差，簡稱方差。叫隨機變量的標準差。18二項分布：如果在一次試驗中某事件發(fā)生的概率是p，那么在n次獨立重復試驗中，這個事件恰好發(fā)生k次的概率為p(=k)=, 的分布列為01xinp此時稱服從二項分布，記作b(n,p).若b(n,p)，則e=np,d=npq,以上q=1-p.19.幾何分布：在獨立重復試驗中，某事件第一次發(fā)生時所做試驗的次數也是一個隨機變量，若在一次試驗中該事件發(fā)生的概率為p，則p(=k)=qk-1p(k=1,2,)，的分布服從幾何分布，e=，d=(q=1-p).二、方法與例題1乘法原理。例1 有2n個人參加收發(fā)電報培訓，每兩個人結為一對互發(fā)互收，有多少種不同的結對方式？解 將整個結對過程分n步，第一步，考慮其中任意一個人的配對者，有2n-1種選則；這一對結好后，再從余下的2n-2人中任意確定一個。第二步考慮他的配對者，有2n-3種選擇，這樣一直進行下去，經n步恰好結n對，由乘法原理，不同的結對方式有(2n-1)(2n-3)31=2加法原理。例2 圖13-1所示中沒有電流通過電流表，其原因僅因為電阻斷路的可能性共有幾種？解 斷路共分4類：1）一個電阻斷路，有1種可能，只能是r4；2）有2個電阻斷路，有-1=5種可能；3）3個電阻斷路，有=4種；4）有4個電阻斷路，有1種。從而一共有1+5+4+1=11種可能。3插空法。例3 10個節(jié)目中有6個演唱4個舞蹈，要求每兩個舞蹈之間至少安排一個演唱，有多少種不同的安排節(jié)目演出順序的方式？解 先將6個演唱節(jié)目任意排成一列有種排法，再從演唱節(jié)目之間和前后一共7個位置中選出4個安排舞蹈有種方法，故共有=604800種方式。4映射法。例4 如果從1，2，14中，按從小到大的順序取出a1,a2,a3使同時滿足：a2-a13,a3-a23，那么所有符合要求的不同取法有多少種？解 設s=1,2,14，=1，2，10；t=(a1,a2,a3)| a1,a2,a3s,a2-a13,a3-a23,=(),若，令，則(a1,a2,a3)t,這樣就建立了從到t的映射，它顯然是單射，其次若(a1,a2,a3)t,令，則，從而此映射也是滿射，因此是一一映射，所以|t|=120，所以不同取法有120種。5貢獻法。例5 已知集合a=1，2，3，10，求a的所有非空子集的元素個數之和。解 設所求的和為x，因為a的每個元素a，含a的a的子集有29個，所以a對x的貢獻為29，又|a|=10。所以x=1029.另解 a的k元子集共有個，k=1,2,10，因此，a的子集的元素個數之和為1029。6容斥原理。例6 由數字1，2，3組成n位數(n3)，且在n位數中，1，2，3每一個至少出現1次，問：這樣的n位數有多少個？解 用i表示由1，2，3組成的n位數集合，則|i|=3n，用a1，a2，a3分別表示不含1，不含2，不含3的由1，2，3組成的n位數的集合，則|a1|=|a2|=|a3|=2n，|a1a2|=|a2a3|=|a1a3|=1。|a1a2a3|=0。所以由容斥原理|a1a2a3|=32n-3.所以滿足條件的n位數有|i|-|a1a2a3|=3n-32n+3個。7遞推方法。例7 用1，2，3三個數字來構造n位數，但不允許有兩個緊挨著的1出現在n位數中，問：能構造出多少個這樣的n位數？解 設能構造an個符合要求的n位數，則a1=3，由乘法原理知a2=33-1=8.當n3時：1）如果n位數的第一個數字是2或3，那么這樣的n位數有2an-1；2）如果n位數的第一個數字是1，那么第二位只能是2或3，這樣的n位數有2an-2，所以an=2(an-1+an-2)(n3).這里數列an的特征方程為x2=2x+2，它的兩根為x1=1+,x2=1-,故an=c1(1+)n+ c2(1+)n,由a1=3,a2=8得，所以8算兩次。例8 m,n,rn+，證明： 證明 從n位太太與m位先生中選出r位的方法有種；另一方面，從這n+m人中選出k位太太與r-k位先生的方法有種，k=0,1,r。所以從這n+m人中選出r位的方法有種。綜合兩個方面，即得式。9母函數。例9 一副三色牌共有32張，紅、黃、藍各10張，編號為1，2，10，另有大、小王各一張，編號均為0。從這副牌中任取若干張牌，按如下規(guī)則計算分值：每張編號為k的牌計為2k分，若它們的分值之和為2004，則稱這些牌為一個“好牌”組，求好牌組的個數。解 對于n1,2,2004,用an表示分值之和為n的牌組的數目，則an等于函數f(x)=(1+)2(1+)3(1+)3的展開式中xn的系數（約定|x|1），由于f(x)= (1+)(1+)(1+)3=3 =3。而02004211，所以an等于的展開式中xn的系數，又由于=(1+x2+x3+x2k+)1+2x+3x2+(2k+1)x2k+,所以x2k在展開式中的系數為a2k=1+3+5+(2k+1)=(k+1)2,k=1,2,從而，所求的“好牌”組的個數為a2004=10032=1006009.10組合數的性質。例10 證明：是奇數(k1).證明 =令i=pi(1ik)，pi為奇數，則，它的分子、分母均為奇數，因是整數，所以它只能是若干奇數的積，即為奇數。例11 對n2,證明：證明 1）當n=2時，22=642；2）假設n=k時，有2k4k,當n=k+1時，因為又4，所以2k+1.所以結論對一切n2成立。11二項式定理的應用。例12 若nn, n2，求證：證明 首先其次因為，所以 2+得證。例13 證明：證明 首先，對于每個確定的k，等式左邊的每一項都是兩個組合數的乘積，其中是(1+x)n-k的展開式中xm-h的系數。是(1+y)k的展開式中yk的系數。從而就是(1+x)n-k(1+y)k的展開式中xm-hyh的系數。于是，就是展開式中xm-hyh的系數。另一方面，= =(xk-1+xk-2y+yk-1)，上式中，xm-hyh項的系數恰為。所以12概率問題的解法。例14 如果某批產品中有a件次品和b件正品，采用有放回的抽樣方式從中抽取n件產品，問：恰好有k件是次品的概率是多少？解 把k件產品進行編號，有放回抽n次，把可能的重復排列作為基本事件，總數為(a+b)n（即所有的可能結果）。設事件a表示取出的n件產品中恰好有k件是次品，則事件a所包含的基本事件總數為akbn-k，故所求的概率為p(a)=例15 將一枚硬幣擲5次，正面朝上恰好一次的概率不為0，而且與正面朝上恰好兩次的概率相同，求恰好三次正面朝上的概率。解 設每次拋硬幣正面朝上的概率為p，則擲5次恰好有k次正面朝上的概率為(1-p)5-k(k=0,1,2,5)，由題設，且0p1，化簡得，所以恰好有3次正面朝上的概率為例16 甲、乙兩個乒乓球運動員進行乒乓球比賽，已知每一局甲勝的概率為0.6，乙勝的概率為0.4，比賽時可以用三局二勝或五局三勝制，問：在哪一種比賽制度下，甲獲勝的可能性大？解 （1）如果采用三局兩勝制，則甲在下列兩種情況下獲勝：a12：0（甲凈勝二局），a22：1（前二局甲一勝一負，第三局甲勝）. p(a1)=0.60.6=0.36,p(a2)=0.60.40.6=0.288.因為a1與a2互斥，所以甲勝概率為p(a1+a2)=0.648.(2)如果采用五局三勝制，則甲在下列三種情況下獲勝：b13：0（甲凈勝3局），b23：1（前3局甲2勝1負，第四局甲勝），b33：2（前四局各勝2局，第五局甲勝）。因為b1，b2，b2互斥，所以甲勝概率為p(b1+b2+b3)=p(b1)+p(b2)+p(b3)=0.63+0.620.40.6+0.620.420.6=0.68256.由（1），（2）可知在五局三勝制下，甲獲勝的可能性大。例17 有a，b兩個口袋，a袋中有6張卡片，其中1張寫有0，2張寫有1，3張寫有2；b袋中有7張卡片，其中4張寫有0，1張寫有1，2張寫有2。從a袋中取出1張卡片，b袋中取2張卡片，共3張卡片。求：（1）取出3張卡片都寫0的概率；（2）取出的3張卡片數字之積是4的概率；（3）取出的3張卡片數字之積的數學期望。解（1）；（2）；（3）記為取出的3張卡片的數字之積，則的分布為0248p所以三、基礎訓練題1三邊長均為整數且最大邊長為11的三角形有_個。2在正2006邊形中，當所有邊均不平行的對角線的條數為_。3用1，2，3，9這九個數字可組成_個數字不重復且8和9不相鄰的七位數。410個人參加乒乓球賽，分五組，每組兩個人有_種分組方法。5以長方體的頂點為頂點的三棱錐的個數是_。6今天是星期二，再過101000天是星期_。7由展開式所得的x的多項式中，系數為有理數的共有_項。8如果凸n邊形(n4)的任意三條對角線不共點，那么這些對角線在凸n邊形內共有_個交點。9袋中有a個黑球與b個白球，隨機地每次從中取出一球（不放回），第k(1ka+b)次取到黑球的概率為_。10一個箱子里有9張卡片，分別標號為1，2，9，從中任取2張，其中至少有一個為奇數的概率是_。11某人拿著5把鑰匙去開門，有2把能打開。他逐個試，試三次之內打開房門的概率是_。12馬路上有編號為1，2，3，10的十盞路燈，要將其中三盞關掉，但不能同時關掉相鄰的兩盞或三盞，也不能關掉兩端的路燈，則滿足條件的關燈方法種數是_。13a,b,c,d,e五個人安排在一個圓桌周圍就坐，若a,b不相鄰有_種安排方式。14已知i,m,n是正整數，且1(1+n)m.15.一項“過關游戲”規(guī)定：在第n關要拋擲一顆骰子n次，如果這n次拋擲所得到的點數之和大于2n，則算過關。問：（1）某人在這項游戲中最多能過幾關？（2）他連過前三關的概率是多少？（注：骰子是一個在各面上分別有1，2，3，4，5，6點數的均勻正方體）四、高考水平訓練題1若n1,2,100且n是其各位數字和的倍數，則這種n有_個。2從-3,-2,-1,0,1,2,3,4中任取3個不同元素作為二次函數y=ax2+bx+c的系數，能組成過原點，且頂點在第一或第三象限的拋物線有_條。3四面體的頂點和各棱的中點共10個點，在其中任取4個不共面的點，有_種取法。4三個人傳球，從甲開始發(fā)球，每次接球后將球傳給另外兩人中的任意一個，經5次傳球后，球仍回到甲手中的傳法有_種。5一條鐵路原有m個車站（含起點，終點），新增加n個車站（n1），客運車票相應地增加了58種，原有車站有_個。6將二項式的展開式按降冪排列，若前三項系數成等差數列，則該展開式中x的冪指數是整數的項有_個。7從1到9這九個自然數中任取兩個分別作為對數的真數和底數，共可得到_種不同的對數值。8二項式(x-2)5的展開式中系數最大的項為第_項，系數最小的項為第_項。9有一批規(guī)格相同的均勻圓棒，每根被劃分成長度相同的5節(jié)，每節(jié)用紅、黃、藍三色之一涂色，可以有_種顏色不同的圓棒？（顛倒后相同的算同一種）10在1，2，2006中隨機選取3個數，能構成遞增等差數列的概率是_。11投擲一次骰子，出現點數1，2，3，6的概率均為，連續(xù)擲6次，出現的點數之和為35的概率為_。12某列火車有n節(jié)旅客車廂，進站后站臺上有m(mn)名旅客候車，每位旅客隨意選擇車廂上車，則每節(jié)車廂都有旅客上車的概率是_。13某地現有耕地10000公頃，規(guī)劃10年后糧食單產比現在增加22%，人均糧食占有量比現在提高10%，如果人口年增長率為1%，那么耕地平均每年至多只能減少多少公頃（精確到1公頃）？（糧食單產=）五、聯賽一試水平訓練題1若0abcd500，有_個有序的四元數組（a,b,c,d）滿足a+d=b+c且bc-ad=93.2.已知直線ax+by+c=0中的a,b,c是取自集合-3,-2,-1,0,1,2,3中的3個不同的元素，并且該直線傾斜角為銳角，這樣的直線條數是_。3已知a=0，1，2，3，4，5，6，7，映射f:aa滿足：（1）若ij，則f(i)f(j)；（2）若i+j=7，則f(i)+f(j)=7，這樣的映射的個數為_。41，2，3，4，5的排列a1,a2,a3,a4,a5具有性質：對于1i4,a1,a2,ai不構成1，2，i的某個排列，這種排列的個數是_。5骰子的六個面標有1，2，6這六個數字，相鄰兩個面上的數字之差的絕對值叫變差，變差的總和叫全變差v，則全變差v的最大值為_，最小值為_。6某次乒乓球單打比賽中，原計劃每兩名選手恰比賽一場，但有3名選手各比賽2場之后就退出了，這樣，全部比賽只進行50場，上述三名選手之間比賽場數為_。7如果a,b,c,d都屬于1,2,3,4且ab,bc,cd, da；且a是a,b,c,d中的最小值，則不同的四位數的個數為_。8如果自然數a各位數字之和等于7，那么稱a為“吉祥數”，將所有的吉祥數從小到大排成一列a1,a2,a3,若an=2005，則an=_。9求值：=_。10投擲一次骰子，出現點數1，2，6的概率均為，連續(xù)擲10次，出現的點數之和是30的概率為_。11將編號為1，2，9這九個小球隨機放置在圓周的九個等分點上，每個等分點上各有一個小球，設周圍上所有相鄰兩球的號碼之差的絕對值之和為s，求s達到最小值的放法的概率（注：如果某種放法經旋轉或鏡面反射后可與另一放法重合，則認為是相同的放法）。12甲、乙兩人輪流向同一目標射擊，第一次甲射擊，以后輪流射擊，甲每次擊中的概率為p(0p1)，乙每次擊中的概率為q(0q1)，求甲、乙首先擊中的概率各是多少？13設m,nn,0mn，求證：+六、聯賽二試水平訓練題1100張卡片上分別寫有數字1到100，一位魔術師把這100張卡片放入顏色分別是紅色、白色、藍色的三個盒子里，每個盒子里至少放入一張卡片。一位觀眾從三個盒子中挑出兩個，并從中各選取一張卡片，然后宣布這兩張卡片上的兩個數的和數，魔術師知道這個和數之后，便能夠指出哪一個是沒有被觀眾取出卡片的盒子。問：共有多少種放卡片的方法，使得這個魔術師總能夠成功？（如果至少有一張卡片被放入不同顏色的盒子，兩種方法被認為是不同的）2設s=1,2,10，a1，a2，ak是s的k個子集合，滿足：（1）|ai|=5,i=1,2,k;（2）|aiaj|2,1ijk，求k的最大值。3求從集合1,2,n中任取滿足下列條件的k個數j1,j2,jk的組合數；（1）1j1j21為固定的正整數；（3）存在h0,1h0k-1，使得m+1.4.設,其中s1，s2，sm都是正整數且s1s2sm，求證組合數中奇數的個數等于2m。5個不同的數隨機排成圖13-2所示的三角形陣，設mk是從上往下第k行中的最大數，求m1m2mn的概率。6證明：2010-2011年高三畢業(yè)班數學課本知識點整理歸納之十八第十八章 組合一、方法與例題1抽屜原理。例1 設整數n4,a1,a2,an是區(qū)間(0,2n)內n個不同的整數，證明：存在集合a1,a2,an的一個子集，它的所有元素之和能被2n整除。證明 （1）若na1,a2,an,則n個不同的數屬于n-1個集合1,2n-1，2,2n-2,n-1,n+1。由抽屜原理知其中必存在兩個數ai,aj(ij)屬于同一集合，從而ai+aj=2n被2n整除；（2）若na1,a2,an，不妨設an=n，從a1,a2,an-1(n-13)中任意取3個數ai, aj, ak(ai,aj0)不被n整除，考慮n個數a1,a2,a1+a2,a1+a2+a3,a1+a2+an-1。）若這n個數中有一個被n整除，設此數等于kn，若k為偶數，則結論成立；若k為奇數，則加上an=n知結論成立。）若這n個數中沒有一個被n整除，則它們除以n的余數只能取1,2,n-1這n-1個值，由抽屜原理知其中必有兩個數除以n的余數相同，它們之差被n整除，而a2-a1不被n整除，故這個差必為ai, aj, ak-1中若干個數之和，同）可知結論成立。2極端原理。例2 在nn的方格表的每個小方格內寫有一個非負整數，并且在某一行和某一列的交叉點處如果寫有0，那么該行與該列所填的所有數之和不小于n。證明：表中所有數之和不小于。證明 計算各行的和、各列的和，這2n個和中必有最小的，不妨設第m行的和最小，記和為k，則該行中至少有n-k個0，這n-k個0所在的各列的和都不小于n-k，從而這n-k列的數的總和不小于(n-k)2，其余各列的數的總和不小于k2，從而表中所有數的總和不小于(n-k)2+k23.不變量原理。俗話說，變化的是現象，不變的是本質，某一事情反復地進行，尋找不變量是一種策略。例3 設正整數n是奇數，在黑板上寫下數1，2，2n，然后取其中任意兩個數a,b,擦去這兩個數，并寫上|a-b|。證明：最后留下的是一個奇數。證明 設s是黑板上所有數的和，開始時和數是s=1+2+2n=n(2n+1)，這是一個奇數，因為|a-b|與a+b有相同的奇偶性，故整個變化過程中s的奇偶性不變，故最后結果為奇數。例4 數a1, a2,an中每一個是1或-1，并且有s=a1a2a3a4+ a2a3a4a5+ana1a2a3=0. 證明：4|n.證明 如果把a1, a2,an中任意一個ai換成-ai，因為有4個循環(huán)相鄰的項都改變符號，s模4并不改變，開始時s=0，即s0，即s0(mod4)。經有限次變號可將每個ai都變成1，而始終有s0(mod4)，從而有n0(mod4)，所以4|n。4構造法。例5 是否存在一個無窮正整數數列a1,a2a3，使得對任意整數a，數列中僅有有限個素數。證明 存在。取an=(n!)3即可。當a=0時，an中沒有素數；當|a|2時，若n|a|，則an+a均為|a|的倍數且大于|a|，不可能為素數；當a=1時，an1=(n!1)(n!)2n!+1，當3時均為合數。從而當a為整數時，(n!)3+a中只有有限個素數。例6 一個多面體共有偶數條棱，試證：可以在它的每條棱上標上一個箭頭，使得對每個頂點，指向它的箭頭數目是偶數。證明 首先任意給每條棱一個箭頭，如果此時對每個頂點，指向它的箭頭數均為偶數，則命題成立。若有某個頂點a，指向它的箭頭數為奇數，則必存在另一個頂點b，指向它的箭頭數也為奇數（因為棱總數為偶數），對于頂點a與b，總有一條由棱組成的“路徑”連結它們，對該路徑上的每條棱，改變它們箭頭的方向，于是對于該路徑上除a，b外的每個頂點，指向它的箭頭數的奇偶性不變，而對頂點a，b，指向它的箭頭數變成了偶數。如果這時仍有頂點，指向它的箭頭數為奇數，那么重復上述做法，又可以減少兩個這樣的頂點，由于多面體頂點數有限，經過有限次調整，總能使和是對每個頂點，指向它的箭頭數為偶數。命題成立。5染色法。例7 能否在55方格表內找到一條線路，它由某格中心出發(fā)，經過每個方格恰好一次，再回到出發(fā)點，并且途中不經過任何方格的頂點？解 不可能。將方格表黑白相間染色，不妨設黑格為13個，白格為12個，如果能實現，因黑白格交替出現，黑白格數目應相等，得出矛盾，故不可能。6凸包的使用。給定平面點集a，能蓋住a的最小的凸圖形，稱為a的凸包。例8 試證：任何不自交的五邊形都位于它的某條邊的同一側。證明 五邊形的凸五包是凸五邊形、凸四邊形或者是三角形，凸包的頂點中至少有3點是原五邊形的頂點。五邊形共有5個頂點，故3個頂點中必有兩點是相鄰頂點。連結這兩點的邊即為所求。7賦值方法。例9 由22的方格紙去掉一個方格余下的圖形稱為拐形，用這種拐形去覆蓋57的方格板，每個拐形恰覆蓋3個方格，可以重疊但不能超出方格板的邊界，問：能否使方格板上每個方格被覆蓋的層數都相同？說明理由。解 將57方格板的每一個小方格內填寫數-2和1。如圖18-1所示，每個拐形覆蓋的三個數之和為非負。因而無論用多少個拐形覆蓋多少次，蓋住的所有數字之和都是非負的。另一方面，方格板上數字的總和為12(-2)+231=-1，當被覆蓋k層時，蓋住的數字之和等于-k，這表明不存在滿足題中要求的覆蓋。-21-21-21-21111111-21-21-21-21111111-21-21-21-28圖論方法。例10 生產由六種顏色的紗線織成的雙色布，在所生產的雙色布中，每種顏色的紗線至少與其他三種顏色的紗線搭配過。證明：可以挑出三種不同的雙色布，它們包含所有的顏色。證明 用點a1，a2，a3，a4，a5，a6表示六種顏色，若兩種顏色的線搭配過，則在相應的兩點之間連一條邊。由已知，每個頂點至少連出三條邊。命題等價于由這些邊和點構成的圖中有三條邊兩兩不相鄰（即無公共頂點）。因為每個頂點的次數3，所以可以找到兩條邊不相鄰，設為a1a2，a3a4。（1）若a5與