《组合数学第二章鸽巢原理.ppt》由会员分享，可在线阅读，更多相关《组合数学第二章鸽巢原理.ppt（19页珍藏版）》请在三一文库上搜索。
1、组合数学 第二章 鸽巢原理,主要内容： 1. 鸽巢原理及其应用 2. 中国剩余定理 3. 加强形式的鸽巢原理 4. Ramsey定理,鸽巢原理,定理: 若有n个鸽巢, n+1只鸽子, 则至少有一个鸽巢里至少有两只鸽子. 注意这里的任意性. 例1. 一年365天, 今有366个人, 则其中至少有两个人生日相同. 例2. 抽屉里有10双手套, 从中取11只出来, 其中至少有两只是完整配对的.,应用举例,例. 在边长为1的正方形内任取5点,则 其中至少有2点的距离不超过,例. 设a1,a2,am是正整数序列, 则至少存在 整数k和l, 0kl m, 使得m|(ak+1+ak+2+ al). 令rk=
2、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周的时间备战比赛, 他决定每天至少下1盘棋,但每周不超过12盘. 则存在连续若干天,他恰好下了21盘棋. 证明: 令ai为到第i天下的总盘数, (ai+21=aj?) 1 a1 a2 a77 1112=132, 22 a1+21 a2+21 a77+21 132+21=153 总共有153种取值, 却有154个数 所
3、以存在ij使得 ai+21=aj .,鸽巢原理,推论1： 如果将n只鸽子放入n个鸽巢并且没有一个鸽巢是空的，那么每个鸽巢恰好包含一只鸽子。 推论2： 如果将n只鸽子放入n个鸽巢并且没有鸽巢被放入多于一只的鸽子，那么每个鸽巢里有一只鸽子。,中国剩余定理(简单形式),令m,n互素, 0 a m-1, 0 b n-1, 则方程组 x a mod m x b mod n 在0,mn内有唯一解. 证明: 下面的n个数(模m都是a) a, m+a, 2m+a, , (n-1)m+a, 模n的余数两两不同.,中国剩余定理(完全形式),令m1,mr两两互素, a1,ar为整数, 则同余方程组 x ai mod
4、 mi, i=1,r 模M(=m1m2mr)有唯一解,其中Mi=M/mi , yi Mi 1 mod mi. 例: (3,5,7)-(35,2), (21, 1), (15, 1) x = 70a1 + 21a2 + 15a3 mod 105,射雕英雄传中的问题,黄蓉给瑛姑出题: 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何.,答案: 三人同行七十稀, 五树梅花廿一支, 七子团圆正半月, 除百零五便得知.,同余方程组 x 2 mod 3, x 3 mod 5, x 2 mod 7 的解是 x = 702 + 213 + 152 mod 105 韩信点兵, 孙子算经
5、, 数书九章(秦九韶),补充: 不互素的情况,定理:设m,n是正整数, 0am, 0bn, 则方程组 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)内有唯一解: x a + c m (b-a)/d mod M. 参考多元一次同余方程组的解法.,加强形式,条件,鸽巢n个, 鸽子m1+m2+mn-n+1只, 其中 m1,m2,mn, n都是正整数,结论,鸽巢1鸽子数 m1, 或,鸽巢2鸽子数 m2, 或,鸽巢n鸽子数 mn, 至少有一个成立.,证明:否则, 总鸽子
6、数(m1-1)+(m2-1)+(mn-1) 与总鸽子数为m1+m2+mn-n+1矛盾.,Erds-Szekeres定理,定理: 在由n2+1个实数构成的序列中, 必然 含有长为n+1的单调(增或减)子序列. 证明:设序列为 a1, a2, , an2+1, 令mk是从ak开始的最长单调增子序列的长度. 若没有长于n+1的单增序列,则m1,mn2+11,n 由加强鸽巢原理, 存在k1k2kn+1使得,若ak1 ak2则必有mk1 mk2,于是:,ak 5 4 6 3 4 2 3 1 9 2 mk 3 3 2 3 2 3 2 2 1 1,Ramsey问题,命题: 6人中或者至少存在3人互相认识,
7、或者至少存在3人互相不认识. 特点: 对所有具体互相认识情况(215)都成立. 该Ramsey问题等价于: 六个顶点的完全图的边, 用红,蓝二色任意着色, 则至少存在一红色边三角形, 或一蓝色边三角形.,完全图, 条边,图示证明,从6人任取一人A.,A,5个人的反例,K6 K3, K3, (K5 K3, K3),Ramsey数与Ramsey定理,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,
8、b2, p KpKa, Kb. 即 r(a,b) ,Ramsey定理的证明,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, Kb AKnow有Ka或Kb.,Ramsey数表,a,b,Ramsey定理的推广,Ramsey定理: n1,n2,nk2, p KpKn1, Kn2, Knk. 例: K17K3, K3, K3. 作业: 第2章 ex1, ex5, ex8, ex15, ex20.,作业,第二章 P25： ex1, ex5, ex8, ex15, ex20. 编程题见网络教室。,