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

《组合数学第二章鸽巢原理.ppt》由会员分享，可在线阅读，更多相关《组合数学第二章鸽巢原理.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学第二章鸽巢原理 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望鸽巢原理鸽巢原理定理定理: 若有若有n个鸽巢个鸽巢, n+1只鸽子只鸽子, 则则至少至少有一个鸽巢里有一个鸽巢里至少至少有两只鸽子有两只鸽子.注意这里的任意性注意这里的任意性.例例1. 一年一年365天天, 今有今有366个人个人, 则其中至少有两个人生日相同则其中至少有两个人生日相同.例例2. 抽屉里有抽屉里有10双手套双手套, 从中取从中取11只出来只出来, 其中至少有两只是完整配对的其中

2、至少有两只是完整配对的.应用举例应用举例例例. 在边长为在边长为1的正方形内任取的正方形内任取5点点,则则 其中至少有其中至少有2点点的距离不超过的距离不超过2/2例例. 设设a1,a2,am是正整数序列是正整数序列, 则至少存在则至少存在 整数整数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

3、).应用应用:国际象棋大师国际象棋大师一位国际象棋大师有一位国际象棋大师有11周的时间备战比赛周的时间备战比赛,他决定他决定每天至少下每天至少下1盘棋盘棋,但但每周不超过每周不超过12盘盘.则存在连续若干天则存在连续若干天,他恰好下了他恰好下了21盘棋盘棋.证明证明: 令令ai为到第为到第i天下的总盘数天下的总盘数, (ai+21=aj?)1 a1 a2 a77 11 12=132,22 a1+21 a2+21 a77+21 132+21=153 总共有总共有153种取值种取值, 却有却有154个数个数 所以存在所以存在ij使得使得 ai+21=aj .鸽巢原理鸽巢原理推论推论1： 如果将如果

4、将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

5、, , (n-1)m+a, 模模n的余数两两不同的余数两两不同.中国剩余定理中国剩余定理(完全形式完全形式)令令m1,mr两两互素两两互素, a1,ar为整数为整数, 则同余方程组则同余方程组 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 射雕英雄传中的问题射雕英雄传中的问题黄蓉给瑛姑出题黄蓉给瑛姑出题:今有物不知其数今有物不知其数,三三数之剩

6、二三三数之剩二, 五五数之剩三五五数之剩三,七七数之剩二七七数之剩二, 问物几何问物几何.答案答案:三人同行七十稀三人同行七十稀,五树梅花廿一支五树梅花廿一支,七子团圆正半月七子团圆正半月,除百零五便得知除百零五便得知.同余方程组同余方程组 x 2 mod 3, x 3 mod 5, x 2 mod 7的解是的解是 x = 702 + 213 + 152 mod 105韩信点兵韩信点兵, 孙子算经孙子算经, 数书九章数书九章(秦九韶秦九韶)补充补充: 不互素的情况不互素的情况定理定理:设设m,n是正整数是正整数, 0 am, 0 bn, 则方程组则方程组 x a mod m, x b mod

7、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,至少有一个成立至少有一个成立.证明证明:否则否则, 总鸽子

8、数总鸽子数 (m1-1)+(m2-1)+(mn-1) 与总鸽子数为与总鸽子数为m1+m2+mn-n+1矛盾矛盾.Erds-Szekeres定理定理121nkkkmmm定理定理: 在由在由n2+1个实数构成的序列中个实数构成的序列中, 必然必然 含有长为含有长为n+1的单调的单调(增或减增或减)子序列子序列.证明证明:设序列为设序列为 a1, a2, , an2+1,令令mk是从是从ak开始的最长单调增子序列的长度开始的最长单调增子序列的长度.若没有长于若没有长于n+1的单增序列的单增序列,则则m1,mn2+1 1,n由加强鸽巢原理由加强鸽巢原理, 存在存在k1k2 mk2,于是于是:121nk

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

10、取一人A.A和和A互相认识互相认识的人的集合的人的集合GG和和A互不认识互不认识的人的集合的人的集合HH5个人的反例个人的反例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,b 2, p KpKa, Kb. 即即 r(a,b) Ramsey定理的证明定理的证明r(

11、a,b)=r(b,a), r(a,2)=r(2,a)=a性质性质: 当当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数表数表345369144918255142543,4961835,4172349,6182855,84abRamsey定理的推广定理的推广Ramsey定理定理: n1,n2,nk 2, p KpKn1, Kn2, Knk.例例: K17K3, K3, K3.作业作业: 第第2章章 ex1, ex5, ex8, ex15, ex20.作业作业第二章第二章 P25：ex1, ex5, ex8, ex15, ex20.编程题见网络教室。编程题见网络教室。