組合-chapt3-16鴿巢原理

組合數(shù)學(xué)

第三章鴿巢原理主要內(nèi)容：1.鴿巢原理及其應(yīng)用2.中國剩余定理3.加強(qiáng)形式的鴿巢原理4.Ramsey定理鴿巢原理(P42)定理:若有n個鴿巢,n+1只鴿子,

則至少有一個鴿巢里至少有兩只鴿子.注意這里的任意性.例1.一年365天,今有366個人,

則其中至少有兩個人生日相同.例2.抽屜里有10雙手套,從中取11只出來,

其中至少有兩只是完整配對的.

關(guān)鍵:選鴿巢和鴿子應(yīng)用舉例(P43)例.在邊長為1的正方形內(nèi)任取5點(diǎn),則其中至少有2點(diǎn)的距離不超過Halloweentreats例.設(shè)a1,a2,…,am是正整數(shù)序列,則至少存在整數(shù)k和l,0k<lm,使得m|(ak+1+ak+2+…+al).

鴿子:rk=a1+a2+…+akmodm,k=1,2,…,m,鴿巢:{0,1,…,m-1}

(a)若有rh=0,即m|(a1+a2+…+ah);(b)否則,r1,r2,…,rm取值為{1,2,…,m-1},所以存在k<l使得rk=rl,即m|(ak+1+ak+2+…+al).應(yīng)用:國際象棋大師(P43)一位國際象棋大師有11周的時間備戰(zhàn)比賽,他決定每天至少下1盤棋,但每周不超過12盤.則存在連續(xù)若干天,他恰好下了21盤棋.證明:令ai為到第i天下的總盤數(shù),(ai+21=aj?)1a1

<a2

<…<a77

1112=132,22a1+21

<a2+21

<…<a77+21132+21=153總共有153種取值[1,153],卻有154個數(shù)(77+77)

所以存在i<j使得

ai+21=aj

.中國剩余定理(存在性證明)令m,n互素,0am-1,0bn-1,則方程組

xamodm----(1)

xbmodn-----(2)在[0,mn)內(nèi)有唯一解.例.x2mod3,x1mod5解:x11mod15證明:(1)在[0,mn)內(nèi)只有n個解(模m余a):a,m+a,2m+a,…,(n-1)m+a.這n個數(shù)模n的余數(shù)兩兩不同.(n鴿n巢,沒有同巢)

由鴿巢原理,(1)(2)在[0,mn)內(nèi)有唯一解.中國剩余定理(構(gòu)造性證明)Thmm,n>0s,t,使得s·m+t·n=gcd(m,n).Thm設(shè)m,n互素,0am-1,0bn-1,則方程組

xamodm,xbmodn------------------(*)

有唯一解

xa·t·n+b·s·mmodmn.-------------(**)

例:同余方程組

xa1mod3-----(1),xa2mod5-----(2),

xa3mod7-----(3)由2·3+(-1)·5=1,得(1)(2)的解是x

a1·(-1)·5+a2·2·3

mod15-5a1+6a2

mod15---(4)由1·15+(-2)·7=1,得(4)(3)的解是

x

(-5a1+6a2)·(-2)·7

+a3·1·15

mod105

70a1+21a2+15a3mod105射雕英雄傳中的問題黃蓉給瑛姑出題:今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何.答案:三人同行七十稀,五樹梅花廿一支,七子團(tuán)圓正半月,除百零五便得知.同余方程組

xa1mod3,xa2mod5,xa3mod7的解是

x=70a1+21a2+15a3mod105韓信點(diǎn)兵(-2),孫子算經(jīng)(4),數(shù)書九章(秦九韶13)加強(qiáng)形式(P45)條件鴿巢n個,鴿子m1+m2+…+mn-n+1只,其中m1,m2,…,mn,n都是正整數(shù),結(jié)論鴿巢1鴿子數(shù)m1,或,鴿巢2鴿子數(shù)m2,……或,鴿巢n鴿子數(shù)mn,至少有一個成立.證明:否則,總鴿子數(shù)(m1-1)+(m2-1)+…+(mn-1)

與總鴿子數(shù)為m1+m2+…+mn-n+1矛盾.Erd?s-Szekeres定理(P46)定理:在由n2+1個實(shí)數(shù)構(gòu)成的序列中,必然含有長為n+1的單調(diào)(增或減)子序列.證明:設(shè)序列為a1,a2,…,an2+1,令mk是從ak開始的最長單調(diào)增子序列的長度.若沒有長于n+1的單增序列,則m1,…,mn2+1[1,n]由加強(qiáng)鴿巢原理,存在k1<k2<…<kn+1使得若ak1ak2則必有mk1>mk2,于是:ak5463423192mk3323232211Ramsey問題(P47)命題:6人中或者至少存在3人互相認(rèn)識,

或者至少存在3人互相不認(rèn)識.特點(diǎn):對所有具體互相認(rèn)識情況(215)都成立.該Ramsey問題等價于:六個頂點(diǎn)的完全圖的邊,用紅,藍(lán)二色任意著色,則至少存在一全是紅色邊三角形,或一全藍(lán)色邊三角形.完全圖K6,C(6,2)條邊圖示證明(P47)從6人任取一人A.A和A互相認(rèn)識

的人的集合GG和A互不認(rèn)識

的人的集合HH5個人的反例(P47)K6K3,K3,(K5K3,K3)Ramsey數(shù)與Ramsey定理(P48)Ramsey數(shù)r(a,b)定義為:r(a,b)=min{n|n個人中必有a個互相認(rèn)識,

或者b個互相不認(rèn)識}=min{n|KnKa,Kb

}例如:r(3,3)=6,r(3,4)=9,r(4,4)=18.Ramsey定理:a,b2,pKpKa,Kb.

即r(a,b)<Ramsey定理的證明(P48)r(a,b)=r(b,a),r(a,2)=r(2,a)=a性質(zhì):當(dāng)a,b2時,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,KbA+Know有Ka或Kb.Kr(a,b-1)Ka,Kb-1A+UnKnowhaveKaorKb.Ramsey數(shù)表(補(bǔ)充)3453691449182551425[43,49]618[35,41]723[49,61]828[55,84]936[69,115]10[40,43]abRamsey定理的推廣定理:n1,n2,…,nk2,pKpKn1,Kn2,…,Knk.

例:K17K3,K3,K3.r(3,3,3)=17.Ktp:p個點(diǎn)的全體t-子集定理:t2,

n1,n2,…,nkt,pKtpKtn1,…,Ktnk.t=1:點(diǎn)染色(鴿巢原理)t=2:邊染色(Ramsey定理)t=3:面(三角形)染色(推廣)t=4:體(四面體)染色(推廣)PaulErd?s(埃爾德什

)簡介1913-1996,匈牙利數(shù)學(xué)家,行為古怪的巡回者1984年與陳省身同獲沃爾夫數(shù)學(xué)獎文章最多,合作者最多,Erd?s數(shù),Erd?s問題埃氏詞典:TheBook,,bosses,slaves,died,left,poison,noise,captured,liberated,preach,SF素?cái)?shù)定理,…,Ramsey理論,106.1106.1(105)1971年后使用興奮劑,$500賭約themanwholovedonlynumbers數(shù)字情種一些Erd?s問題($100)證明limnr(n,n)1/n

極限存在

($100)對r(n,n)>(1+c)n給出構(gòu)造性證明

($250)r(4,n)>n3/log3n沃爾夫獎聲明:forhisnumerouscontributionstonumbertheory,combinatorics,probability,settheoryandmathematicalanalysis,andforpersonallystimulatingmathematicianstheworldover作業(yè)作業(yè):P50ex4,7,11,13,16.編程題:HalloweentreatsBiorhythms作業(yè)ex4.證明：如果從集合{1,2,…,2n}中選擇n+1個整數(shù)，

那么總存在兩個數(shù)它們之間相差1.ex7.證明：對任意給定的52個整數(shù)，存在兩個整數(shù)，

要么兩者的和能被100整除，要么兩者的差能被100整除。ex11.一個學(xué)生有37天來準(zhǔn)備考試。根據(jù)以往經(jīng)驗(yàn)，她知道她需要的學(xué)習(xí)

時間不超過60小時。她還希望每天至少學(xué)習(xí)一個小時。

證明，無論她怎么安排學(xué)習(xí)時間(每天學(xué)習(xí)的時間是整數(shù)小時)，

都存在連續(xù)若干天，在此期間她恰好學(xué)習(xí)了13個小時。ex13.設(shè)S是平面上6個點(diǎn)的集合，其中沒有3個點(diǎn)共線。給由S的點(diǎn)

所確定的15條線段著色，將它們或者著成紅色，或者著成藍(lán)色。

證明：至少存在兩個由S的點(diǎn)所確定的三角形或者是紅色三角形

或者是藍(lán)色三角形。ex16.證明：在一群n>1個人中，存在兩人，他們在這群人中有

相同數(shù)目的熟人(假設(shè)自己不是自己的熟人)。補(bǔ)充:不互素的情況Thmm,n>0s,t,使得s·m+t·n=gcd(m,n).定理:設(shè)m,n是正整數(shù),0a<m,0b<n,則方程組

xamodm,xbmodn(*)

有解當(dāng)且僅當(dāng)gcd(m,n)|(b-a).

令d=gcd(m,n),M=lcm(m,n),且d=ms+nt

若d|(b-a),則(*)在[0,M)內(nèi)有唯一解:

x

(ant+bms)/d

modM.(**)證明:若有解,則d|(b-a);若d|(b-a)則(**)是解唯一性:M=mn/d,(a,b)有M種選擇,鴿巢原理.顏色重合扇形數(shù)目大小兩圓盤,劃分成200個恒等扇形.大盤任選100個涂紅色,其余涂藍(lán)色.小盤的200個任選涂紅或藍(lán)色.求證能轉(zhuǎn)動小盤使得100個以上同色.小盤轉(zhuǎn)動一周:

小盤有多少個大小扇形對齊位置?

每個小扇形發(fā)生多少次顏色重合?

總共有多少次顏色重合?

反證法:若每次對齊顏色重合數(shù)99?最大公約數(shù)定理:設(shè)m,n為非負(fù)整數(shù),存在整數(shù)s,t使得

gcd(m,n)=ms+nt.證明:令A(yù)={ma+nb>0|任意整數(shù)a,b}r=minA,d=gcd(m,n)(1)dr(r是d的倍數(shù)dr)(2)dr(r是m,n的公因子dr)

設(shè)r=ma+nb

且r不是

m的因子,

則m=qr+p,其中0<p<r,即

p=m(1-qa)+n(-qb)pA矛盾.Euclid算法:計(jì)算最大公約數(shù)d定理:設(shè)m,n為非負(fù)整數(shù),存在整數(shù)s,t使得

d:=gcd(m,n)=ms+nt.Euclid方法(輾轉(zhuǎn)相除法)gcd(56,12)=gcd(12,8)=gcd(8,4)=gcd(4,0)=4Euclid算法(輾轉(zhuǎn)相除法)輸入m,n,輸出dEuclid(a,b)1.ifb=0,thenreturna