《組合數(shù)學(xué)》課件PPT

《組合數(shù)學(xué)》課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 第二章第二章 鴿巢原理和鴿巢原理和Ramsey定理定理組合存在性定理組合存在性定理lRamsey定理（鴿巢原理為其最簡形式）定理（鴿巢原理為其最簡形式）l偏序集分解定理（偏序集分解定理（Dilworth定理）定理）l相異代表系存在定理（相異代表系存在定理（Hall定理）定理）1928年英國數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟(jì)學(xué)家年英國數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟(jì)學(xué)家Frank，Ramsey(1903-1930)在倫敦?cái)?shù)學(xué)會(huì)上宣讀一篇在倫敦?cái)?shù)學(xué)會(huì)上宣讀一篇 “論形式邏輯中的一個(gè)問題論形式邏輯中的一個(gè)問題”的論文，奠定了的論文，奠定了 Ramsey理論的基礎(chǔ)。理論的基礎(chǔ)。核心思想是：核心思想是：“任何一個(gè)足夠大的結(jié)構(gòu)中必定包含任何一個(gè)足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)一個(gè)給定大小的規(guī)則子結(jié)構(gòu)”20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理第二章第二章 鴿巢原理和鴿巢原理和Ramsey定理定理2.1 鴿巢原理的簡單形式2.2 鴿巢原理的加強(qiáng)形式2.3 Ramsey定理20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理2.1 鴿巢原理的簡單形式鴿巢原理的簡單形式鴿巢原理是組合學(xué)中最簡單、最基本原理也叫抽屜原理抽屜原理(又稱為又稱為重疊原理重疊原理或或狄利克雷狄利克雷(Dirichlet)原理原理）。定理定理2.1.1若把n+1個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有2個(gè)或更多的物體20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理證明證明 如果每個(gè)盒子中至多有一如果每個(gè)盒子中至多有一個(gè)物體，那么個(gè)物體，那么n個(gè)盒子中至多有個(gè)盒子中至多有n個(gè)物體，而我們共有個(gè)物體，而我們共有n+1個(gè)物個(gè)物體，矛盾。體，矛盾。故定理成立。故定理成立。鴿巢原理的鴿巢原理的集合描述形式集合描述形式：設(shè)有限集合設(shè)有限集合A有有n+1個(gè)元素，將個(gè)元素，將A分劃成分劃成n個(gè)不個(gè)不相交子集的并，則至少有一個(gè)子集含有兩個(gè)或相交子集的并，則至少有一個(gè)子集含有兩個(gè)或兩個(gè)以上的元素。兩個(gè)以上的元素。定理是用群體的整體性表現(xiàn)出個(gè)體的某些特定理是用群體的整體性表現(xiàn)出個(gè)體的某些特性，屬于從宏觀到微觀的理論研究成果性，屬于從宏觀到微觀的理論研究成果注意注意 應(yīng)用時(shí)要分清物品與盒子以及物體數(shù)與盒子總數(shù)。應(yīng)用時(shí)要分清物品與盒子以及物體數(shù)與盒子總數(shù)。這個(gè)原理只能用來證明某種安排的這個(gè)原理只能用來證明某種安排的存在性存在性，而卻不，而卻不能找到具體滿足要求的安排能找到具體滿足要求的安排 不能被推廣到只存在不能被推廣到只存在n個(gè)個(gè)(或更少或更少)物體的情形。物體的情形。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理例例2.1.1 證明：13個(gè)人中必有兩人的屬相相同。u 幾個(gè)例子幾個(gè)例子例例2.1.2 有5雙不同的襪子混在一個(gè)抽屜里，我們至少從中選出多少只襪子才能保證找到1雙襪子？20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理解解 應(yīng)用定理應(yīng)用定理2.1.1，共有，共有5個(gè)盒子，個(gè)盒子，每個(gè)盒子對(duì)應(yīng)每個(gè)盒子對(duì)應(yīng)1雙襪子。雙襪子。如果選擇如果選擇5+1=6只襪子分別放到它所只襪子分別放到它所屬那雙襪子的盒子中，則必有兩只襪屬那雙襪子的盒子中，則必有兩只襪子落入同一個(gè)盒子中，即為一雙襪子。子落入同一個(gè)盒子中，即為一雙襪子。因此我們至少從中選出因此我們至少從中選出6只襪子才能只襪子才能保證找到保證找到1雙襪子。雙襪子。本例實(shí)際上是知道本例實(shí)際上是知道n個(gè)盒子，而找個(gè)盒子，而找n+1個(gè)物體的問題。個(gè)物體的問題。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理例例2.1.3對(duì)任意給定的對(duì)任意給定的52個(gè)整數(shù)，個(gè)整數(shù)，證明：其中必存在兩個(gè)整數(shù)，要么證明：其中必存在兩個(gè)整數(shù)，要么兩者的和能被兩者的和能被100整除，要么兩者整除，要么兩者的差能被的差能被100整除。整除。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理1 1、已知：、已知：、已知：、已知：5252個(gè)整數(shù)，個(gè)整數(shù)，個(gè)整數(shù)，個(gè)整數(shù)，2 2、目標(biāo)：找被、目標(biāo)：找被、目標(biāo)：找被、目標(biāo)：找被100100整除的兩個(gè)數(shù)整除的兩個(gè)數(shù)整除的兩個(gè)數(shù)整除的兩個(gè)數(shù)3 3、解題途徑：把、解題途徑：把、解題途徑：把、解題途徑：把5252個(gè)物體放到個(gè)物體放到個(gè)物體放到個(gè)物體放到5151個(gè)盒子中，需要構(gòu)個(gè)盒子中，需要構(gòu)個(gè)盒子中，需要構(gòu)個(gè)盒子中，需要構(gòu)造造造造5151個(gè)盒子個(gè)盒子個(gè)盒子個(gè)盒子4 4、根據(jù)題干中要求的兩個(gè)整數(shù)必須具備的性質(zhì)構(gòu)造、根據(jù)題干中要求的兩個(gè)整數(shù)必須具備的性質(zhì)構(gòu)造、根據(jù)題干中要求的兩個(gè)整數(shù)必須具備的性質(zhì)構(gòu)造、根據(jù)題干中要求的兩個(gè)整數(shù)必須具備的性質(zhì)構(gòu)造盒子盒子盒子盒子5 5、是否能夠被、是否能夠被、是否能夠被、是否能夠被100100整除的關(guān)鍵在余數(shù)，那么一個(gè)整數(shù)整除的關(guān)鍵在余數(shù)，那么一個(gè)整數(shù)整除的關(guān)鍵在余數(shù)，那么一個(gè)整數(shù)整除的關(guān)鍵在余數(shù)，那么一個(gè)整數(shù)除以除以除以除以100100的余數(shù)為的余數(shù)為的余數(shù)為的余數(shù)為0 0，1 1，2 2，9999n n 兩個(gè)整數(shù)的和可以被兩個(gè)整數(shù)的和可以被兩個(gè)整數(shù)的和可以被兩個(gè)整數(shù)的和可以被100100整除，則二者的余數(shù)的和是整除，則二者的余數(shù)的和是整除，則二者的余數(shù)的和是整除，則二者的余數(shù)的和是100100n n 兩個(gè)整數(shù)的差可以被兩個(gè)整數(shù)的差可以被兩個(gè)整數(shù)的差可以被兩個(gè)整數(shù)的差可以被100100整除，則二者的余數(shù)相同整除，則二者的余數(shù)相同整除，則二者的余數(shù)相同整除，則二者的余數(shù)相同分析：分析：證明：證明：對(duì)于任意一個(gè)整數(shù)，它除以對(duì)于任意一個(gè)整數(shù)，它除以100的余數(shù)的余數(shù)顯然只能有如下顯然只能有如下100種情況，種情況，0，1，2，3，99而現(xiàn)在有任意給定的而現(xiàn)在有任意給定的52個(gè)整數(shù)，我們需要構(gòu)個(gè)整數(shù)，我們需要構(gòu)造造51個(gè)盒子，即對(duì)這個(gè)盒子，即對(duì)這100個(gè)余數(shù)進(jìn)行分組，個(gè)余數(shù)進(jìn)行分組，共共51組：組：0，1，99，2，98，3，97，49，51，50根據(jù)定理根據(jù)定理2.1.1，這，這52個(gè)整數(shù)，必有兩個(gè)整數(shù)個(gè)整數(shù)，必有兩個(gè)整數(shù)除以除以100的余數(shù)落入上面的余數(shù)落入上面51組中的同一組中，組中的同一組中，若是若是0或或50則說明它們的和及差都能被則說明它們的和及差都能被100整除；整除；若是剩下的若是剩下的49組的話，因?yàn)橐唤M有兩個(gè)余數(shù)，組的話，因?yàn)橐唤M有兩個(gè)余數(shù)，余數(shù)相同則它們的差能被余數(shù)相同則它們的差能被100整除，余數(shù)不同整除，余數(shù)不同則它們的和能被則它們的和能被100整除。整除。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理例例2.1.4 一名象棋大師有一名象棋大師有11周時(shí)間準(zhǔn)備周時(shí)間準(zhǔn)備一場錦標(biāo)賽，她決定每天至少下一盤一場錦標(biāo)賽，她決定每天至少下一盤棋，為了不能太累一周中下棋的次數(shù)棋，為了不能太累一周中下棋的次數(shù)不能多于不能多于12盤。盤。證明證明：她一定在此期：她一定在此期間的連續(xù)若干天中恰好下棋間的連續(xù)若干天中恰好下棋21盤。盤。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理1、題干提供的信息：一共、題干提供的信息：一共11周周2、約束條件：、約束條件：n n 每每周周最多下最多下12盤棋盤棋n n 每每天天至少下至少下1盤棋盤棋 3、目標(biāo)：連續(xù)若干、目標(biāo)：連續(xù)若干天天共下棋共下棋21盤盤4、解題途徑：構(gòu)造下棋盤數(shù)的部分和、解題途徑：構(gòu)造下棋盤數(shù)的部分和分析：分析：20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理證明:令b1，b2，b77分別為這11周中他每天下棋的次數(shù)，并作部分和a1=b1,a2=b1+b2,，a77=b1+b2+b77.20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理所以有所以有1a1a2a3a771211=132(2.1.1)考慮數(shù)列考慮數(shù)列a1,a2,，a77，a1+21,a2+21,，a77+21,它們都在它們都在1與與132+21=153之間，共有之間，共有154項(xiàng)，項(xiàng)，由定理由定理2.1.1知，其中必有兩項(xiàng)相等知，其中必有兩項(xiàng)相等根據(jù)題意，有bi1(1i77),且bi+bi+1+bi+612(1i71),20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理由（由（2.1.1）式知）式知a1,a2,，a77這這77項(xiàng)互不相等，項(xiàng)互不相等，從而從而a1+21,a2+21,，a77+21這這77項(xiàng)也互不相項(xiàng)也互不相等，所以一定存在等，所以一定存在1i aj，則ai與從aj開始的最長遞減子序列合并，組成的子序列的長度Li=Lj+1 Lj；這與Li=Lj矛盾；反證法。假設(shè)既不存在長度為n+1的遞增子序列，也不存在長度為n+1的遞減子序列即1Lin 且 1Min，其中1in2+1，由集合論的知識(shí)知道集合(Li,Mi)的元素?cái)?shù)為n2，根據(jù)定理2.1.1，必然有（Li,Mi）=(Lj,Mj)（i j），當(dāng)然Li=Lj，而且Mi=Mj。對(duì)于序列中的元素ai,aj，分兩種情況：20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理（2）若ai Mj，這又與Mi=Mj矛盾。所以假設(shè)1Lin 且 1Min不成立。原結(jié)論成立。這個(gè)例子的結(jié)論是1935年由數(shù)學(xué)家保羅艾狄胥（Erds）和喬治塞克爾斯（Szekeres）首先給出的，它還有更為有趣的表述：n2+1個(gè)人肩并肩地站成一排，則總能選出n+1個(gè)人，讓他們向前邁出一步，所形成新一排的身高是遞增或遞減的。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理定理定理2.1.1 鴿巢原理簡單形式鴿巢原理簡單形式若把n+1個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有2個(gè)或更多的物體思考？把多少個(gè)物體放到 n 個(gè)盒子中，能保證至少存在一個(gè)盒子中包含 r 個(gè)以上物體？20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理定理定理2.2.1的推論的推論推論推論2.2.1若若 n(r1)+1個(gè)物品個(gè)物品放入放入n個(gè)盒個(gè)盒子子。則則至少有一個(gè)至少有一個(gè)盒子里含有盒子里含有r個(gè)或者更多個(gè)或者更多的物品。的物品。證明證明 在定理在定理2.2.1中取中取q1=q2=qn=r即可。即可。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理2.2 鴿巢原理的加強(qiáng)形式鴿巢原理的加強(qiáng)形式定理定理2.2.1 (鴿巢原理的加強(qiáng)形式鴿巢原理的加強(qiáng)形式)2鴿巢原理的加強(qiáng)形式鴿巢原理的加強(qiáng)形式定理定理2.2.1 的證明的證明證明證明:(反證法反證法)對(duì)于對(duì)于i1，2，n，假設(shè)第，假設(shè)第i個(gè)盒子里至個(gè)盒子里至多含有多含有qi-1個(gè)物品，則個(gè)物品，則n個(gè)盒子里物品數(shù)的個(gè)盒子里物品數(shù)的總和不超過總和不超過 q1+q2+qn n 個(gè)個(gè)與已知條件與已知條件(q1+q2+qn n+1)矛盾。矛盾。20222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理 與簡單形式的關(guān)系與簡單形式的關(guān)系 上節(jié)的鴿巢原理的簡單形式是這一原理的特殊情況，即q1=q2=qn=2，有 q1+q2+qnn+1=n+120222022年年1010月月1111日日第二章第二章 鴿巢原理和鴿巢原理和RamseyRamsey定理定理 推論推論2.2.2 若若設(shè)有設(shè)有n個(gè)正整數(shù)個(gè)正整數(shù)m1,m2,mn滿足下面的不等式滿足下面的不等式 (m1+mn)/n r1,則則 m1,mn中至少有一個(gè)數(shù)中至少有一個(gè)數(shù) r證明證明 由上面的不等式得 m1+mn(r1)n+1，由推論2.2.1，存在mi，使得mir。另外一個(gè)平均原理：另外一個(gè)平均原理：設(shè)有設(shè)有n個(gè)正整數(shù)個(gè)正整數(shù)m1,m2,mn滿足下面的不等式滿足下面的不等式 (m1+mn)/n r+1,則則 m1,mn中至少有一個(gè)數(shù)中至少有一個(gè)數(shù)n，若將m個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有大于等于 個(gè)物體表示取天棚運(yùn)算是大于等于 的最小正整數(shù) 證明：證明：根據(jù) 的定義有：反證法。假定每個(gè)盒子里的物體都小于 個(gè)。，則至多是 個(gè)，那么n個(gè)盒子里的物體總數(shù)n()n =m，與m個(gè)物體矛盾。因此原結(jié)論成立。