組合數學2

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

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

3、. 雙下標,4. 給定數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)的一個置換,則:,命

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

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

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

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個整數a1, a2, …, am。則至少存在整 數k和l(1≤k≤l≤m)， 使得,證明 構造序列s1=a1, s2=a1+a2, …, sm=a1+a2+…+am (2.3.1) 則有 s1＜ s2 ＜…＜sm 如下分兩種情況討論：,16,(a) 若有一個sh,

9、 使m|sh, 則命題已明（此時 k=1, l=h）; (b) 設若單調增序列（2.3.1）式中任何一個元素都不能被m整除。 令sh=phm + rh ( ph是整數，h= 1,2,…m,) , 則因0＜rh＜m,由鴿巢原理，序列r1, r2, …, rm 相對于序列 1, 2, …, m – 1；則在r1, r2, …, rm 中，必有兩個相同，選中i≠j（不妨設i＜j）使ri=

10、rj, 從而它們之差的余數為：,17,這時,例 6 設a1, a2, a3為任意三個整數,(b1, b2, b3)為(a1, a2, a3)的一個任意置換排列，則: (ai - bi)(i=1, 2, 3) 中至少有一個是偶數。 ,18,證明: 由鴿巢原理a1, a2, a3中至少有兩個數同為 奇數或同為偶數，不妨設a1, a2同為奇數，置換a1, a2, a3 后得b1, b2中至少有一個是奇數，因為二奇數之

11、差必為偶數，從而a1-b1與a2-b2中至少有一個偶數。當a1, a2同取偶數時，討論過程類似（因二偶數之差必為偶數）。,19,例７　設a1 , a2 , ··· , a100是由 1和２組成的序列, 已知從其任一數開始的順序10個數的和 不超過16．即: ai + ai+1 +… + ai+9 ≤16，1≤ i ≤91則至少存在 h 和 k ，k

12、> h，使得　　 ah + ah+1 +… + ak = 39 證:　令　Sj = ∑ai，j=1,2,… ,100　顯然,20,S1h　Sk－Sh =39 　即 ah + ah+1 +… + ak = 39,21,例8 試證在邊長為 √2的正方形里任取5點,至少有2點的距離不超過1. 如右下圖所示,將邊長為√2的正方形劃為4個全等的小正方形.設置相隔距離最遠的點在四個角，顯然中心位置安

13、排第五點到其他A B 四個點距離相等，而且是 最大距離，等于1。C D,,,,,E,22,例9（中國余數定理）令m和n為二互質的 正整 數，并令a和b為二整數，且: 0≤a≤m-1 以及 0≤b≤n

14、-1 。 于是，存在一個正整數x，使得x除以m的余數為a，并且x除以n的余數為b；即x可以寫成:x=pm+a的同時又可以寫成x=qn+b的形式，s說明余數不同；這里p和q是兩個整數。 證明：用反證法：我們考慮n個整數,23,0m+a, 1m+a, 2m+a, ….., (n-1)m+a; 這些整數中每個除以m都余a。假設其中的兩個除以n有相同的余數r。令這兩個數表示形式為im+a和jm+a，其中0≤i＜

15、j≤n-1。因此，存在兩個整數qi和qj，使得： im+a = qin +r 　及 jm+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

16、 - i的因子。該矛盾產生于我們的假設： n個整數 0m+a, 1m+a, 2m+a, ….., (n-1)m+a中有兩個除以n有相同的余數r的數。因此我們斷言：這個n數中的每一個數除以n都有不同的余數。,25,根據鴿巢原理：n個數，0,1,2,3,…n-1中的每 個數作為余數都要出現；其中特殊的數b也是如此。令p為整數，滿足0≤p≤n-1 ，且使數x = pm + a除以n余數為b。則對于某個適當的

17、q，有x = qn +b成立因此x = pm + a且x = qn +b ，證畢,26,,中國余數定理是說明： 一個整數x與兩個互質的整數n,m相除，可以得到兩種表示結果： x = pm + a 和 x = qn+ b ，其中a 和 b 分別是小于除數m 和 n的余數，例如： 19 = 9×2+1 = 3×5+4；其中m=2；n=5是互質 而選擇n=4的話： 19 = 4&

18、#215;4+3=8×2+2=pm+2 只有一種表示形式。,27,2.1.1 鴿巢原理（加強形式） 定理2.2.1 令q1,q2,…..qn為正整數。如果將q1+q2+….+qn-n+1個物體放入n個盒子內，那么，或者第一個盒子至少含有q1個物體，或者第二個盒子至少含有q2個物體，…..或者第n個盒子至少含有qn個物體。上節(jié)鴿巢原理簡單形式只是加強形式的特殊情況，令qi = 2 那么： q1+q2+….+

19、qn-n+1= 2n-n+1 =n+1 盒子中自少有一,28,若第i個盒子中至多放進qi -1個物件(i=1, 2, …, n)，則放進n個盒子的物件總數是：,個里放的物品數量是2個。 證明：用反證法：討論每個盒子最多放物 件的數量，找出矛盾,29,在初等數學中加強形式常用于qi =r 的特殊情況： 推論 1 若n(r-1)+1個物件放進n個盒子中，則至少有一個盒子放進了r個或更多的物件。

20、推論 2 m個物件放進n個盒子，則至少有一個盒子里放的物件數不少于［(m-1)/n］+1。例如：將5個物件放在3個盒子里， [(m-1)/n]+1= [(5-1)/3]+1=[4/3]+1=1 + 1 = 2至少有一個盒子里放的物件數不少于2個。,30,推論3若q1, q2, …, qn是n個正整數，而且 則qi(i=1, 2, …, n)中至少有一個不小于r。 推論2、3是說明

21、平均放置物品的情況，在下面的例題中我們會多次使用。,31,例1 一籃子水果裝有蘋果、香蕉、和橘子。為了 保證籃子內或者至少8個蘋果或者至少6個香蕉或者至少9個橘子，則放入籃子中的水果的最小數量是多少？解：由加強形式可知，無論怎么選擇， （8 + 6 + 9）－3 + 1 = 21件水果將保證籃子內的水果數量滿足所要求的性質。而總數20件水果則不滿足所要求的性質。,32,例 2 把兩個大小不等的同心圓盤都劃分成

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

23、個扇面使大小圓盤對應扇面數字相同者應是200/20=10。 根據鴿巢原理，至少有一次，其中對應扇面數字相同者不少于10。,34,例6某班有58名學生，準備選修的課程有“數理 邏輯”，“離散數學”，“數理統(tǒng)計”，“組合數學”中的1門、 2門、 3門。求證：至少有5名學生選修的課程相同。4門選修的課程中選修1門的有C(4,1)種;選修2門的有C(4,2)種;選修3門的有C(4,3)種;共有 :C(4,1)+C(4,2)+

24、C(4,3)=4+6+4=14種,35,把14種選修課程的情況當作“鴿巢”，學生當作“鴿子”則：有58只“鴿子” 14個“鴿巢”根據鴿巢原理[(58-1)/14] +1= [4.07] +1= 5，14種選課情況中至少有一種被5個學生選中，故58個學生中至少有5名學生選修的課程相同。[ x ] 是x值的取整函數。,36,例 5（P.Erdos and A.Szekeres, 1935） 試證任意 n2+1個實數

25、所成的序列a1, a2, …, an2+1中都含有一個長為n+1的遞增子序列或遞減子序列。 證明 證明思路: 假定沒有長為n+1的遞增子序列，必可推得存在長為n+1的遞減子序列或反之。 對每個k(k=1, 2, …, n2+1)，令mk表示以ak為首的最長遞增子序列的長度。若有一個mk＞n, 則命題已證明。下設對每個k(k=1, 2, …, n2+1),,37,mk≤n，即假設不存在任何一條長度大于n的遞 增子序列。 因對

26、每個k(k=1, 2, …, n2+1), mk≥1，這使n2+1個正整數m1, m2, …, mn2+1都落在1, 2, …, n之間。由鴿巢原理之二的推論2（取r=n+1的特殊形式），上述n2+1個整數中必有n+1個完全相同。不失一般性， 令：其中， 1≤k1＜k2＜…＜kn+1≤n2+1。下證：,38,ak1, ak2, …, akn+1構成一長為n+1的遞增子序列。 用反證法:設若不然,即存在某個i(i=1,2,

27、…,n)使aki ＜ aki+1 , 則因ki＜ki+1,故可對以aki+1為首的最長遞增子序列前再置以aki而得到一條以 aki為首的最長遞增子序列，但這將導致 mki ＞ mki+1 , 與mki= mki+1 矛盾。 結論是aki ≥ aki +1,而這對每個i(i=1, 2, …, n)都是對的,從而有ak1 ≥ ak2 ≥ … ≥ akn+1,39,總 結,本次課我們學習鴿巢