组合数学基础9.doc

组合数学基础9.doc第九讲Ramsey定理§1(鸽笼原理)(本页)§2(Ramsey定理)§3(定理的应用)§1鸽笼原理下面我们将介绍一个重要而又基本的组合原理-. 如果把件东西放入"十1个盒子,,+,,,…,= (1<s<m)证设2】 .如果存在某一$•使尖能被m整除,则命题成立,若不然用m除圣记十&(m>/>0).由于不同余数至多有m—,必存在正整数为和M吏rk=n(l<k<l<m)^从而I f3^—3k=失=(么一院m尸皿、i+l ・即、i+,但为了使自己不太疲倦,,:设这位大师前$•天的练****赛次数为失(1<'V77),则序列如,…,<11X21=132故m+21<,㈤十21(1W77),由于“I,"',。”之中任何两个数都不相同,。】+21,鬼十21,...,。"十21之中任何两个数都不相同,故必存在湖)使失=即=21,因此从第1十1天起到第$•天为止,这些天中,,2,…,,。a=lfmod2).对1,2,…,,3,5,7,-199之一.-共有100个,于是所选取的101个整数中,必有两个数在上述表示式中含有相同的确不妨设这两个数是&和况且这样况能被&:-+1(**)设S%・''顷是正整数,把si件物品放入£个盒子里,则存在某•一$(1W£)使第$•个盒子里至多装%,对所有的§(1V£V£)均有第$•个盒子至多装有%-£个盒子装有的物件总数至多为2(%一1)=T<52%T+1§=1 4=1 4==q2=-=qt=r时,上述原理可叙述为:(***)如果把1)十1件物品装入t个盒子中,则至少有一•[提法为:(****)如果t个整数mi,m2,…,mt的算术平均数(二=】“')"大于,一1,则"(1W£),则因此= +1的实数序列“1,处,…,%+1的递增子序列或长为九++⑶为首元素的最长递增子序列,则"(***),取r=n+1知混+1个数啷(1*心弁2+1)半l<mk<n时,=m^=…(1V知<靛<…<+1V饬2十1)此时必有%次"1J‘,存在某.—使%J闻f胞j开始的最长子序列,然后把%放在这个子序列的前面,就得到一个以啊''(槌心)从而是一个长为》十1的递减子序列.§2Ramsey定理鸽笼原理的进一步,更深刻、,巳(,)㈤=<XGS||X|E令R(S)=血U也U…U血,也0为=0(£产/) ⑴是R⑴的一个任意的t有序划分&,&…,血是t个分量知亥,一顷是满足条件1<^<<4>(1<«<t) (2),&中,则称这个%子集为8的(安'”)集,Ramsey定理可以叙述如下:定理1设给定条件⑵的一组整数%和儿则存在正整数N,使得当n>对册集S(1«M)的所有厂子集R⑴的任一有序划分(1),必有某个$•存在使S包含•个(豹也)"的最小者为"("皿…皿『I首先,我们用归纳法,对上述定理当t=,] 地治顷,1)=勿+亥_1,%>1(£=1,2). (3)证明(见相关知识心)注1引理1性勿双2,1)