组合数学第二章 鸽巢原理.ppt

《组合数学第二章 鸽巢原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、组合数学第二章鸽巢原理主要内容：1.鸽巢原理及其应用2.中国剩余定理3.加强形式的鸽巢原理4.Ramsey定理鸽巢原理定理:若有n个鸽巢,n+1只鸽子,则至少有一个鸽巢里至少有两只鸽子.注意这里的任意性.例1.一年365天,今有366个人,则其中至少有两个人生日相同.例2.抽屉里有10双手套,从中取11只出来,其中至少有两只是完整配对的.应用举例例.在边长为1的正方形内任取5点,则其中至少有2点的距离不超过例.设a1,a2,…,am是正整数序列,则至少存在整数k和l,0k

2、(ak+1+ak+2+…+al).令rk=a1+a2+…+akmodm,k=1,2,…,m,则(

3、a)若有rh=0,即m

4、(a1+a2+…+ah);(b)否则,r1,r2,…,rm取值为{1,2,…,m-1},所以存在k

5、(ak+1+ak+2+…+al).应用:国际象棋大师一位国际象棋大师有11周的时间备战比赛,他决定每天至少下1盘棋,但每周不超过12盘.则存在连续若干天,他恰好下了21盘棋.证明:令ai为到第i天下的总盘数,(ai+21=aj?)1a1

6、入n个鸽巢并且没有一个鸽巢是空的，那么每个鸽巢恰好包含一只鸽子。推论2：如果将n只鸽子放入n个鸽巢并且没有鸽巢被放入多于一只的鸽子，那么每个鸽巢里有一只鸽子。中国剩余定理(简单形式)令m,n互素,0am-1,0bn-1,则方程组xamodmxbmodn在[0,mn]内有唯一解.证明:下面的n个数(模m都是a)a,m+a,2m+a,…,(n-1)m+a,模n的余数两两不同.中国剩余定理(完全形式)令m1,…,mr两两互素,a1,…,ar为整数,则同余方程组xaimodmi,i=1,…,r模M(=m1m2…mr)有唯一解其中Mi=M/mi,yiMi1modmi.例:(3,5,

7、7)--(35,2),(21,1),(15,1)x=70a1+21a2+15a3mod105射雕英雄传中的问题黄蓉给瑛姑出题:今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何.答案:三人同行七十稀,五树梅花廿一支,七子团圆正半月,除百零五便得知.同余方程组x2mod3,x3mod5,x2mod7的解是x=70×2+21×3+15×2mod105韩信点兵,孙子算经,数书九章(秦九韶)补充:不互素的情况定理:设m,n是正整数,0a

8、(b-a).令d=gcd(m,n),M=lcm(

9、m,n).若d

10、(b-a),则(*)在[0,M)内有唯一解:xa+cm[(b-a)/d]modM.参考多元一次同余方程组的解法.加强形式条件鸽巢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定理定理:在由n2+1个实数构成的序列中,必然含有长为n+1的单调(增或减)子序列.证明:设序列为a1,a2,…,an2+1,令mk是从

11、ak开始的最长单调增子序列的长度.若没有长于n+1的单增序列,则m1,…,mn2+1[1,n]由加强鸽巢原理,存在k1mk2,于是:ak5463423192mk3323232211Ramsey问题命题:6人中或者至少存在3人互相认识,或者至少存在3人互相不认识.特点:对所有具体互相认识情况(215)都成立.该Ramsey问题等价于:六个顶点的完全图的边,用红,蓝二色任意着色,则至少存在一红色边三角形,或一蓝色边三角形.完全图,条边图示证明从6人任取一人A.A和A互相认识的人的集合GG和A互不认识的人的集合HH5个人的反例K6K3

12、,K3,(K5K3,K3)Ramsey数与Ramsey定理Ramsey数r(a,b)定义为:r(a,b)=min{n

13、n个人中必有a个互相认识,或者b个互相不认识}=min{n

14、KnKa,Kb}例如:r(3,3)=6,r(3,4)=9,r(4,4)=18.Ramsey定理:a,b2,pKpKa,Kb.即r(a,b)<Ramsey定理的证明r(a,b)=r(b,a),r(a,2)=r(2,a)=a性质:当a