《組合數學課件--第三章第四節(jié) 鴿巢原理》由會員分享，可在線閱讀，更多相關《組合數學課件--第三章第四節(jié) 鴿巢原理（38頁珍藏版）》請在裝配圖網上搜索。

1、,*,第,3,章 容斥原理與鴿巢原理,3.1 De Morgan,定理,3.2,容斥原理,3.3,容斥原理舉例,3.4,棋盤多項式與有限制的排列,3.5,有禁區(qū)的排列,3.6,廣義的容斥原理,3.7,廣義容斥原理的應用,2.8,第二類,Stirling,數的展開式,2.9,歐拉函數,(n),2.10 n,對夫妻問題,*,2.11,Mobius,反演定理,2.12,鴿巢原理,2.13,鴿巢原理舉例,2.14,鴿巢原理的推廣,*,2.15 Ramsey,數,1,3.12,鴿巢原理,1,、,366,個人中必然有至少兩人生日相同,(,不包括閏年,),；,2,、抽屜里散放著,10,雙手套，從中任意抽取,

2、11,只，其中至少有兩只是成雙的；,3,、某次會議有,n,位代表參加，則至少有兩個人認識的人數是一樣的；,4,、任給,5,個整數，其中至少有,3,個數的和被,3,除盡；,2,鴿巢原理：,n,個鴿子巢，若有,n+1,只鴿子在里面，則至少有一個巢里的鴿子數不少于,2,。,抽屜原理：如果把,n+1,個物體放到,n,個抽屜里，則必有一個抽屜里至少放了兩個物體。,3.12,鴿巢原理,3,3.13.1,任取,11,個數，求證其中至少有兩個數它們的差是,10,的倍數。,證明：,一個數是不是,10,的倍數取決于這個數的個位數是不是,0,，是,0,就是,10,的倍數；,一個數的個位數只可能是,0,1,.,9,十

3、個數，任取,11,個數，其中必有兩個數個位數相同，,那么這兩個數的差的個位數必然是,0,。,3.13,鴿巢原理舉例,4,例,3.13.2,設,a,1,a,2,a,m,。是正整數的序列，則至少存在整數,k,和,L,1k,Lm,使得和,a,k,+a,k+1,+,a,L,是,m,的倍數。,證明：,有兩種可能：,(1),若有一個,s,h,是,m,的倍數，那么上式成立。,構造一個序列,s,1,=a,1,s,2,=a,1,+a,2,s,3,=a,1,+a,2,+a,3,s,m,=a,1,+a,2,+a,m,則,s,1,s,2,s,m,3.13,鴿巢原理舉例,5,(2),設在上面的序列中沒有任何一個元素是,

4、m,的倍數，,序列,s,1,=a,1,s,2,=a,1,+a,2,s,3,=a,1,+a,2,+a,3,s,m,=a,1,+a,2,+a,m,則,s,1,s,2,k,。,s,L,=a,1,+a,2,+a,k,+a,k+1,+,a,L,-),s,k,=a,1,+a,2,+,a,k,s,L,-s,k,=a,k+1,+,a,L,s,L,-s,k,=0 (mod m),也就是說：,s,L,-s,k,=a,k+1,+,a,L,是,m,倍數。,3.13,鴿巢原理舉例,7,3.13.3,A,是,1,2,.,2n,中任意,n+1,個數，試證至少存在一對,a,bA,使得,a,與,b,互素。,相鄰數互素；,證明：

5、,從,A,中任意取,n+1,個數，必有兩個數相鄰，相鄰數互素；,設這,n+1,個數為,a,1,a,2,a,n+1,，如果兩兩不相鄰；,構造序列,a,1,a,1,+1,a,2,a,2,+1,a,n,a,n,+1,a,n+1,，是,2n+1,個不同的正整數；,與已知條件矛盾。,3.13,鴿巢原理舉例,8,例,3.13.4,設,a,1,a,2,a,100,是由,1,和,2,組成的序列，已知從其中任意一個數開始的連續(xù),10,個數的和不超過,16,，即對于,1i91,恒有,a,i,+a,i+1,+a,i+9,16,則至少存在,h,和,k,，,kh,使得,a,h+1,+,a,k,=39,證明：,s,100

6、,=(a,1,+a,2,+a,10,)+,(a,11,+a,12,+a,20,)+,+,(a,91,+a,92,+a,100,),根據條件：,s,100,1016=160,作序列,s,1,=a,1,s,2,=a,1,+a,2,s,100,=a,1,+a,2,+a,100,。由于每個,a,i,都是正整數，因此：,s,1,s,2,9n-36,X,的非空子集的數目？,C(9,1)+C(9,2)+C(9,9),X,的任何子集的元素和都小于或等于,9n-36,解這個不等式可得：,n60.77,n,是正整數，因此,n,60,因此：,9n60,。,=2,9,-1=511,3.13,鴿巢原理舉例,*,15,3

7、.14,鴿巢原理的推廣,推廣形式之一,設,k,和,n,都是任意的正整數，若至少有,kn+1,只鴿子分配在,n,個鴿巢里，則至少存在一個鴿巢中有不少于,k+1,只鴿子。,推論,3.7 m,只鴿子，,n,個鴿巢，則至少有一個鴿巢里有不少于,只鴿子。,16,推論,3.8,若取,n(m-1)+1,個球放進,n,個盒子，則至少有,1,個盒子的球數不少于,m,個。,推論,3.9,若,m,1,m,2,m,n,是,n,個正整數，而且,則,m,1,m,2,m,n,中至少有,1,個數不小于,r,。,3.14,鴿巢原理的推廣,17,例,3.14.8,：設,A=,a,1,a,2,a,20,是,10,個,0,和,10,

8、個,1,組成的,20,位進制數。,B=b,1,b,2,b,20,是任意的,20,位,2,進制數。,C=,b,1,b,2,b,20,b,1,b,2,b,20,=C,1,C,2,C,40,則存在某個,i,1i21,使得,C,i,C,i+1,C,i+19,與,a,1,a,2,a,20,至少有,10,位對應數字相同。,.,.,.,.,.,.,A,C,第,i,格,第,i+19,格,1 2 19 20 1 2 19 20,1 2 ,19 20 1 19 20,B,3.14,鴿巢原理的推廣,18,.,A,1 2 19 20,4,、,因,此必有一次相同數字的格數不少于,10,位,1,、假想著,A,如圖所示從左

9、向右一格一格移動。,2,、在移動到最后時。每一個,b,j,都遍歷了,a,1,a,2,a,20,。因為,A,中有,10,個,0,和,10,個,1,，每一個,b,j,都有,10,位次對應相等。,3,、在,20,次的移動過程中共有,1020=200,位次對應相等。,.,.,.,.,C,1 2 ,19 20 1 19 20,3.14,鴿巢原理的推廣,19,定理,.7,若序列,的,n,2,+1,個元素是不相等的實數，則從這個序列中至少可選出一組由,n+1,個元素組成的或為單調增或為單調減的子序列。,例如：對于序列：,5,3,16,10,15,14,9,11,6,7,。共,3,2,+1,個元素。,證明,1

10、,：從序列中的每一個元素,a,i,向后可選出若干個單調增子序列，其中有一個元素最多的單調增子序列，設其元素個數為,l,i,i,=1,2,n,2,+1,于是得一序列,3.14,鴿巢原理的推廣,20,1,：若序列,(L),中有一個元素,l,k,n+1,則定理得證。,2,：設不存在元素個數超過,n,的單調增子序列，即,:,根據鴿巢原理的推論,3.7,，至少存在,n+1,個：,的值相等,3.14,鴿巢原理的推廣,21,設,k,1,k,2,k,n+1,已知條件中,a,l,是不同的實數，則有如下結論,如若不然，設,k,i,k,j,有,a,ki,b,2,a,-2,b,=(,h-m)n,2,b,(2,a-b,

11、-1)=(h-m)n,2,a-b,-1,即為所求：,3.14,鴿巢原理的推廣,28,例,3.14.11,：能否在一個,n,n,的棋盤的每個方格填上,1,2,或,3,，使得棋盤上各行各列以及對角線上的數字之和都不相等。,解：,棋盤上各行各列以及對角線上的數字之和共有,2n+2,個數。,從,1,2,或,3,中取,n,個數，,答案是否定的,。,從,1,2,或,3,中取,n,個數，最大和值是,3n,最小和值是,n,共有,2n+1,個數值。,3.14,鴿巢原理的推廣,29,例,3.14.12,試證,6,個人在一起，其中至少存在,3,個人或互相認識，或互相不認識。,v,a,v,b,v,c,v,d,v,e,

12、v,f,不認識的兩個人對應,的頂點聯線著藍色。,6,個人設為,A,B,C,D,E,F,分別用,6,個頂點,v,a,v,b,v,c,v,d,v,e,v,f,表示，過此,6,個頂點作完全圖，互相認識的兩個人，對應頂點的連線著紅色。,3.14,鴿巢原理的推廣,30,問題等價于證明這,6,個頂點的完全圖的邊，用紅、藍二色任意著色，必然至少存在一個紅色邊三角形，或者存在一個藍色邊三角形。,v,a,v,b,v,c,v,d,v,e,v,f,3.14,鴿巢原理的推廣,31,在圖論中經常用補圖的概念來表述：,6,個頂點的圖,G,中要么有一個三角形，要么圖,G,的補圖中有一個三角形。,v,a,v,b,v,c,v,

13、d,v,e,v,f,圖,G,v,a,v,b,v,c,v,d,v,e,v,f,圖,G,的補圖,3.14,鴿巢原理的推廣,32,Va,點和其他,5,個頂點相連有,5,條邊，每條邊或著以紅色，或著以藍色。依據鴿巢原理，其中至少有,3,條邊同色，不妨假定有,3,條邊著以紅色，,v,a,v,b,v,c,v,d,v,e,v,f,3,條邊的另外,3,個端點設為,v,e,v,d,v,b,。,這,3,個端點間的聯線或同色或不同色，,若同色。則已存在一個同色三角形，如果不同色，則至少有一條邊是紅色，,3.14,鴿巢原理的推廣,33,對于,A,以外的,5,個人可分為,Friend,和,Strange,兩個集合。,F

14、riend=,其余,5,人中與,A,互相認識的集合；,Strange=,其余,5,人中與,A,不認識的人的集合；,依據鴿巢原理，,Friend,和,Strange,中有一個集合至少有,3,個人，首先假設是集合,friend,。,Friend,中所有人若是彼此互相不認識，則問題已得到證明，,否則有兩個人互相認識，不妨設這兩個人是,P,和,Q,，則,A,，,P,，,Q,這,3,個人彼此認識。,3.14,鴿巢原理的推廣,34,否則設,L,和,M,互不相識，則,A,L,M,互不相識。,若是,Strange,至少有,3,個人,可以同樣討論如下,:,若,Strange,中所有人彼此互相認識,則問題的條件已

15、得到滿足,3.14,鴿巢原理的推廣,35,|,Friend,|3?,Friend,中人,互不相識？,Friend,有,3,人,互不相識。,Friend,有,P,，,Q,二人互相認識,A,P,Q,互相認識,Strange,中人,互相認識？,Strange,有,3,人,互相認識。,Strange,有,L,M,互不相識？,Y,N,Y,N,Y,N,A,L,M,互不相識？,推理過程如下：,A,以外的,5,個人,36,3.11.3,推廣形式之二,定理,3.12,設有,p,1,+p,2,+p,n,-n+1,只鴿子，有標號分別為：,1,2,n,的鴿巢，則存在至少一個標號為,j,的鴿巢至少有,p,j,只鴿子，,j=1,2,n,。,3.14,鴿巢原理的推廣,*,37,一對常數,a,和,b,，對應于一個整數,r,使得,r,個人或,a,個人互相認識，或有,b,個互不認識；,（或有,a,個人互不認識，或有,b,個人互相認識，）,這個數,r,的最小值用,R(a,b,),來表示。,稱作,Ramsey,數,3.15 Ramsey,數,*,R(3,3)=6,，,R(3,4)=9,R(4,4)=18,38,