組合數(shù)學(xué)課件--第三章第四節(jié) 鴿巢原理

《組合數(shù)學(xué)課件--第三章第四節(jié) 鴿巢原理》由會(huì)員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)課件--第三章第四節(jié) 鴿巢原理（38頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

4、m,的倍數(shù)，,序列,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,倍數(shù)。,3.13,鴿巢原理舉例,7,3.13.3,A,是,1,2,.,2n,中任意,n+1,個(gè)數(shù)，試證至少存在一對(duì),a,bA,使得,a,與,b,互素。,相鄰數(shù)互素；,證明：

5、,從,A,中任意取,n+1,個(gè)數(shù)，必有兩個(gè)數(shù)相鄰，相鄰數(shù)互素；,設(shè)這,n+1,個(gè)數(shù)為,a,1,a,2,a,n+1,，如果兩兩不相鄰；,構(gòu)造序列,a,1,a,1,+1,a,2,a,2,+1,a,n,a,n,+1,a,n+1,，是,2n+1,個(gè)不同的正整數(shù)；,與已知條件矛盾。,3.13,鴿巢原理舉例,8,例,3.13.4,設(shè),a,1,a,2,a,100,是由,1,和,2,組成的序列，已知從其中任意一個(gè)數(shù)開始的連續(xù),10,個(gè)數(shù)的和不超過,16,，即對(duì)于,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,),根據(jù)條件：,s,100,1016=160,作序列,s,1,=a,1,s,2,=a,1,+a,2,s,100,=a,1,+a,2,+a,100,。由于每個(gè),a,i,都是正整數(shù)，因此：,s,1,s,2,9n-36,X,的非空子集的數(shù)目？,C(9,1)+C(9,2)+C(9,9),X,的任何子集的元素和都小于或等于,9n-36,解這個(gè)不等式可得：,n60.77,n,是正整數(shù)，因此,n,60,因此：,9n60,。,=2,9,-1=511,3.13,鴿巢原理舉例,*,15,3

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

8、個(gè),1,組成的,20,位進(jìn)制數(shù)。,B=b,1,b,2,b,20,是任意的,20,位,2,進(jìn)制數(shù)。,C=,b,1,b,2,b,20,b,1,b,2,b,20,=C,1,C,2,C,40,則存在某個(gè),i,1i21,使得,C,i,C,i+1,C,i+19,與,a,1,a,2,a,20,至少有,10,位對(duì)應(yīng)數(shù)字相同。,.,.,.,.,.,.,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,、,因,此必有一次相同數(shù)字的格數(shù)不少于,10,位,1,、假想著,A,如圖所示從左

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

10、,：從序列中的每一個(gè)元素,a,i,向后可選出若干個(gè)單調(diào)增子序列，其中有一個(gè)元素最多的單調(diào)增子序列，設(shè)其元素個(gè)數(shù)為,l,i,i,=1,2,n,2,+1,于是得一序列,3.14,鴿巢原理的推廣,20,1,：若序列,(L),中有一個(gè)元素,l,k,n+1,則定理得證。,2,：設(shè)不存在元素個(gè)數(shù)超過,n,的單調(diào)增子序列，即,:,根據(jù)鴿巢原理的推論,3.7,，至少存在,n+1,個(gè)：,的值相等,3.14,鴿巢原理的推廣,21,設(shè),k,1,k,2,k,n+1,已知條件中,a,l,是不同的實(shí)數(shù)，則有如下結(jié)論,如若不然，設(shè),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,：能否在一個(gè),n,n,的棋盤的每個(gè)方格填上,1,2,或,3,，使得棋盤上各行各列以及對(duì)角線上的數(shù)字之和都不相等。,解：,棋盤上各行各列以及對(duì)角線上的數(shù)字之和共有,2n+2,個(gè)數(shù)。,從,1,2,或,3,中取,n,個(gè)數(shù)，,答案是否定的,。,從,1,2,或,3,中取,n,個(gè)數(shù)，最大和值是,3n,最小和值是,n,共有,2n+1,個(gè)數(shù)值。,3.14,鴿巢原理的推廣,29,例,3.14.12,試證,6,個(gè)人在一起，其中至少存在,3,個(gè)人或互相認(rèn)識(shí)，或互相不認(rèn)識(shí)。,v,a,v,b,v,c,v,d,v,e,

12、v,f,不認(rèn)識(shí)的兩個(gè)人對(duì)應(yīng),的頂點(diǎn)聯(lián)線著藍(lán)色。,6,個(gè)人設(shè)為,A,B,C,D,E,F,分別用,6,個(gè)頂點(diǎn),v,a,v,b,v,c,v,d,v,e,v,f,表示，過此,6,個(gè)頂點(diǎn)作完全圖，互相認(rèn)識(shí)的兩個(gè)人，對(duì)應(yīng)頂點(diǎn)的連線著紅色。,3.14,鴿巢原理的推廣,30,問題等價(jià)于證明這,6,個(gè)頂點(diǎn)的完全圖的邊，用紅、藍(lán)二色任意著色，必然至少存在一個(gè)紅色邊三角形，或者存在一個(gè)藍(lán)色邊三角形。,v,a,v,b,v,c,v,d,v,e,v,f,3.14,鴿巢原理的推廣,31,在圖論中經(jīng)常用補(bǔ)圖的概念來表述：,6,個(gè)頂點(diǎn)的圖,G,中要么有一個(gè)三角形，要么圖,G,的補(bǔ)圖中有一個(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,的補(bǔ)圖,3.14,鴿巢原理的推廣,32,Va,點(diǎn)和其他,5,個(gè)頂點(diǎn)相連有,5,條邊，每條邊或著以紅色，或著以藍(lán)色。依據(jù)鴿巢原理，其中至少有,3,條邊同色，不妨假定有,3,條邊著以紅色，,v,a,v,b,v,c,v,d,v,e,v,f,3,條邊的另外,3,個(gè)端點(diǎn)設(shè)為,v,e,v,d,v,b,。,這,3,個(gè)端點(diǎn)間的聯(lián)線或同色或不同色，,若同色。則已存在一個(gè)同色三角形，如果不同色，則至少有一條邊是紅色，,3.14,鴿巢原理的推廣,33,對(duì)于,A,以外的,5,個(gè)人可分為,Friend,和,Strange,兩個(gè)集合。,F

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

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