组合-chapt3-16鸽巢原理

组合数学

第三章鸽巢原理主要内容：1.鸽巢原理及其应用2.中国剩余定理3.加强形式的鸽巢原理4.Ramsey定理鸽巢原理(P42)定理:若有n个鸽巢,n+1只鸽子,

则至少有一个鸽巢里至少有两只鸽子.注意这里的任意性.例1.一年365天,今有366个人,

则其中至少有两个人生日相同.例2.抽屉里有10双手套,从中取11只出来,

其中至少有两只是完整配对的.

关键:选鸽巢和鸽子应用举例(P43)例.在边长为1的正方形内任取5点,则其中至少有2点的距离不超过Halloweentreats例.设a1,a2,…,am是正整数序列,则至少存在整数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).应用:国际象棋大师(P43)一位国际象棋大师有11周的时间备战比赛,他决定每天至少下1盘棋,但每周不超过12盘.则存在连续若干天,他恰好下了21盘棋.证明:令ai为到第i天下的总盘数,(ai+21=aj?)1a1

<a2

<…<a77

1112=132,22a1+21

<a2+21

<…<a77+21132+21=153总共有153种取值[1,153],却有154个数(77+77)

所以存在i<j使得

ai+21=aj

.中国剩余定理(存在性证明)令m,n互素,0am-1,0bn-1,则方程组

xamodm----(1)

xbmodn-----(2)在[0,mn)内有唯一解.例.x2mod3,x1mod5解:x11mod15证明:(1)在[0,mn)内只有n个解(模m余a):a,m+a,2m+a,…,(n-1)m+a.这n个数模n的余数两两不同.(n鸽n巢,没有同巢)

由鸽巢原理,(1)(2)在[0,mn)内有唯一解.中国剩余定理(构造性证明)Thmm,n>0s,t,使得s·m+t·n=gcd(m,n).Thm设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射雕英雄传中的问题黄蓉给瑛姑出题:今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何.答案:三人同行七十稀,五树梅花廿一支,七子团圆正半月,除百零五便得知.同余方程组

xa1mod3,xa2mod5,xa3mod7的解是

x=70a1+21a2+15a3mod105韩信点兵(-2),孙子算经(4),数书九章(秦九韶13)加强形式(P45)条件鸽巢n个,鸽子m1+m2+…+mn-n+1只,其中m1,m2,…,mn,n都是正整数,结论鸽巢1鸽子数m1,或,鸽巢2鸽子数m2,……或,鸽巢n鸽子数mn,至少有一个成立.证明:否则,总鸽子数(m1-1)+(m2-1)+…+(mn-1)

与总鸽子数为m1+m2+…+mn-n+1矛盾.Erdös-Szekeres定理(P46)定理:在由n2+1个实数构成的序列中,必然含有长为n+1的单调(增或减)子序列.证明:设序列为a1,a2,…,an2+1,令mk是从ak开始的最长单调增子序列的长度.若没有长于n+1的单增序列,则m1,…,mn2+1[1,n]由加强鸽巢原理,存在k1<k2<…<kn+1使得若ak1ak2则必有mk1>mk2,于是:ak5463423192mk3323232211Ramsey问题(P47)命题:6人中或者至少存在3人互相认识,

或者至少存在3人互相不认识.特点:对所有具体互相认识情况(215)都成立.该Ramsey问题等价于:六个顶点的完全图的边,用红,蓝二色任意着色,则至少存在一全是红色边三角形,或一全蓝色边三角形.完全图K6,C(6,2)条边图示证明(P47)从6人任取一人A.A和A互相认识

的人的集合GG和A互不认识

的人的集合HH5个人的反例(P47)K6K3,K3,(K5K3,K3)Ramsey数与Ramsey定理(P48)Ramsey数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,b2,pKpKa,Kb.

即r(a,b)<Ramsey定理的证明(P48)r(a,b)=r(b,a),r(a,2)=r(2,a)=a性质:当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数表(补充)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个点的全体t-子集定理:t2,

n1,n2,…,nkt,pKtpKtn1,…,Ktnk.t=1:点染色(鸽巢原理)t=2:边染色(Ramsey定理)t=3:面(三角形)染色(推广)t=4:体(四面体)染色(推广)PaulErdös(埃尔德什

)简介1913-1996,匈牙利数学家,行为古怪的巡回者1984年与陈省身同获沃尔夫数学奖文章最多,合作者最多,Erdös数,Erdös问题埃氏词典:TheBook,,bosses,slaves,died,left,poison,noise,captured,liberated,preach,SF素数定理,…,Ramsey理论,106.1106.1(105)1971年后使用兴奋剂,$500赌约themanwholovedonlynumbers数字情种一些Erdös问题($100)证明limnr(n,n)1/n

极限存在

($100)对r(n,n)>(1+c)n给出构造性证明

($250)r(4,n)>n3/log3n沃尔夫奖声明:forhisnumerouscontributionstonumbertheory,combinatorics,probability,settheoryandmathematicalanalysis,andforpersonallystimulatingmathematicianstheworldover作业作业:P50ex4,7,11,13,16.编程题:HalloweentreatsBiorhythms作业ex4.证明：如果从集合{1,2,…,2n}中选择n+1个整数，

那么总存在两个数它们之间相差1.ex7.证明：对任意给定的52个整数，存在两个整数，

要么两者的和能被100整除，要么两者的差能被100整除。ex11.一个学生有37天来准备考试。根据以往经验，她知道她需要的学习

时间不超过60小时。她还希望每天至少学习一个小时。

证明，无论她怎么安排学习时间(每天学习的时间是整数小时)，

都存在连续若干天，在此期间她恰好学习了13个小时。ex13.设S是平面上6个点的集合，其中没有3个点共线。给由S的点

所确定的15条线段着色，将它们或者着成红色，或者着成蓝色。

证明：至少存在两个由S的点所确定的三角形或者是红色三角形

或者是蓝色三角形。ex16.证明：在一群n>1个人中，存在两人，他们在这群人中有

相同数目的熟人(假设自己不是自己的熟人)。补充:不互素的情况Thmm,n>0s,t,使得s·m+t·n=gcd(m,n).定理:设m,n是正整数,0a<m,0b<n,则方程组

xamodm,xbmodn(*)

有解当且仅当gcd(m,n)|(b-a).

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

若d|(b-a),则(*)在[0,M)内有唯一解:

x

(ant+bms)/d

modM.(**)证明:若有解,则d|(b-a);若d|(b-a)则(**)是解唯一性:M=mn/d,(a,b)有M种选择,鸽巢原理.颜色重合扇形数目大小两圆盘,划分成200个恒等扇形.大盘任选100个涂红色,其余涂蓝色.小盘的200个任选涂红或蓝色.求证能转动小盘使得100个以上同色.小盘转动一周:

小盘有多少个大小扇形对齐位置?

每个小扇形发生多少次颜色重合?

总共有多少次颜色重合?

反证法:若每次对齐颜色重合数99?最大公约数定理:设m,n为非负整数,存在整数s,t使得

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

设r=ma+nb

且r不是

m的因子,

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

p=m(1-qa)+n(-qb)pA矛盾.Euclid算法:计算最大公约数d定理:设m,n为非负整数,存在整数s,t使得

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