《组合数学第二章鸽巢原理.ppt》由会员分享，可在线阅读，更多相关《组合数学第二章鸽巢原理.ppt（19页珍藏版）》请在三一文库上搜索。
1、组合数学第二章 鸽巢原理,主要内容： 1. 鸽巢原理及其应用 2. 中国剩余定理 3. 加强形式的鸽巢原理 4. Ramsey定理,拍钙桶纽柠捧玫莲尉好扦痉橱封类俏牙接简谍乍郧府疹傍精车夹胞碱嘴神组合数学第二章鸽巢原理组合数学第二章鸽巢原理,鸽巢原理,定理: 若有n个鸽巢, n+1只鸽子, 则至少有一个鸽巢里至少有两只鸽子. 注意这里的任意性. 例1. 一年365天, 今有366个人, 则其中至少有两个人生日相同. 例2. 抽屉里有10双手套, 从中取11只出来, 其中至少有两只是完整配对的.,历颅矗县压烈宽恿智吞母拒摔趣叔江斤码赶塞媚介诺亚讯夺媳寨穷哩犁摘组合数学第二章鸽巢原理组合数学第二章
2、鸽巢原理,应用举例,例. 在边长为1的正方形内任取5点,则 其中至少有2点的距离不超过,例. 设a1,a2,am是正整数序列, 则至少存在 整数k和l, 0kl 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 1112=132, 22 a1+21 a2+21 a77+21 132+21=153 总共有153种取值, 却有154个数 所以存在ij使得 ai+21=aj .,骏伯姻萧泛烈殆兵致宋纪扣帮穆凭癌璃卑踌知低疹响卡张亿蛋契适丹渴今组合数学第二章鸽巢原理组合数学第二章鸽巢原理,鸽巢原理,推论1： 如果将n只鸽子放入n个鸽巢并且没有一个鸽巢是空的，那么每个鸽巢恰好包含一只鸽子。 推论2： 如果将n只鸽
4、子放入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两两
5、互素, a1,ar为整数, 则同余方程组 x ai mod 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,愚送琢莫郝砷放岭掀辫肩墅蒜搀衅肆镐拾濒锤牢肃袍恕跨作跺董揍辖架简组合数学第二章鸽巢原理组合数学第二章鸽巢原理,射雕英雄传中的问题,黄蓉给瑛姑出题: 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何.,答案: 三人同行七十稀, 五树梅花廿一支, 七子团圆正半月, 除百零五便
6、得知.,同余方程组 x 2 mod 3, x 3 mod 5, x 2 mod 7 的解是 x = 702 + 213 + 152 mod 105 韩信点兵, 孙子算经, 数书九章(秦九韶),驶铺袒熙浑撅猖捆唉忙冷肺庞方踌臻奉肮驳华专四纠楚兼桓蹈蛮川员词邢组合数学第二章鸽巢原理组合数学第二章鸽巢原理,补充: 不互素的情况,定理:设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
7、-a)/d mod M. 参考多元一次同余方程组的解法.,赃栅丘硷踩希掇扎奋俗棚泣崎畴曼挣脾陪剥盼迂旱玻毗骑盾莆熄滁妙鸵开组合数学第二章鸽巢原理组合数学第二章鸽巢原理,加强形式,条件,鸽巢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矛盾.,付蒜务刘瞪拣涂知车湿陕幅试虎丧用慧旋从跪宁铂枫跑仓者簿锐辫贝粕憨组合数学第二章鸽巢原理组合数学第二章鸽巢原理,Erds-Sz
8、ekeres定理,定理: 在由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人互相
9、认识, 或者至少存在3人互相不认识. 特点: 对所有具体互相认识情况(215)都成立. 该Ramsey问题等价于: 六个顶点的完全图的边, 用红,蓝二色任意着色, 则至少存在一红色边三角形, 或一蓝色边三角形.,完全图, 条边,迄努狞籽阻禽户望综咋吹箭谤樟膜花听聘渡川破撕厅躯唉各么拙芍醋鞭冰组合数学第二章鸽巢原理组合数学第二章鸽巢原理,图示证明,从6人任取一人A.,A,动线钝稳嗓闯末酷目茁兼戳桑非唁面赚蕉邓孝讶乎匝后锻词跨鄙笔杯亮趋组合数学第二章鸽巢原理组合数学第二章鸽巢原理,5个人的反例,K6 K3, K3, (K5 K3, K3),肯彬豢馁凤娶铬投娥柏咯搭纺腰砖典帮解常拜翻挖邀榨周童蚌壕康
10、术略权组合数学第二章鸽巢原理组合数学第二章鸽巢原理,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,b2, p KpKa, Kb. 即 r(a,b) ,难战南兄乞免牛海峻剿心切椎蓉家谗炬未焙乱狠聚袒馅缉袱甲喘杖蓟拥海组合数学第二章鸽巢原理组合数学第二章鸽巢原理,Ramsey定理的证明,r(a,b)=r(b,a), r(a,2)=r(2,a)=a 性质: 当a,
11、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. 编程题见网络教室。,吕推摄钻贵宛晓黄蒸肿椽餐诱莎牡晓滑沂超疵砧壳笆吭承提诈幻汉魔诧剑组合数学第二章鸽巢原理组合数学第二章鸽巢原理,