組合數(shù)學

1、2024/3/20,1,組合數(shù)學,帥天平,北京郵電大學數(shù)學系,Email: tpshuai@bupt.edu.cn,,2024/3/20,2,第1章鴿巢原理,1.1 鴿巢原理：簡單形式1.2 鴿巢原理：加強形式1.3 Ramsay數(shù)1.4 Ramey數(shù)的推廣,鴿巢原理，又叫抽屜原理，是一個重要而又初等的組合學原理，由Peter Gustav Lejeune Dirichlet 在1834年首次形式化給出，它能夠解決各種有趣

2、的問題，常常得出一些令人驚奇的結(jié)論，特別的它在計算機科學中經(jīng)常出現(xiàn).,2024/3/20,3,1 鴿巢原理：簡單形式,證明: 設這n+1個數(shù)是 a1,a2,…,an+1,定理 1.1.1 如果把n+1只鴿子放入n個鴿巢，那么至少有一個鴿巢中有兩只或更多的鴿子.,【例1】 在13個人中至少有兩個人在同一個月過生日.,【例2】 從1到2n的正整數(shù)中任取n+1個，則這n+1個數(shù)中至少有一對數(shù)，其中一個是另一個的倍數(shù).,202

3、4/3/20,4,1 鴿巢原理：簡單形式,對此序列中的每一個數(shù)去掉一切2的因子，直至剩下一個奇數(shù)為止. 例如，68＝2×2×17，則去掉2×2，只留下17. 那么我們會得到一個由奇數(shù)組成的序列 b1,b2,…,bn+1.1到2n之間只有n個奇數(shù)，故序列{ b1,b2,…,bn+1}中至少有兩個是相同的. 設bi = bj = b，則aj = 2pbi，aj = 2qbj,由于ai≠aj，顯然

4、，其中一個是另一個的倍數(shù).,可以看出，應用鴿巢原理可以巧妙的解決看似復雜的問題，其關鍵是如何去構(gòu)造問題中的“鴿子”和“鴿巢”.,2024/3/20,5,1 鴿巢原理：簡單形式,【例3】 ：1)、在邊長為2的正方形中任取5 點，證明：存在2 點其間距離不超過21/22)、在邊長為1 的正三角形中任取10 點，證明：存在2 點其間距離不超過1/3,,2024/3/20,6,【例4】 設 a1 , a2 , ··

5、83; , am是正整數(shù)序列，則至少存在一個k和 l , 1≤k≤ l ≤m，使得和 ak + ··· + al 是m的倍數(shù)。,h = 1 , 2 , ··· , m . 若存在 l , Sl≡0 (mod m)，則命題成立．否則，1≤rh≤m-1．對所有h = 1 , 2 ,··· , m．由鴿巢原理，故存在 rk-1 = rl ,

6、 即Sk-1≡ Sl，不妨設 l ＞k-1．則 Sl－Sk-1 = ak + ak+1 +… + al ≡0 (mod m),1 鴿巢原理：簡單形式,2024/3/20,7,【例5】 設a1 , a2 , ··· , a100是由1和2組成的序列 , 已知從其任一數(shù)開始的順序10個數(shù)的和不超過16．即 ai + ai+1 +… + ai+9 ≤16，1≤ i ≤91則至

7、少存在一對h和k ，k > h，使得　　 ah+1 +… + ak = 39,1 鴿巢原理：簡單形式,2024/3/20,8,根據(jù)假定有　S100≤10×16 = 160作序列S1 , S2 , … , S100 , S1 +39, … , S100+39 .共200項．其中最大項 S100+39≤160+39由鴿巢原理，必有兩項相等．而且必是前段中某項與后段中某項相等．設　 Sk

8、= Sh + 39，k>h　Sk－Sh =39 　即 ah+1 +… + ak = 39,1 鴿巢原理：簡單形式,2024/3/20,9,1 鴿巢原理：簡單形式,【例6】 ：一位象棋大師以11 周時間準備一次比賽，他決定每天至少下一盤棋，為了不至于太累，他限定每一周不多于12 盤對局，證明，存在連續(xù)若干天，在這些天中他恰下了21 盤棋。解 ：令ai是第1天到第i天下的總盤數(shù)(i=1,2,…,77;11周共77天),,類似

9、的其他題目,2024/3/20,10,1 鴿巢原理：簡單形式,這154個數(shù)均在1-153之間，故必有兩個數(shù)相等，且容易知道這兩個數(shù)是一個在前段，一個在后段，即一個為ai，一個為aj+21，ai=aj+21立知ai-aj=21，j<i,即第j+1天至第i天之間總共下了21盤,2024/3/20,11,1 鴿巢原理：簡單形式,【例7】 ：證明任意給定的52 個整數(shù)中，總存在兩個數(shù)，它們的和或差能被100 整除。,解：設此52個整

10、數(shù)為a1,a2,…,a52.被除的余數(shù)分別為r1,r2,…,r52?{0,1,…,99}.構(gòu)造鴿子巢為{0},{1,99},{2,98},{3,97},…,{49,51},{50}共51個，這52個余數(shù)必有2個落入同一個巢，比如說是ri，rj,若它倆相等則ai-aj被100整除，否則ri+rj=100，此時ai+aj被100整除。,2024/3/20,12,2 鴿巢原理：加強形式,定理 1. 2.1 設a1,a2,…,an都是正整數(shù)

11、. 如果把a1+a2+…+an-n+1只鴿子住入n個鴿巢，那么或者第一個鴿巢至少住入a1只鴿子，或者第二個鴿巢至少住入a2只鴿子,…,或者第n個鴿巢至少住入an只鴿子。證明 設將a1+a2+…+an-n+1個只鴿子住入n個鴿巢中. 如果對于每個i =1,2,…,n，第i個鴿巢都不能住入ai或更多的只鴿子，那么所有鴿巢中的鴿子的總數(shù)不超過 (a1-1) + (a2-1) + … + (an-1) = a1+a2+

12、…+an-n比原鴿子數(shù)少1. 因此，必存在某個i ，使得第i個鴿巢至少含有ai只鴿子.,2024/3/20,13,2 鴿巢原理：加強形式,推論 1.2.1 若把n(r-1)+1只鴿子住入n個鴿巢，那么至少有一個鴿巢中有r只鴿子住入.,也可以寫成如下形式：,在定理1.2.1中，如果令ai = 2(i =1,2,…,n)，就是定理1.1.1；如果ai = r(i =1,2,…,n)，則變成了：,推論 1.2.2 若將m只鴿子放入n個

13、鴿巢中，則至少有一個鴿巢中有不少于 只鴿子 .,2024/3/20,14,2 鴿巢原理：加強形式,推論 1.2.3 設a1,a2,…,an是n個整數(shù)，而且 則a1,a2,…,an中至少有一個數(shù)不小于r. 或者,2024/3/20,15,【例8】 若序列S ={ a1 , a2 , … , amn+1}中的各數(shù)是不等的，m , n 是正整數(shù)，則 S有一長度為m+1的嚴格增子序列或長度

14、為n+1的減子序列，而且 S有一長度為m+1的減子序列或長度為n+1的增子序列．,證１　由S中的每個 ai 向后選取最長增子序列，設其長度為li ，從而得序列　L = { l1 , l2 , … , lmn+1 }．若存在 lk≥m+1，則結(jié)論成立．,2 鴿巢原理：加強形式,2024/3/20,16,不妨設 i1 ai2 > ··· > ain+1 ，,li1 = li2 =

15、··· = lin= lin+1,2 鴿巢原理：加強形式,即有一長度為n+1的減子列．,矛盾．,否則，若,2024/3/20,17,證２　從ai 向后取最長增子列及減子列，設其長度分別為 li ，l'i .若對任意 i ，都有l(wèi)i ∈[1，m], l?i∈[1，n],不超過mn種對．則存在 j lk， 若aj >ak，則 l?j >l?k ，矛盾．,2

16、 鴿巢原理：加強形式,2024/3/20,18,【例9】 將[ 1 , 67 ]劃分為４個子集，必有一個子集中有一數(shù)是同子集中的某兩數(shù)之差．,證:　用反證法．設命題不真．即存在劃分P1∪ P2∪ P3∪P4＝[ 1，67 ]，Pi中不存在一個數(shù)是Pi中兩數(shù)之差，i=1,2,3,4.因 ?(67-1)/4?+1 = 17，故有一子集，其中至少有17個數(shù)，設這17個數(shù)從小到大為a1 , … , a17 ．不妨設 A={a1 ,

17、… , a17 }?P1。令bi= ai +1 －a1，i = 1，···，16。,2 鴿巢原理：加強形式,2024/3/20,19,設　B＝｛b1 , ··· , b16}，B? [ 1 , 67 ]。由反證法假設，B∩P1 = ф。因而 B? ( P2∪ P3∪ P4 ) 因為?(16-1)/3?+1=6，不妨設{b1 , ·

18、;·· , b6} ? P2 ， 令ci=bi＋1－b1，i = 1, ···,5設C＝{c1 , ··· , c5 }，C ? [ 1 , 67 ]由反證法假設，C∩( P1∪P2 ) =ф，故有 C ?(P3∪P4 )因為?(5-1)/2?+1=3，不妨設{c1 , c2 , c3 } ? P3,2 鴿巢原理：加強形式

19、,2024/3/20,20,令　di= ci +1 －c1，i = 1 , 2設　D＝{ d1 , d2 } , D?[ 1 , 67]。由反證法假設， D∩( P1∪P2∪P3 )=ф，因而 　D ? P4　由反證法假設， d2－d1? P1∪P2∪P3 且d2－d1 ? P4 ，故 d2－d1 ? [ 1 , 67 ]，但顯然 d2－d1

20、? [ 1 , 67 ]，矛盾。,2 鴿巢原理：加強形式,2024/3/20,21,21,【例10】 A={1,2,…,99},X是A的子集，?X?=10，試證：可以找到X的兩個非空真子集Y和Z，Y∩Z=?，使得Y的元素之和和Z的元素之和相等。,解：先求X的非空真子集的數(shù)目：,另一方面，X的非空真子集A，其元素之和有：,C(10,1)+C(10,2)+…+C(10,9)=210-2=1022,2 鴿巢原理：加強形式,2024/3/2

21、0,22,22,非空真子集的數(shù)量有1022個，而非空真子集的元素之和小于或等于855，因此至少有兩個非空真子集的元素之和相等，設這兩個子集分別為A和B，使得：,如果,則結(jié)果成立。否則：,令：,Y和Z就是滿足條件的兩個集合。,2 鴿巢原理：加強形式,2024/3/20,23,23,【例11】將上下兩個同心而且同樣大小的圓盤A，B分別劃分成200個全等的扇形，在A盤上任取100個扇形涂上紅色，其余100個扇形涂上藍色，而B盤上的200個扇

22、形任意地涂上紅色或藍色。證明，總可適當?shù)剞D(zhuǎn)動兩圓盤到某個位置，當上下的扇形互相重合時，兩圓盤上至少有100對具有相同顏色的扇形重迭在一起。,（證）定義兩圓盤的扇形對齊時為一種重迭格局，由于每個圓盤都分為200個扇形，故當其中一個圓盤轉(zhuǎn)動時，可能出現(xiàn)的重迭格局有200個。對這200個格局計算同色扇形重迭的對數(shù)。,2 鴿巢原理：加強形式,2024/3/20,24,24,由于A盤上紅、藍扇形各100個，因此，B盤上每個扇形（或紅色或藍色）在

23、這200個格局里與A盤上的同色扇形各重迭100次。對B盤的每個扇形統(tǒng)計，在這200個格局中B盤的200個扇形與A盤同色扇形重迭在一起共 對。因此可計算出每一格局中同色扇形重迭的平均對數(shù)為 。因此至少有一格局中同色扇形重迭的至少有100對。,***,2 鴿巢原理：加強形式,2024/3/20,25,25,【例12】 ：設A= a1a2···a20是10個0和10個1組成的20位２進制數(shù)。B=b1b2

24、3;··b20是任意的20位2進制數(shù)。C=b1b2···b20b1b2···b20= C1C2···C40,則存在某個i,1≤i≤21,使得CiCi+1···Ci+19與a1a2···a20至少有10位對應數(shù)字相同。,…...,…...,...,...,...,...,

25、A,C,,,第 i 格,第 i +19格,1 2 ········· 19 20 1 2 ······· 19 20,1 2 ···&

26、#183;····　　　 19 20 1 ······ 19 20,B,2 鴿巢原理：加強形式,2024/3/20,26,26,…...,A,1 2 ········· 1

27、9 20,4、因此必有一次相同數(shù)字的格數(shù)不少于10位,1、假想著A如圖所示從左向右一格一格移動。,2、在移動到最后時。每一個bj都遍歷了a1,a2,…,a20。因A中有10個0和10個1，每一個bj都有10位次對應相等。,3、在20次的移動過程中共有10×20=200位次對應相等。,2 鴿巢原理：加強形式,2024/3/20,27,27,【例13】 ：隨意地給正十邊形的10個頂點編上號碼1,2,3,4,5,6,7,8,9,1

28、0,求證：必有一個頂點及與之相鄰的兩頂點之和不小于17。,證明：以A1,A2,A3,…,A10表示正十邊形的10個頂點，,以qi表示頂點Ai與Ai相鄰的兩頂點號碼之和,求?qi,=(1+2+…+10)?3=165,因此必存在qi?17,2 鴿巢原理：加強形式,2024/3/20,28,28,【例14】 ：下圖中畫出了3行9列共27個小方格，將每一個方格涂上紅色或者藍色，證明：無論如何涂色，其中必有至少兩列它們的涂色方式完全相同。,解：

29、每個方格的涂色方案有紅和藍2種，每列有3個格子，因此每列有：,2×2×2=8種涂色方案。,現(xiàn)在有9列，根據(jù)鴿巢原理，必有至少兩列它們的涂色方式完全相同。,2 鴿巢原理：加強形式,2024/3/20,29,29,【例15】 ：設n是大于1的奇數(shù)，則下列數(shù)的集合：{2-1,22-1,23-1,...,2n-1-1,2n-1}中至少存在一數(shù)被n除盡。,證：,{2-1,22-1,23-1,...,2n-1-1,2n-1

30、}整除n可得n個余數(shù)，,除以n的余數(shù)共有0,1,2,…,n-1個。,如果{2-1,22-1,23-1,...,2n-1-1,2n-1}除以n所得余數(shù)互不相等,則結(jié)論成立。,否則：,2 鴿巢原理：加強形式,2024/3/20,30,30,設a,b?n,a?b, 2a-1(modn)=2b-1(modn)=r,2a-1=hn+r,2b-1=mn+r,設a>b,,2a-2b=(h-m)n,2b(2a-b-1)=(h-m)n,2a-b-

31、1即為所求：,2 鴿巢原理：加強形式,2024/3/20,31,31,【例16】 ：能否在一個n?n的棋盤的每個方格填上1,2或3，使得棋盤上各行各列以及對角線上的數(shù)字之和都不相等。,解：棋盤上各行各列以及對角線上的數(shù)字之和共有2n+2個數(shù)。,從1,2或3中取n個數(shù)，,答案是否定的。,從1,2或3中取n個數(shù)，最大和值是3n,最小和值是n,共有2n+1個數(shù)值。,2 鴿巢原理：加強形式,2024/3/20,32,【例17】 一個抽屜里由

32、20件襯衫，其中4件藍色，7件灰色，9件紅色.從中隨意取出至少多少件，才能保證有4件是同色的？保證5，6，7，8，9件同色呢？,解:　1、3×3＋1＝10保證4件同色。 2、4＋4×2＋1＝13保證5件同色。 3、4＋5×2＋1＝15保證6件同色。 4、4＋6×2＋1＝17保證7件同色。 5、4＋7＋7＋1＝19保

33、證8件同色。 6、4＋7＋8＋1＝20保證9件同色。,2 鴿巢原理：加強形式,2024/3/20,33,2 鴿巢原理：加強形式,定理1.2.3 假設類型i的物品有xi件，i=1,2,…,n,且,從中任意取出至少ar件才能保證至少有r件同類型的物品，則,2024/3/20,34,34,【引例】（Ramsey問題） 試證6個人在一起，其中至少存在3個人或互相認識，或互相不認識。,,va,,vb,vc,vd,ve,v

34、f,,,,,,,,,,,,,,,,不認識的兩個人對應的頂點聯(lián)線著藍色。,6個人設為A,B,C,D,E,F,分別用6個頂點va,vb,vc,vd,ve,vf表示，過此6個頂點作完全圖，互相認識的兩個人，對應頂點的連線著紅色。,3 Ramsey問題與Ramsey數(shù),2024/3/20,35,35,問題等價于證明這6個頂點的完全圖的邊，用紅、藍二色任意著色，必然至少存在一個紅色邊三角形，或者存在一個藍色邊三角形。,,va,,vb,vc,v

35、d,ve,vf,,,,,,,,,,,,,,,,3 Ramsey問題與Ramsey數(shù),2024/3/20,36,36,Va點和其他5個頂點相連有5條邊，每條邊或著以紅色，或著以藍色。依據(jù)鴿巢原理，其中至少有3條邊同色，不妨假定有3條邊著以紅色，,3條邊的另外3個端點設為ve,vd,vb。,這3個端點間的聯(lián)線或同色或不同色，,若同色。則已存在一個同色三角形，如果不同色，則至少有一條邊是紅色，從而有同色三角形,3 Ramsey問題與Ram

36、sey數(shù),2024/3/20,37,類似可得命題2： 對6個頂點的完全圖任意進行紅、藍兩邊著色,都至少存在兩個同色的三角形.命題3： 對10個頂點的完全圖K10任意進行紅、藍兩邊著色,都或者存在一個紅色K4，或者存在一個藍色K3命題4： 對9個頂點的完全圖K9任意進行紅、藍兩邊著色,都或者存在一個紅色K4,或者存在一個藍色K3.,命題 5： K18的邊紅,藍２著色,存在紅K4或藍K4 ．,由上述推導得如下命題 命題1： 對6個

37、頂點的完全圖任意進行紅、藍兩邊著色，都存在一個紅色的三角形或藍色的三角形.,3 Ramsey問題與Ramsey數(shù),2024/3/20,38,3 Ramsey問題與Ramsey數(shù),定義 1.3.1 對于任意給定的兩個正整數(shù)a和b，如果存在最小的正整數(shù)r(a,b)使得當N≥r(a,b)時，對KN任意進行紅、藍兩邊著色，KN中均有紅色Ka，或藍色Kb，則r(a,b)稱為Ramsey數(shù).,對上面的幾個命題進行歸納，可以得出如下定義：,定理

38、 1.3.1 對任意正整數(shù)a，b，有（1）r(a,b) =r(b,a) （2）r(a,2)=a,2024/3/20,39,3 Ramsey問題與Ramsey數(shù),證明 令N＝r(a-1,b) + r(a,b-1),對KN進行任意紅、藍兩邊著色. 設x是KN的一個頂點,在KN中與x相關聯(lián)的邊共有r(a-1,b) + r(a,b-1)條,這些邊要么為紅色,要么為藍色. 由鴿巢原理知,與x相關聯(lián)的這些邊中,要么至少有

39、r(a-1,b)條紅色的邊,要么有至少r(a,b-1)條藍色的邊.,定理 1.3.2 對任意正整數(shù)a≥3，b≥3，有 r(a,b)≤r(a-1,b) + r(a,b-1).,2024/3/20,40,3 Ramsey問題與Ramsey數(shù),（1）這些邊中有r(a-1,b)條紅邊. 在以這些紅邊相關聯(lián)的r(a-1,b)個頂點構(gòu)成的完全圖Kr(a-1,b)中,必有一紅色Ka-1或藍色Kb. 若有紅色Ka

40、-1，則它加上頂點x以及x與Ka-1之間的紅邊，即構(gòu)成一個紅色Ka；否則，就有一個藍色Kb. （2）這些邊中有r(a,b-1)條藍邊. 在以這些藍邊與x相關聯(lián)的r(a,b-1)個頂點構(gòu)成的完全圖Kr(a,b-1)中，必有一個紅色Ka或一個藍色Kb-1，若有藍色Kb-1，則它加上頂點x以及x與Kb-1之間的藍邊，即構(gòu)成一個藍色Kb；否則，就有一個紅色Ka. 綜合（1）、（2），知r(a,b)≤N.,2024/3/20,41,3 R

41、amsey問題與Ramsey數(shù),證明 對a+b作歸納. 當a+b≤5時,a=2或b=2,由定理2.3.1知定理1.3.3成立. 假設對一切滿足5≤a+b<m+n的a,b，定理成立，由定理1.3.2及歸納假設，有,定理 1.3.3 對任意正整數(shù)a≥2，b≥2，有,r(a,b)≤,所以，對任意的正整數(shù)a≥2，b≥2，定理的結(jié)論成立,r(m,n)≤r(m,n-1)+r(m-1,n)≤,2024/3/20,42,3 Ramse

42、y問題與Ramsey數(shù),2024/3/20,43,3 Ramsey問題與Ramsey數(shù),2024/3/20,44,3 Ramsey問題與Ramsey數(shù),則必有Kn的一個２著色方案中無同色Km，由r(m ,m)定義可知，r(m , m)>n,下面的表格給出目前已知的Ramsey數(shù)部分結(jié)果, 完全的結(jié)果可以見: http://mathworld.wolfram/RamseyNumber.html,2024/3/20,45,3

43、 Ramsey問題與Ramsey數(shù),2024/3/20,46,若將２著色改為k 著色，同色Ka或同色Kb改為同色 Ka i i = 1,2,…,k.即得Ramsey數(shù) r(a1,a2,…,ak). 對于給定的正整數(shù) ai ( ai≥2),i = 1 , 2 , … , k．存在最小正整數(shù)r, 當對Kr用k種顏色Ci ( i = 1 , 2 , … , k)任意邊著色．則存在 i ，出現(xiàn)全Ci色的Ka i (即邊都是Ci色的

44、ai個頂點的完全圖)；這個最小正整數(shù) r 用 r (a1 , … , ak)表示．,4 Ramsey 數(shù)的推廣,2024/3/20,47,r (a1 , a2 , … , ak)≤ r ( a1 , r ( a2 , … , ak) ),證　設r ( a1 , r ( a2 , … , ak) ) = p， r (a2 , … , ak) = q；對Kp的邊２著色，出現(xiàn)第一色Ka1或第二色Kq，用k－1種

45、色對Kq的邊著色，至少出現(xiàn)i色的ai點完全圖，i = 2 , … , k．對Kp的邊k 著色，將后k－1種色看作同一種色，出現(xiàn)第一色Ka 1或另一色(k－1種色看作另一色）的Kq．即出現(xiàn)第i 色Ka i ，i = 2 , … , k. 故 r (a1 , a2 , … , ak)≤ p,4 Ramsey 數(shù)的推廣,定理1.4.1 對于任意的正整數(shù)a1 , a2… , ak，有,2024/3/20,48,例　r ( 3 , 3

46、 , 3) = 17,證　設三色為 r ,b ,g．則對K17的任一頂點v 有　dr(v) + db(v) + dg(v) = 16；因?16/3?=6 ,故任一頂點與其他頂點的連線中，至少有６條同色．不妨設dr(v1)≥6, (v1v2)…(v1v7)都是紅邊．從而可得如下判斷樹．,4 Ramsey 數(shù)的推廣,2024/3/20,49,4 Ramsey 數(shù)的推廣,2024/3/20,50,4 Ramsey 數(shù)的推廣,r

47、(a1 , a2 , … , ak)≤ r ( a1 -1,a2 , … , ak) + r ( a1,a2 -1, … , ak)+…+ r ( a1,a2 , … , ak-1),定理1.4.2 對于任意的正整數(shù)a1 ?2, a2 ?2 … , ak ?2 ，有,定理1.4.3 對于任意的正整數(shù)a1 , a2… , ak，有,2024/3/20,51,4 推廣,廣義Ramsey 數(shù)的一個應用----許爾(Schur)

48、定理的證明。Schur定理：對任意的正整數(shù)n,都存在一個整數(shù)fn使得無論將集合{1,2,…,fn}劃分成哪n個子集合，總有一個子集中有三個數(shù)x,y,z（不一定不同），使?jié)M足 x+y=z。集合劃分 (有限劃分) ：給定集合A，A的一組子集族{A1,A2,…Am}稱為A的一個劃分(諸Ai均為A的子集），若Ai?Aj=?，對任意的i?j，且?i=1mAi=A.,2024/3/20,52,4 Ramsey 數(shù)的推廣,Schur定理

49、的廣義Ramsey 數(shù)證明。Schur定理：設{A1,A2,…An}是集合{1,2,…,fn}的任意一個劃分，則總有一個子集Ai中有三個數(shù)x,y,z（不一定不同），使?jié)M足 x+y=z。這里記滿足上述條件的正式fn的最小值為sn，則有s1=2,s2=5,s3=14,2024/3/20,53,4 Ramsey 數(shù)的推廣,定理1.4.5(Ramsey定理) 設q1 , q2 , … , qn是正整數(shù)，且q1 ?t, q2 ?

50、t … , an ?t ，則必有最小的正整數(shù)N(q1 , q2 , … , qn；t)，使得當m? N(q1 , q2 , … , qn；t)時，對任意有m個元素的集合S (|S|=m),將S的全體t元子集任意分放到n個盒子里，那么，要么有S中的q1元素，它的所有t元子集全在第一個盒子里，要么有S中的q2元素，它的所有t元子集全在第二個盒子里，要么有S中的q3元素，它的所有t元子集全在第3個盒子里,….,要么有S中的qn元素，它的所