鴿巢原理0和式與積式

1、1,第二章鴿巢原理 2.0 和式與積式,2.0.1 和式(Sum formula） 定義 1 a0+a1+…+an稱為a0, a1, …, an的和式，常簡記為,或,(2.0.1),“∑”稱為和號； “ai”稱為和式的通項或累加項，“i”為通項的下標(biāo)或足標(biāo)，用來標(biāo)識和式中,2,不同的項。下標(biāo)i的變化范圍常以邏輯表達式的形式寫在和號下面，簡單時也以羅列的形式表示在和號“∑”的上、下方，下邊指明初值，上邊指明

2、終值，其變化取由初值到終值的相繼遞增整數(shù)。  若令Nn表示前n+1個自然數(shù)所成之集，即Nn={0, 1, 2, …, n}， 則（2.0.1）式還可表示為,3,,命題 1 用和號∑表示的和式中，通項下標(biāo)的改變不影響和式。 例如,都表示同一和式。  當(dāng)通項下標(biāo)不取連續(xù)整數(shù)時，也希望能尋找一些規(guī)律，以便于用和式寫出簡單的表示式，下面給出一些特殊和式的例子。,4,1. 奇數(shù)做下標(biāo),2. 偶數(shù)做下標(biāo),5,3. 雙下標(biāo),

3、4. 給定數(shù)42的所有因子之和:因為 42 =2×21=2×3×7=6×7=1×42=….所以42的所有因子為：1,2,3,6,7,14,21,42,6,1+2+3+6+7+14+21+42= 6. 空和（由邏輯表達式不成立所致， 約定空和的值為0）,7,命題 2（加法的交換律）如果（i1, i2, …, ii）是(1, 2, …, n)的一個置換,則:,命題 3（加法

4、的結(jié)合律）如果1≤m≤n， 則 :,,,8,命題 4（乘法交換律）,命題 5（乘法對加法的分配律）,推論,9,注意到若附加條件xi＞0(1≤i≤n)， 則,2.1.2 積式（Product formula） 與和式類似, 還可以并行的討論積式,或更一般地寫為,10,即積式可轉(zhuǎn)化為和式來處理。條件xi＞0并無實質(zhì)性的限制，因若某個xi=0，則整個積式為0，又恰有k項取負(fù)時，可先對（2.1.8）式兩邊乘(-1)k，以確保x

5、i＞0， 最后再將其恢復(fù)過來。,例如： （1） n的階乘,11,2.1.1 鴿巢原理（簡單形式） 若在n個盒子中放有n+1個物件，則至少有一個盒子中放有兩個或更多的物件。  證明： 若每個盒子中至多存放1個物件，則n個盒子中至多存放n個物件，但因最初已有n+1個物件，這是不可能的。,2.1 鴿巢原理,12,請注意，鴿巢原理沒有能力指出究竟哪個盒子中放有兩個或更多的物件, 若要做到這一點，除非逐個

6、檢查n個盒子。即應(yīng)用鴿巢原理只能證明某種安排或某些現(xiàn)象的存在性，但卻不能用來構(gòu)造這種安排或找出某些現(xiàn)象中的具體例子。 例１　367人中至少有２人的生日相同。,13,例２ 10雙手套中任取11只，其中至少有兩只 是完整配對的。例３ 13人中至少有兩人的屬相相等。例4 為了從n對夫婦中保證選出一對夫婦，至少要從2n個人中任取n+1個人。 證明: 設(shè)先取的n個人，如果其中已經(jīng)有一對夫婦的話，問題已經(jīng)解決；如

7、果這n個人中沒有一對夫妻，那么這n個人可能的分配情況是：,14,1） n個人全部是作丈夫的。 2） n個人全部是作妻子的。 3） n個人中有M1,M2,…Mi位先生和 wi+1,wi+2,wn 位太太，但他們中無夫妻。 前兩種情況只要再增加余下的一個人，總能配成一對夫妻；第三種情況下再增加一位先生就能與wi+1,wi+2,wn 位太太配成一對夫妻

8、，再增加一位太太也能與M1,M2,…Mi位先生配成一對夫妻。,15,例5 給定m個正整數(shù)a1, a2, …, am。則至少存在整數(shù)k和l(1≤k≤l≤m)， 使得,證明 構(gòu)造序列s1=a1, s2=a1+a2, …, sm=a1+a2+…+am (2.3.1) 則有 s1＜ s2 ＜…＜sm 如下分兩種情況討論：(a) 若有一個sh, 使m|sh, 則命題已明(此時 k=1, l=h),1

9、6,(b) 設(shè)若單調(diào)增序列（2.3.1）式中任何一個元素都不能被m整除。 令sh=phm + rh ( ph是整數(shù)，h= 1,2,…m,) , 則因0＜rh＜m,由鴿巢原理，余數(shù)r1, r2, …, rm 對應(yīng)于序列 1, 2, …, m–1；(只有m–1個)則在r1, r2, …, rm 中，必有兩個相同，選中i≠j（不妨設(shè)i＜j）使ri=rj, 從而它們之差的余數(shù)為：,17,這時,例 6 設(shè)a1, a2, a3為任

10、意三個整數(shù),(b1, b2, b3)為(a1, a2, a3)的一個任意置換排列，則: (ai - bi)(i=1, 2, 3) 中至少有一個是偶數(shù)。 ,18,證明: 由鴿巢原理a1, a2, a3中至少有兩個數(shù)同為 奇數(shù)或同為偶數(shù)，不妨設(shè)a1, a2同為奇數(shù)，置換a1, a2, a3 后得b1, b2中至少有一個是奇數(shù)，又因為二奇數(shù)之差必為偶數(shù)，從而a1-b1與a2-b2中至少有一個偶數(shù)。當(dāng)a1, a2同取偶數(shù)

11、時，討論過程類似（因二偶數(shù)之差必為偶數(shù)）。,19,例７　設(shè)a1 , a2 , ··· , a100是由 1和2組成的序列, 已知從其中任一數(shù)開始的順序10個數(shù)的和不超過16．即: ai + ai+1 +… + ai+9 ≤16，1≤ i ≤91則：至少存在 h 和 k ，k > h，使得　　 ah + ah+1 +… + ak = 39 證:　令　

12、 ，j=1,2,… ,100　顯然,20,S1h　Sk－Sh =39 　即 ah + ah+1 +… + ak = 39,21,例8 試證在邊長為 √2的正方形里任取5點,至少有2點的距離不超過1. 如右下圖所示,將邊長為√2的正方形劃為4個全等的小正方形.設(shè)置相隔距離最遠(yuǎn)的點在四個角，顯然中心位置安排第五點到其他A B 四個點距離相等，而且是

13、 最大距離，等于1。C D,,,,,E,22,例9（中國余數(shù)定理）令m和n為二互質(zhì)的正整 數(shù)，并令a和b為二整數(shù)，且: 0≤a≤m-1 以及 0≤b≤n-1 。 于是，存在一個正整數(shù)x，使得x除以m的余數(shù)為a，并且x除以n的余數(shù)為b；即x可以寫成:x=pm+a的同時又

14、可以寫成x=qn+b的形式，說明余數(shù)不同；這里p和q是兩個整數(shù)。 證明：用反證法：我們考慮n個整數(shù),23,0m+a, 1m+a, 2m+a, ….., (n-1)m+a; 這些整數(shù)中每個除以m都余a。假設(shè)其中的兩個除以n有相同的余數(shù)r。令這兩個數(shù)表示形式為im+a和jm+a，其中0≤i＜j≤n-1。因此，存在兩個整數(shù)qi和qj，使得： im+a = qin +r 　及 j

15、m+a = qjn +r 　　從第二個方程減去第一個方程得：　　　　 (j – i)m= ( qj – qi)n,24,由上式可以看出，由于n與m沒有除1外 的公因子，因此n是(j – i)的一個因子。然而， 0≤i＜j≤n-1, 意味著: 0 ＜j-i≤n-1＜n,也就是說n不可能是j - i的因子。該矛盾產(chǎn)生于我們的假設(shè)： n個整數(shù) 0m+a, 1m+a, 2m+a, ….., (n-1

16、)m+a中有兩個除以n有相同的余數(shù)r的數(shù)。因此我們斷言： 這個n數(shù)中的每一個數(shù)除以n都有不同的余數(shù)。,25,根據(jù)鴿巢原理：n個數(shù)，0,1,2,3,…n-1中的每 個數(shù)作為余數(shù)都要出現(xiàn)；其中特殊的數(shù)b也是如此。令p為整數(shù)，滿足0≤p≤n-1 ，且使數(shù) x = pm + a除以n余數(shù)為b。則對于某個適當(dāng)?shù)膓，有x = qn +b成立因此x = pm + a且x = qn +b ，證畢,26,中國余數(shù)定理是說

17、明： 一個整數(shù)x與兩個互質(zhì)的整數(shù)n,m相除，可以得到兩種表示結(jié)果： x = pm + a 和 x = qn+ b ，其中a 和 b 分別是小于除數(shù)m 和 n的余數(shù)，例如： 19 = 9×2+1 = 3×5+4；其中m=2；n=5是互質(zhì) 而選擇n=4的話： 19 = 4×4+3=8×2+2=pm+2 只有一種表示形式。,27,2.1.1 鴿巢原理（加強形

18、式） 定理2.2.1 令q1,q2,…..qn為正整數(shù)。如果將q1+q2+….+qn-n+1個物體放入n個盒子內(nèi)，那么，或者第一個盒子至少含有q1個物體，或者第二個盒子至少含有q2個物體，…..或者第n個盒子至少含有qn個物體。上節(jié)鴿巢原理簡單形式只是加強形式的特殊情況，令qi = 2 那么： q1+q2+….+qn-n+1= 2n-n+1 =n+1 盒子中自少有一,28,若第i個盒子中至多放進qi -1個物件(i=

19、1, 2, …, n)，則放進n個盒子的物件總數(shù)是：,個里放的物品數(shù)量是2個。 證明：用反證法：討論每個盒子最多放物 件的數(shù)量，找出矛盾,29,在初等數(shù)學(xué)中加強形式常用于qi =r 的特殊情況： 推論 1 若n(r-1)+1個物件放進n個盒子中，則至少有一個盒子放進了r個或更多的物件。推論 2 m個物件放進n個盒子，則至少有一個盒子里放的物件數(shù)不少于［(m-1)/n］+1。例如：將5個物

20、件放在3個盒子里， [(m-1)/n]+1= [(5-1)/3]+1=[4/3]+1=1 + 1 = 2至少有一個盒子里放的物件數(shù)不少于2個。,30,推論3若q1, q2, …, qn是n個正整數(shù)，而且 則qi(i=1, 2, …, n)中至少有一個不小于r。 推論2、3是說明平均放置物品的情況，在下面的例題中我們會多次使用

21、。,31,例1 一籃子水果裝有蘋果、香蕉、和橘子。為了 保證籃子內(nèi)或者至少8個蘋果或者至少6個香蕉或者至少9個橘子，則放入籃子中的水果的最小數(shù)量是多少？解：由加強形式可知，無論怎么選擇， （8 + 6 + 9）－3 + 1 = 21件水果將保證籃子內(nèi)的水果數(shù)量滿足所要求的性質(zhì)。而總數(shù)20件水果則不滿足所要求的性質(zhì)。,32,例 2 把兩個大小不等的同心圓盤都劃分成20個 相等的扇區(qū)。在大圓盤的20

22、個扇區(qū)中分別填入10個0及10個1, 對小圓盤只要求用0或1兩種數(shù)字把扇區(qū)填滿而不限制雙方的個數(shù)。 斷言存在某種配合，可使小圓盤的20個扇區(qū)中至少有10個與大圓盤的對應(yīng)扇區(qū)中數(shù)字相同。  證明： 固定小圓盤并讓大圓盤依次轉(zhuǎn)過20個扇面, 這使小圓盤的每個扇面恰碰到10次與自己,33,相同的數(shù)字。對整個小圓盤來說， 相同的數(shù)字總數(shù)應(yīng)是20×10=200。 從而大圓盤平均轉(zhuǎn)過一個扇面使大小圓盤對應(yīng)扇面數(shù)字相同者應(yīng)是200/2

23、0=10。 根據(jù)鴿巢原理，至少有一次，其中對應(yīng)扇面數(shù)字相同者不少于10個。 例如：將小圓盤的扇面全部填數(shù)字0(或者1)這些數(shù)字0(或者1)至少與大圓盤的扇面的十個0(或者1)相同。,34,例6某班有58名學(xué)生，準(zhǔn)備選修的課程有“數(shù)理 邏輯”，“離散數(shù)學(xué)”，“數(shù)理統(tǒng)計”，“組合數(shù)學(xué)”中的1門、 2門、 3門。求證：至少有5名學(xué)生選修的課程相同。4門選修的課程中選修1門的有C(4,1)種;選修2門的有C

24、(4,2)種;選修3門的有C(4,3)種;共有 :C(4,1)+C(4,2)+C(4,3)=4+6+4=14種,35,把14種選修課程的情況當(dāng)作“鴿巢”，學(xué)生當(dāng)作“鴿子”則：有58只“鴿子” 14個“鴿巢”根據(jù)鴿巢原理平均分配法推論2則： [(58-1)/14] +1= [4.07] +1= 5，14種選課情況中至少有一種被5個學(xué)生選中，故58個學(xué)生中至少有5名學(xué)生選修的課程相同。 [ x ]

25、 是x值的取整函數(shù)。,36,例 5（P.Erdos and A.Szekeres, 1935） 試證任意 n2+1個實數(shù)所成的序列a1, a2, …, an2+1中都含有一個長為n+1的遞增子序列或遞減子序列。 證明：思路: 假定沒有長為n+1的遞增子序列，則證明必存在長為n+1的遞減子序列。對每個k(k=1, 2, …, n2+1)，令mk表示以ak為首的最長遞增子序列的長度。若有一個mk＞n, 則命題已證明。

26、下設(shè)對每個k(k=1, 2, …, n2+1),,37,mk≤n，即假設(shè)不存在任何一條長度大于n的遞 增子序列。 因?qū)γ總€k(k=1, 2, …, n2+1), mk≥1，這使n2+1個正整數(shù)m1, m2, …, mn2+1都落在1, 2, …, n之間。由鴿巢原理之二的推論2（取r=n+1的特殊形式），上述n2+1個整數(shù)中必有n+1個完全相同。不失一般性， 令：其中， 1≤k1＜k2＜…＜kn+1≤n2+1。下證：,3

27、8,ak1, ak2, …, akn+1構(gòu)成一長為n+1的遞減子序列。 用反證法:設(shè)若不然,即存在某個i(i=1,2,…,n)使aki ＜ aki+1 , 則因ki＜ki+1,故可對以aki+1為首的最長遞增子序列前再置以aki而得到一條以 aki為首的更最長遞增子序列，但這將導(dǎo)致 mki ＞ mki+1 , 與mki= mki+1 矛盾。 結(jié)論是aki ≥ aki +1,而這對每個i(

28、i=1, 2, …, n)都是對的,從而有ak1 ≥ ak2 ≥ … ≥ akn+1遞減的,39,第二章 鴿巢原理 2.2 Ramsey定理Ramsey問題可以看成是鴿巢原理的推廣下面舉例說明Ramsey問題。例1　6 個人中至少存在３人相互認(rèn)識或者相互不認(rèn)識。,40,證:這個問題與K6的邊２著色存在同色三角形等 價。假定用紅藍(lán)兩種顏色對完全圖K6著色。 我們用紅色邊表示認(rèn)識，用藍(lán)色邊表示不認(rèn)識，如果

29、有一個同色三角形就代表6人中有三人認(rèn)識或者不認(rèn)識；設(shè)K6的頂點集為{v1 , v2 , ··· , v6 }，dr(v)表示與頂點 v 關(guān)聯(lián)的紅色邊的條數(shù)，db(v)表示與 v 關(guān)聯(lián)的藍(lán)色邊的條數(shù)。在K6 中，有：,41,dr(v)＋ db(v)＝５， 由鴿巢原理將5條邊分配成2種顏色，至少有：[(5-1)/2]+1=３條邊同色?，F(xiàn)將證明過程用判斷樹表示如下：,,,,,,,,,,

30、,,,,,,v1,v6,v5,v4,v3,v2,42,dr(v1)≥3?,db(v1)≥3,設(shè)(v1v2) (v1v3) (v1v4)為紅邊,設(shè)(v1v2) (v1v3) (v1v4)為藍(lán)邊,△v2v3v4是紅△ ?,△v2v3v4是藍(lán)△ ?,設(shè)( v2v3 )是藍(lán)邊,設(shè)( v2v3 )是紅邊,△v1v2v3是藍(lán)△,△v1v2v3是紅△,,,,,,,,,,√,√,Y,N,N,N,Y,Y,,,,,,,,,,,,,,,,,,,v6,v5,v

31、4,v3,v2,v1,,43,定理說明：六點夠成的完全圖中，用紅、蘭兩種顏色對邊涂色，總能得到一個紅三角形或者是一個蘭三角形，注意: 6是染兩色時出現(xiàn)同色三角形的最小點數(shù)。若取5點，則可舉出反例(如P22圖2.2 所示)，圖中就沒有同色的三角形，即可使K5不存在同色三角形。,v5,v4,v3,v2,v1,,,,,,,,,,,44,總 結(jié),本次課我們學(xué)習(xí)鴿巢原理、Ramsey定理的基本原理和部分完全圖的多色涂色問題。

32、 要求能夠利用該鴿巢原理解決一些實際問題。,45,本次授課到此結(jié)束 作業(yè)如下: P25 4. 證明：如果從{1, 2, 3 ,..... 2n}中選擇 n+1個整數(shù)，那么總存在兩個整數(shù)，它們之差為1。9. 一間屋子里有10人，他們當(dāng)中沒有人超過60歲(年齡以整數(shù)給出)但又至少不低于1歲，證明：總能找出兩組人(兩組不含相同的人)，各組人年齡和是相同。提中的數(shù)10能更小嗎？,46,15. 證明：對任