2012軟件組合數(shù)學(xué)第二章鴿巢原理簡單形式

1、第二章 鴿巢原理和Ramsey定理組合存在性定理Ramsey定理（鴿巢原理為其最簡形式）偏序集分解定理（Dilworth定理）相異代表系存在定理（Hall定理）1928年英國數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟學(xué)家Frank， Ramsey(1903-1930) 在倫敦數(shù)學(xué)會上宣讀一篇 “ 論形式邏輯中的一個問題”的論文，奠定了 Ramsey理論的基礎(chǔ)。核心思想是：“任何一個足夠大的結(jié)構(gòu)中必定包含一個給定大小的規(guī)則子結(jié)構(gòu)”2022年8月30日第二章 鴿巢原理和Ramsey定理第二章 鴿巢原理和Ramsey定理2.1 鴿巢原理的簡單形式2.2 鴿巢原理的加強形式2.3 Ramsey定理2022年8月30日第二章

2、 鴿巢原理和Ramsey定理2.1 鴿巢原理的簡單形式鴿巢原理是組合學(xué)中最簡單、最基本原理也叫抽屜原理(又稱為重疊原理或狄利克雷(Dirichlet)原理）。定理2.1.1若把n+1個物體放入n個盒子中，則至少有一個盒子中有2個或更多的物體2022年8月30日第二章 鴿巢原理和Ramsey定理證明 如果每個盒子中至多有一個物體，那么n個盒子中至多有n個物體，而我們共有n+1個物體，矛盾。故定理成立。 鴿巢原理的集合描述形式： 設(shè)有限集合A有n+1個元素，將A分劃成n個不相交子集的并，則至少有一個子集含有兩個或兩個以上的元素。 定理是用群體的整體性表現(xiàn)出個體的某些特性，屬于從宏觀到微觀的理論研究

3、成果注意 應(yīng)用時要分清物品與盒子以及物體數(shù)與盒子總數(shù)。 這個原理只能用來證明某種安排的存在性，而卻不能找到具體滿足要求的安排 不能被推廣到只存在n個(或更少)物體的情形。2022年8月30日第二章 鴿巢原理和Ramsey定理例2.1.1 證明：13個人中必有兩人的屬相相同。 幾個例子例2.1.2 有5雙不同的襪子混在一個抽屜里，我們至少從中選出多少只襪子才能保證找到1雙襪子？ 2022年8月30日第二章 鴿巢原理和Ramsey定理解 應(yīng)用定理2.1.1，共有5個盒子，每個盒子對應(yīng)1雙襪子。如果選擇5+1=6只襪子分別放到它所屬那雙襪子的盒子中，則必有兩只襪子落入同一個盒子中，即為一雙襪子。因此

4、我們至少從中選出6只襪子才能保證找到1雙襪子。 本例實際上是知道n個盒子，而找n+1個物體的問題。 2022年8月30日第二章 鴿巢原理和Ramsey定理例2.1.3對任意給定的52個整數(shù)，證明：其中必存在兩個整數(shù)，要么兩者的和能被100整除，要么兩者的差能被100整除。 2022年8月30日第二章 鴿巢原理和Ramsey定理1、已知：52個整數(shù)，2、目標(biāo)：找被100整除的兩個數(shù)3、解題途徑：把52個物體放到51個盒子中，需要構(gòu)造51個盒子4、根據(jù)題干中要求的兩個整數(shù)必須具備的性質(zhì)構(gòu)造盒子5、是否能夠被100整除的關(guān)鍵在余數(shù)，那么一個整數(shù)除以100的余數(shù)為0，1，2，99 兩個整數(shù)的和可以被1

5、00整除，則二者的余數(shù)的和是100 兩個整數(shù)的差可以被100整除，則二者的余數(shù)相同分析：證明：對于任意一個整數(shù)，它除以100的余數(shù)顯然只能有如下100種情況，0，1，2，3，99而現(xiàn)在有任意給定的52個整數(shù)，我們需要構(gòu)造51個盒子，即對這100個余數(shù)進(jìn)行分組，共51組：0，1，99，2，98，3，97，49，51，50根據(jù)定理2.1.1，這52個整數(shù)，必有兩個整數(shù)除以100的余數(shù)落入上面51組中的同一組中，若是0或50則說明它們的和及差都能被100整除；若是剩下的49組的話，因為一組有兩個余數(shù)，余數(shù)相同則它們的差能被100整除，余數(shù)不同則它們的和能被100整除。2022年8月30日第二章 鴿巢

6、原理和Ramsey定理例2.1.4 一名象棋大師有11周時間準(zhǔn)備一場錦標(biāo)賽，她決定每天至少下一盤棋，為了不能太累一周中下棋的次數(shù)不能多于12盤。證明：她一定在此期間的連續(xù)若干天中恰好下棋21盤。 2022年8月30日第二章 鴿巢原理和Ramsey定理1、題干提供的信息：一共11周2、約束條件： 每周最多下12盤棋 每天至少下1盤棋 3、目標(biāo)：連續(xù)若干天共下棋21盤4、解題途徑：構(gòu)造下棋盤數(shù)的部分和分析：2022年8月30日第二章 鴿巢原理和Ramsey定理證明:令b1，b2，b77分別為這11周中他每天下棋的次數(shù)，并作部分和a1=b1,a2=b1+b2,，a77=b1+b2+b77.2022年

7、8月30日第二章 鴿巢原理和Ramsey定理所以有1a1a2a3a771211=132 (2.1.1)考慮數(shù)列a1,a2,，a77，a1+21,a2+21,，a77+21,它們都在1與132+21=153之間，共有154項，由定理2.1.1知，其中必有兩項相等根據(jù)題意，有bi1(1i77),且bi+bi+1+bi+612(1i71),2022年8月30日第二章 鴿巢原理和Ramsey定理由（2.1.1）式知a1,a2,，a77這77項互不相等，從而a1+21,a2+21,，a77+21這77項也互不相等，所以一定存在1i aj，則ai與從aj開始的最長遞減子序列合并，組成的子序列的長度Li=L

8、j+1 Lj；這與Li = Lj矛盾；反證法。假設(shè)既不存在長度為n+1的遞增子序列，也不存在長度為n+1的遞減子序列即1Lin 且 1Min，其中1in2 + 1，由集合論的知識知道集合(Li, Mi)的元素數(shù)為n2，根據(jù)定理2.1.1，必然有（Li, Mi） = (Lj, Mj)（i j），當(dāng)然Li = Lj，而且Mi = Mj。對于序列中的元素ai, aj，分兩種情況： 2022年8月30日第二章 鴿巢原理和Ramsey定理（2）若ai Mj，這又與Mi = Mj矛盾。所以假設(shè)1Lin 且 1Min不成立。原結(jié)論成立。這個例子的結(jié)論是1935年由數(shù)學(xué)家保羅艾狄胥（Erds）和喬治塞克爾斯（

9、Szekeres）首先給出的，它還有更為有趣的表述：n2+1個人肩并肩地站成一排，則總能選出n+1個人，讓他們向前邁出一步，所形成新一排的身高是遞增或遞減的。2022年8月30日第二章 鴿巢原理和Ramsey定理定理2.1.1 鴿巢原理簡單形式若把n+1個物體放入n個盒子中，則至少有一個盒子中有2個或更多的物體思考？把多少個物體放到 n 個盒子中，能保證至少存在一個盒子中包含 r 個以上物體？2022年8月30日第二章 鴿巢原理和Ramsey定理2022年8月30日第二章 鴿巢原理和Ramsey定理定理2.2.1的推論推論2.2.1若 n(r1) + 1個物品放入n個盒子。則至少有一個盒子里含

10、有r個或者更多的物品。證明 在定理2.2.1中取q1=q2=qn=r即可。2022年8月30日第二章 鴿巢原理和Ramsey定理2.2 鴿巢原理的加強形式定理2.2.1 (鴿巢原理的加強形式)2鴿巢原理的加強形式定理2.2.1 的證明證明:(反證法) 對于i1，2，n，假設(shè)第i個盒子里至多含有qi-1個物品，則n個盒子里物品數(shù)的總和不超過 q1+q2+qn n 個與已知條件(q1+q2+qn n+1)矛盾。2022年8月30日第二章 鴿巢原理和Ramsey定理 與簡單形式的關(guān)系 上節(jié)的鴿巢原理的簡單形式是這一原理的特殊情況，即q1 = q2 = = qn= 2，有 q1 + q2 + +qnn + 1 = n + 12022年8月30日第二章 鴿巢原理和Ramsey定理 推論2.2.2 若設(shè)有n個正整數(shù)m1 , m2 , , mn滿足下面的不等式 (m1 + +mn)/n r1, 則 m1, mn中至少有一個數(shù) r證明 由上面的不等式得 m1 + +mn (r1)n+1， 由推論2.2.1， 存在mi，使得mir。 另外一個平均原理：設(shè)有n個正整數(shù)m1 , m2 , , mn滿足下面的不