組合數(shù)學第二章鴿巢原理

1、組合數(shù)學第二章鴿巢原理鴿巢原理鴿巢原理定理定理: 若有若有n個鴿巢個鴿巢, n+1只鴿子只鴿子, 則至少有一個鴿巢里至少有兩只鴿子則至少有一個鴿巢里至少有兩只鴿子.注意這里的任意性注意這里的任意性.例例1. 一年一年365天天, 今有今有366個人個人, 則其中至少有兩個人生日相同則其中至少有兩個人生日相同.例例2. 抽屜里有抽屜里有10雙手套雙手套, 從中取從中取11只出來只出來, 其中至少有兩只是完整配對的其中至少有兩只是完整配對的.應用舉例應用舉例例例. 在邊長為在邊長為1的正方形內(nèi)任取的正方形內(nèi)任取5點點,則則 其中至少有其中至少有2點的距離不超過點的距離不超過2/2例例. 設(shè)設(shè)a1,

2、a2,am是正整數(shù)序列是正整數(shù)序列, 則至少存在則至少存在 整數(shù)整數(shù)k和和l, 0 kl m, 使得使得m|(ak+1+ak+2+ al). 令令rk=a1+a2+ak mod m, k=1,2,m, 則則 (a) 若有若有rh=0, 即即m|(a1+a2+ ah); (b) 否則否則, r1,r2,rm取值為取值為1,2,m-1, 所以所以 存在存在kl使得使得rk=rl , 即即m|(ak+1+ak+2+ al).應用應用:國際象棋大師國際象棋大師一位國際象棋大師有一位國際象棋大師有11周的時間備戰(zhàn)比賽周的時間備戰(zhàn)比賽,他決定每天至少下他決定每天至少下1盤棋盤棋,但每周不超過但每周不超過1

3、2盤盤.則存在連續(xù)若干天則存在連續(xù)若干天,他恰好下了他恰好下了21盤棋盤棋.證明證明: 令令ai為到第為到第i天下的總盤數(shù)天下的總盤數(shù), (ai+21=aj?)1 a1 a2 a77 11 12=132,22 a1+21 a2+21 a77+21 132+21=153 總共有總共有153種取值種取值, 卻有卻有154個數(shù)個數(shù) 所以存在所以存在ij使得使得 ai+21=aj .鴿巢原理鴿巢原理推論推論1： 如果將如果將n只鴿子放入只鴿子放入n個鴿巢并且沒個鴿巢并且沒有一個鴿巢是空的，那么每個鴿巢恰好包含有一個鴿巢是空的，那么每個鴿巢恰好包含一只鴿子。一只鴿子。推論推論2： 如果將如果將n只鴿子放

4、入只鴿子放入n個鴿巢并且沒個鴿巢并且沒有鴿巢被放入多于一只的鴿子，那么每個鴿有鴿巢被放入多于一只的鴿子，那么每個鴿巢里有一只鴿子。巢里有一只鴿子。中國剩余定理中國剩余定理(簡單形式簡單形式)令令m,n互素互素, 0 a m-1, 0 b n-1, 則方程組則方程組 x a mod m x b mod n在在0,mn內(nèi)有唯一解內(nèi)有唯一解.證明證明: 下面的下面的n個數(shù)個數(shù)(模模m都是都是a) a, m+a, 2m+a, , (n-1)m+a, 模模n的余數(shù)兩兩不同的余數(shù)兩兩不同.中國剩余定理中國剩余定理(完全形式完全形式)令令m1,mr兩兩互素兩兩互素, a1,ar為整數(shù)為整數(shù), 則同余方程組則

5、同余方程組 x ai mod mi, i=1,r模模M(=m1m2mr)有唯一解有唯一解MyMaxriiii mod1其中其中Mi=M/mi , yi Mi 1 mod mi.例例: (3,5,7)-(35,2), (21, 1), (15, 1) x = 70a1 + 21a2 + 15a3 mod 105 射雕英雄傳中的問題射雕英雄傳中的問題黃蓉給瑛姑出題黃蓉給瑛姑出題:今有物不知其數(shù)今有物不知其數(shù),三三數(shù)之剩二三三數(shù)之剩二, 五五數(shù)之剩三五五數(shù)之剩三,七七數(shù)之剩二七七數(shù)之剩二, 問物幾何問物幾何.答案答案:三人同行七十稀三人同行七十稀,五樹梅花廿一支五樹梅花廿一支,七子團圓正半月七子團圓

6、正半月,除百零五便得知除百零五便得知.同余方程組同余方程組 x 2 mod 3, x 3 mod 5, x 2 mod 7的解是的解是 x = 702 + 213 + 152 mod 105韓信點兵韓信點兵, 孫子算經(jīng)孫子算經(jīng), 數(shù)書九章數(shù)書九章(秦九韶秦九韶)補充補充: 不互素的情況不互素的情況定理定理:設(shè)設(shè)m,n是正整數(shù)是正整數(shù), 0 am, 0 bn, 則方程組則方程組 x a mod m, x b mod n (*) 有解當且僅當有解當且僅當gcd(m,n)|(b-a). 令令d=gcd(m,n), M=lcm(m,n). 若若d|(b-a), 則則(*)在在0,M)內(nèi)有唯一解內(nèi)有唯一

7、解: x a + c m (b-a)/d mod M.參考多元一次同余方程組的解法參考多元一次同余方程組的解法.加強形式加強形式條件條件鴿巢鴿巢n個個, 鴿子鴿子m1+m2+mn-n+1只只,其中其中 m1,m2,mn, n都是正整數(shù)都是正整數(shù), 結(jié)論結(jié)論鴿巢鴿巢1鴿子數(shù)鴿子數(shù) m1,或或,鴿巢鴿巢2鴿子數(shù)鴿子數(shù) m2, 或或,鴿巢鴿巢n鴿子數(shù)鴿子數(shù) mn,至少有一個成立至少有一個成立.證明證明:否則否則, 總鴿子數(shù)總鴿子數(shù) (m1-1)+(m2-1)+(mn-1) 與總鴿子數(shù)為與總鴿子數(shù)為m1+m2+mn-n+1矛盾矛盾.Erds-Szekeres定理定理121nkkkmmm定理定理: 在由

8、在由n2+1個實數(shù)構(gòu)成的序列中個實數(shù)構(gòu)成的序列中, 必然必然 含有長為含有長為n+1的單調(diào)的單調(diào)(增或減增或減)子序列子序列.證明證明:設(shè)序列為設(shè)序列為 a1, a2, , an2+1,令令mk是從是從ak開始的最長單調(diào)增子序列的長度開始的最長單調(diào)增子序列的長度.若沒有長于若沒有長于n+1的單增序列的單增序列,則則m1,mn2+1 1,n由加強鴿巢原理由加強鴿巢原理, 存在存在k1k2 mk2,于是于是:121nkkkaaaak 5 4 6 3 4 2 3 1 9 2mk 3 3 2 3 2 3 2 2 1 1Ramsey問題問題命題命題: 6人中或者至少存在人中或者至少存在3人互相認識人互相

9、認識, 或者至少存在或者至少存在3人互相不認識人互相不認識.特點特點: 對所有具體互相認識情況對所有具體互相認識情況(215)都成立都成立.該該Ramsey問題等價于問題等價于:六個頂點的六個頂點的完全圖完全圖的邊的邊, 用紅用紅,藍二色任意著色藍二色任意著色, 則至少存在一紅色邊三角形則至少存在一紅色邊三角形, 或一藍色邊三角形或一藍色邊三角形.完全圖完全圖, 條邊條邊256 圖示證明圖示證明從從6人任取一人人任取一人A.A和和A互相認識互相認識的人的集合的人的集合GG和和A互不認識互不認識的人的集合的人的集合HH5個人的反例個人的反例K6 K3, K3, (K5 K3, K3)Ramsey

10、數(shù)與數(shù)與Ramsey定理定理Ramsey數(shù)數(shù)r(a,b)定義為定義為:r(a,b) = min n | n個人中必有個人中必有 a個互相認識個互相認識, 或者或者b個互相不認識個互相不認識 = min n | KnKa, Kb 例如例如: r(3,3)=6, r(3,4)=9, r(4,4)=18.Ramsey定理定理: a,b 2, p KpKa, Kb. 即即 r(a,b) Ramsey定理的證明定理的證明r(a,b)=r(b,a), r(a,2)=r(2,a)=a性質(zhì)性質(zhì): 當當a,b 2時時, r(a,b) r(a-1,b)+r(a,b-1). 在在r(a-1,b)+r(a,b-1)個人中任選一人個人中任選一人A, 其他人分成兩個集合其他人分成兩個集合Know, Unknow.|Know|+|Unknow|= r(a-1,b) + r(a,b-1) - 1 |Know| r(a-1,b) 或者或者 |Unknow| r(a,b-1) Kr(a-1,b)Ka-1, Kb A Know有有Ka或或Kb.Ramsey數(shù)表數(shù)表345369144918255142543,4961835,4172349,6182855,8493669,1151040,43abRam