《組合數(shù)學—第二章鴿巢原理和Ramsey定理(2)》由會員分享，可在線閱讀，更多相關《組合數(shù)學—第二章鴿巢原理和Ramsey定理(2)（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、,*,*,第二章 鴿巢原理和,Ramsey,定理,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,單擊此處編輯母版標題樣式,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,2.2,鴿巢原理的加強形式,定理,2.2.1 (,鴿巢原理的加強形式,),2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,推論,2.2.1,若,n(,r,1)+1,個物品,放入,n,個盒子,。,則,至少有一個,盒子里含有,r,個或者更多的物品。,推論,2.2.2,若,設有,n,個正整數(shù),m,1,m,2,m,n,滿足下面的不等式,(m,1,+m,n,)/n,r,1,則,m,1,m,n,
2、中至少有一個數(shù),r,推論,2.2.3,設,m,和,n,都是正整數(shù)且,m,n,，若將,m,個物體放入,n,個盒子中，則至少有一個盒子中有大于等于,個物體,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,推論,2.2.2,若,設有,n,個正整數(shù),m,1,m,2,m,n,滿足下面的不等式,(m,1,+m,n,)/n,r,1,則,m,1,m,n,中至少有一個數(shù),r,另外兩個平均原理：,設有,n,個正整數(shù),m,1,m,2,m,n,滿足下面的不等式,(m,1,+m,n,)/n,r+1,則,m,1,m,n,中至少有一個數(shù),n,，若將,m,個物體放入,n,個盒子中，則至少有一個盒子中有大于等于
3、,個物體,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,例,2.2.3,設有大小兩只圓盤，每個都劃分成大小相等的,200,個小扇形，在大盤上任選,100,個小扇形涂成黑色，其余的,100,個小扇形涂成白色，而將小盤上的,200,個小扇形任意涂成黑色或白色?，F(xiàn)將大小兩只圓盤的中心重合，轉(zhuǎn)動小盤使小盤上的每個小扇形含在大盤上小扇形之內(nèi)。證明：有一個位置使小盤上至少有,100,個小扇形同大盤上相應的小扇形同色。,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,證明,如圖,2.2.1,所示，使大小兩盤中心
4、重合，固定大盤，轉(zhuǎn)動小盤，則有,200,個不同位置使小盤上的每個小扇形含在大盤上的小扇形中，由于大盤上的,200,個小扇形中有,100,個涂成黑色，,100,個涂成白色，所以小盤上的每個小扇形無論涂成黑色或白色，在,200,個可能的重合位置上恰好有,100,次與大盤上的小扇形同色，因而小盤上的,200,個小扇形在,200,個重合位置上共同色,100200=20000,次，平均每個位置同色,2000020=100,次。由推論,2.2.3,知，存在著某個位置，使同色的小扇形數(shù)大于等于,100,個。,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,例,2.2.4,用鴿巢原理的加強形式
5、證明,證明：任意,n,2,+1,個實數(shù),組成的序列中，必有一個長度為,n,+1,的遞增子序列，或必有一個長度為,n,+1,的遞減子序列。,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,證明：,假設長為,n,2,+1,的實數(shù)序列中沒有長度為,n,+1,的遞增子序列，下面證明其必有一長度為,n,+1,的遞減子序列。,令,m,k,表示從,a,k,開始的最長遞增子序列的長度，因為實數(shù)序列中沒有長度為,n,+1,的遞增子序列，所以有：,根據(jù)推論,2.2.3,，這相當于把,n,2,+1,個物體,放入,n,個盒子,1,，,2,，,，,n,中，必有一個盒子,i,里,面至少有 個物體，即存在,
6、n,+1,個,m,k,取值相同，有,使得,（,2.2.1,）,對應于這些下標的實數(shù)序列必滿足,（,2.2.2,）,它們構(gòu)成一長為,n,+1,的遞減序列。,否則，若有某個,j,（）使得 ，那么由從 開始的最長遞增子序列加上 ，就得到一個從 開始的長度為 的遞增子序列。由 的定義知,這與（,2.2.1,）式矛盾。因此（,2.2.2,）式成立。同理可證若沒有長度為,n+1,的遞減子序列，則必有一長度為,n+1,的遞增子序列。因此，結(jié)論成立。,2.3,Ramsey,定理,任何一個,6,人聚會，必有,3,個人相互認識或者相互不認識,其,思想,可以概括為“在任何一個足夠大的結(jié)構(gòu)中必定包含一個給定大小的規(guī)則
7、子結(jié)構(gòu)”。,例,2.3.1,設,K,6,是,6,個頂點的完全圖，用紅、藍兩色涂色,K,6,的邊，則存在一個紅色三角形，或存在一個藍色三角形。,證明：,設,K,6,的頂點為,v,1,v,2,v,3,v,4,v,5,v,6,.,對于任意一種涂色方案，根據(jù)鴿巢原理加強形式的推論,3,，與,v,1,關聯(lián)的,5,條邊至少有,條同色邊,不妨設這三條邊為,v,1,v,2,v,1,v,3,v,1,v,4,（,1,）,若這三條邊均為紅色,v,1,v,2,v,3,v,4,(a),當,v,2,v,3,v,4,之間有一條紅邊，如,v,2,v,3,(b),v,2,v,3,v,4,之間沒有紅邊，,v,1,v,2,v,3,
8、v,4,v,1,v,2,v,3,v,4,(a),(b),（,2,）,若這三條邊均為藍色，同理可證,.,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,例,2.3.2,用紅、藍兩色涂色,K,9,的邊，證明或者存在一個藍色的三角形或紅色的完全四邊形。,Ramsey,定理簡單形式,定理,2.3.1,設,p,，,q,是正整數(shù)，,p,，,q,2,，則存在最小的正整數(shù),R,(,p,q,),，使得當,n,R,(,p,q,),時，用紅、藍兩色涂色,K,n,的邊，或者存在一個藍色的完全,p,邊形,K,p,，或者存在一個紅色的完全,q,邊形,K,q,。,稱,R(p,q),為,Ramsey,數(shù)；,確
9、定精確的,Ramsey,數(shù)的值是相當困難的工作。到目前為止，僅有極少數(shù)小,p,，,q,的,Ramsey,數(shù)被找到。,2024年11月28日,第二章 鴿巢原理和,Ramsey,定理,q,p,3,4,5,6,7,8,9,10,3,6,9,14,18,23,28,36,40,43,4,18,25,35,41,49,61,56,84,69,115,92,149,5,43,49,58,87,80,143,101,216,121,316,141,442,6,102 165,111 298,127,495,169,780,178,1171,7,205 540,216 1031,232 1713,2826,8
10、,282 1870,317 3583,6090,9,565 6588,580,12677,10,798,23556,證明思路：歸納法,歸納假設,R,(,p,2),p,R,(2,q,),q,歸納步驟,R,(,p,-1,q,),，,R,(,q,-1,p,),存在,R,(,p,q,),R,(,p,-1,q,)+,R,(,q,-1,p,),假設對正整數(shù),p,q,p,p,q,q,p,+,q,5,。因此,R,(3,3)=6,。,定理,2.3.2,設,p,q,是正整數(shù)，,p,，,q,2,，則,R,(,p,q,)=,R,(,q,p,),證明：,令,n,R,(,p,q,),。對于藍、紅兩色涂色,K,n,的邊的任
11、何一種方案，將藍邊換紅邊，紅邊換藍邊，則或存在一個藍色的完全,p,邊形，或存在一個紅色的完全,q,邊形。而原來的涂色方案中必存在一個紅色的完全,p,邊形或一個藍色的完全,q,邊形，即,R,(,q,p,),R,(,p,q,),。同理可證,R,(,p,q,),R,(,q,p,),。因此，,R,(,p,q,)=,R,(,q,p,),R,(,p,q,),的圖表示,R,(,p,q,),的集合表述,K,n,的頂點集,V,集合,S,K,n,的邊集,E S,的,2,元子集的集合,T,用,2,色涂色,K,n,的邊 將,T,劃分成,E,1,E,2,存在藍色完全,p,邊形 存在,S,的,p,子集其所有,2,元子集,
12、E,1,存在紅色完全,q,邊形 存在,S,的,q,子集其所有,2,元子集,E,2,集合表述具有更強的表達能力,.,定理推廣（,1,）,將,2,元子集推廣到,r,元子集,對于任意給定的正整數(shù),p,q,r,(,p,q,r,),存在一個最小的正整數(shù),R,(,p,q,;,r,),使得當集合,S,的元素數(shù)大于等于,R,(,p,q,;,r,),時，將,S,的,r,子集族任意劃分成,E,1,E,2,，則或者,S,有,p,子集,A,，,A,的所有,r,元子集屬于,E,1,或者存在,q,子集,B,，,B,的所有,r,元子集屬于,E,2,.,定理推廣（,2,）,將,T,劃分成,E,1,E,2,E,k,設,r,k,
13、1,q,i,r,i,=1,2,k,是給定正整數(shù)，則存在一個最小的正整數(shù),R,(,q,1,q,2,q,k,;,r,),，使得當,n,R,(,q,1,q,2,q,k,;,r,),時,當,n,元集,S,的所有,r,元子集劃分成,k,個子集族,T,1,T,2,T,k,，那么存在,S,的,q,1,元子集,A,1,其所有的,r,元子集屬于,T,1,或者存在,S,的,q,2,元子集,A,2,，,A,2,的所有,r,元子集屬于,T,2,或者存在,S,的,q,k,元子集,A,k,其所有的,r,元子集屬于,T,k,.,Ramsey,定理斷定,Ramsey,數(shù)的存在性,.,Ramsey,數(shù)的確定是一個很困難的問題,.,r,=1,是鴿巢原理，,R,(,q,1,q,2,q,k,;1)=,q,1,+,q,2,+,q,k,k,+1,r,=2,k,=2,是簡單的,Ramsey,定理,.,結(jié)果：,9,個,Ramsey,數(shù)的精確值，部分上界、下界,作業(yè),
組合數(shù)學—第二章鴿巢原理和Ramsey定理(2)
