组合数学第二章鸽巢原理.ppt
《组合数学第二章鸽巢原理.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 韩信点兵, 孙子算经
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 第二 章鸽巢 原理
链接地址:https://www.31doc.com/p-3393803.html