《組合數(shù)學(xué)》課件PPT

組合數(shù)學(xué)課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 習(xí)題二 2.1 證明：在一個至少有2人的小組中，總存在兩個人，他們在組內(nèi)所認(rèn)識的人數(shù)相同。證明：假設(shè)沒有人誰都不認(rèn)識：那么每個人認(rèn)識的人數(shù)都為1,n-1，由鴿巢原理知，n個人認(rèn)識的人數(shù)有n-1種，那么至少有2個人認(rèn)識的人數(shù)相同。 假設(shè)有1人誰都不認(rèn)識：那么其他n-1人認(rèn)識的人數(shù)都為1,n-2，由鴿巢原理知，n-1個人認(rèn)識的人數(shù)有n-2種，那么至少有2個人認(rèn)識的人數(shù)相同。假設(shè)至少有兩人誰都不認(rèn)識，則認(rèn)識的人數(shù)為0的至少有兩人。2.2 任取11個整數(shù)，求證其中至少有兩個數(shù)的差是10的整數(shù)倍。證明：對于任意的一個整數(shù)，它除以10的余數(shù)只能有10種情況：0，1，9?，F(xiàn)在有11個整數(shù)，由鴿巢原理知，至少有2個整數(shù)的余數(shù)相同，則這兩個整數(shù)的差必是10的整數(shù)倍。2.3 證明：平面上任取5個坐標(biāo)為整數(shù)的點，則其中至少有兩個點，由它們所連線段的中點的坐標(biāo)也是整數(shù)。2.3證明：有5個坐標(biāo)，每個坐標(biāo)只有4種可能的情況：（奇數(shù)，偶數(shù)）；（奇數(shù)，奇數(shù)）；（偶數(shù)，偶數(shù)）；（偶數(shù)，奇數(shù)）。由鴿巢原理知，至少有2個坐標(biāo)的情況相同。又要想使中點的坐標(biāo)也是整數(shù)，則其兩點連線的坐標(biāo)之和為偶數(shù)。因為 奇數(shù)+奇數(shù) = 偶數(shù) ； 偶數(shù)+偶數(shù)=偶數(shù)。因此只需找以上2個情況相同的點。而已證明：存在至少2個坐標(biāo)的情況相同。證明成立。2.4 一次選秀活動，每個人表演后可能得到的結(jié)果分別為“通過”、“淘汰”和“待定”，至少有多少人參加才能保證必有100個人得到相同的結(jié)果？證明： 根據(jù)推論2.2.1，若將3*（100-1）+1=298個人得到3種結(jié)果，必有100人得到相同結(jié)果。2.5 一個袋子里裝了100個蘋果、100個香蕉、100個橘子和100個梨。那么至少取出多少水果后能夠保證已經(jīng)拿出20個相同種類的水果？證明：根據(jù)推論2.2.1，若將4*（20-1）+ 1 = 77個水果取出，必有20個相同種類的水果。2.6 證明：在任意選取的n+2個正整數(shù)中存在兩個正整數(shù)，其差或和能被2n整除。（書上例題2.1.3）證明：對于任意一個整數(shù)，它除以2n的余數(shù)顯然只有2n種情況，即：0，1，2，2n-2，2n-1。而現(xiàn)在有任意給定的n+2個整數(shù)，我們需要構(gòu)造n+1個盒子，即對上面2n個余數(shù)進行分組，共n+1組： 0,1，2n-1,2，2n-2,3,2n-3,，n-1,n+1，n。根據(jù)鴿巢原理，n+2個整數(shù)，必有兩個整數(shù)除以2n落入上面n+1個盒子里中的一個，若是0或n則說明它們的和及差都能被2n整除；若是剩下n-1組，因為一組有兩個余數(shù)，余數(shù)相同則它們的差能被2n整除，不同則它們的和能被2n整除。證明成立。2.7 一個網(wǎng)站在9天中被訪問了1800次，證明：存在連續(xù)的3天，這個網(wǎng)站的訪問量超多600次。證明： 設(shè)網(wǎng)站在9天中訪問數(shù)分別為a1，a2，.，a9 其中a1+a2+.+a9 = 1800， 令a1+a2+a3 = b1，a4+a5+a6 = b2，a7+a8+a9 = b3因為（b1+b2+b3）/3 = 600 由推論2.2.2知，b1，b2，b3中至少有一個數(shù)大于等于600。 所以存在有連續(xù)的三天，訪問量大于等于600次。2.8 將一個矩形分成5行41列的網(wǎng)格，每個格子涂1種顏色，有4種顏色可以選擇，證明：無論怎樣涂色，其中必有一個由格子構(gòu)成的矩形的4個角上的格子被涂上同一種顏色。證明：首先對一列而言，因為有5行，只有4只顏色選擇，根據(jù)鴿巢原理，則必有兩個單元格的顏色相同。另外，每列中兩個單元格的不同位置組合有=10種，這樣一列中兩個同色單元格的位置組合共有10*4=40種情況。 而現(xiàn)在共有41列，根據(jù)鴿巢原理，無論怎樣涂色，則必有兩列相同，也就是必有一個由格子構(gòu)成的矩形的4個角上的格子是同一顏色。2.9 將一個矩形分成(m+1)行列的網(wǎng)格每個格子涂1種顏色，有m種顏色可以選擇，證明：無論怎么涂色，其中必有一個由格子構(gòu)成的矩形的4個角上的格子被涂上同一種顏色。證明： （1）對每一列而言，有（m+1）行，m種顏色，有鴿巢原理，則必有兩個單元格顏色相同。 （2）每列中兩個單元格的不同位置組合有種，這樣一列中兩個同色單元格的位置組合共有 種情況 （3）現(xiàn)在有列，根據(jù)鴿巢原理，必有兩列相同。證明結(jié)論成立。2.10 一名實驗員在50天里每天至少做一次實驗，而實驗總次數(shù)不超過75。證明一定存在連續(xù)的若干天，她正好做了24次實驗。證明：令b1，b2，.，b50 分別為這50天中他每天的實驗數(shù)，并做部分和 a1 = b1，a2 = b1+b2 ，。a50 = b1+b2+.+b50 .由題，bi=1(1=i=50)且a50=75所以 1=a1a2a3a50=75 (*)考慮數(shù)列 a1，a2，.，a50，a1+24，a2+24，a50+24，它們都在1與75+24=99之間。由鴿巢原理知，其中必有兩項相等。由（*）知，a1，a2，.，a50互不相等，從而a1+24，.a50+24 也互不相等，所以一定存在1=ij1,f(1)=2 f(n)可以由f(n)來生成，當(dāng)在f(n)個大圓的基礎(chǔ)上，在球面上再加上第n+1個大圓時，它同前n個大圓共得到2n個交點(因無三個大圓相交于一點)，而每增加一個交點就增加一個新的面，故共增加2n個面。所以有f(n+1)= f(n)+2n。設(shè)P是平面上n個連通區(qū)域D1,D2,Dn的公共交界點，如下圖所示?，F(xiàn)用k種顏色對其著色，要求有公共邊界的相鄰區(qū)域著以不同的顏色，令f(n)表示不同的著色方案。，求它所滿足的遞推關(guān)系。有： f(n)= (k-1)f(n-2)+(k-2)f(n-1) （n4） f(2)=k(k-1) ， f(3)=k(k-1)(k-2)(1) 有D1與Dn-1同色，此時Dn有k-1種方案，可將D1與D n-2看成相鄰區(qū)域，則D1,D2, , Dn-2的著色方案為f(n-2)。(2) D1與Dn-1異色，此時Dn有k-2種方案，可將，則D1,D2, , Dn-1的著色方案為f(n-1)。(k-1)f(n-2)+(k-2)f(n-1)另有：f(n)=k(k-1)n-1-f(n-1) 第七章例n種顏色涂色裝有7顆珠子的手鐲，如果只考慮手鐲的旋轉(zhuǎn)，求有多少種涂色方案？ 解 對象集D1,2,3,4,5,6,7，顏色集是R(1,2,3,n)，D上的置換群Gg0,g1,g2,g6，其中g(shù)i表示旋轉(zhuǎn)360*i/7，因7是質(zhì)數(shù)，所以除(g0)7外，其它(gi)1，(i=1,2,3,4,5,6)，代入Polya公式，得L1/7*n7+6n而四邊形：轉(zhuǎn)180時