组合数学第二章.pptVIP

组合数学第二章 鸽巢原理 鸽巢原理 应用举例 应用:国际象棋大师 中国剩余定理(简单形式) 中国剩余定理(完全形式)陈述 射雕英雄传中的问题 中国剩余定理(完全形式)证明 补充: 不互素的情况 加强形式 Erd?s-Szekeres定理 Ramsey问题 图示证明 5个人的反例 Ramsey数与Ramsey定理 Ramsey定理的证明 Ramsey数表 Ramsey定理的推广 颜色重合扇形数目 Paul Erd?s(埃尔德什 )简介 一些Erd?s问题 作业 最大公约数 举例: 扩展的Euclid方法 主要内容： 1. 鸽巢原理及其应用 2. 中国剩余定理 3. 加强形式的鸽巢原理 4. Ramsey定理 定理: 若有n个鸽巢, n+1只鸽子, 则至少有一个鸽巢里至少有两只鸽子. 注意这里的任意性. 例1. 一年365天, 今有366个人, 则其中至少有两个人生日相同. 例2. 抽屉里有10双手套, 从中取11只出来, 其中至少有两只是完整配对的. 关键: 选鸽巢和鸽子 例. 在边长为1的正方形内任取5点,则 其中至少有2点的距离不超过 Halloween treats 例. 设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). 一位国际象棋大师有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 . 令m,n互素, 0 ? a ? m-1, 0 ? b ?n-1, 则方程组 x ? a mod m x ? b mod n 在[0,mn)内有唯一解. 举例. x ? 1 mod 2, x ? 2 mod 3 解: x ? 5 mod 6 证明: 下面的n个数(模m都是a) a, m+a, 2m+a, …, (n-1)m+a, 模n的余数两两不同. 令m1,…,mr两两互素, a1,…,ar为整数, 则同余方程组 x ? ai mod mi, i=1,…,r 模M(=m1m2…mr)有唯一解 其中Mi=M/mi , yi Mi ? 1 mod mi. 例: (3,5,7)--(Mi, yi): (35,2), (21, 1), (15, 1) x = 70a1 + 21a2 + 15a3 mod 105 黄蓉给瑛姑出题: 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何. 答案: 三人同行七十稀, 五树梅花廿一支, 七子团圆正半月, 除百零五便得知. 同余方程组 x ? a1 mod 3, x ? a2 mod 5, x ? a3 mod 7 的解是 x = 70a1 + 21a2 + 15a3 mod 105 韩信点兵(-2), 孙子算经(4), 数书九章(秦九韶13) 令m1,…,mr两两互素, a1,…,ar为整数, 则同余方程组 x ? ai mod mi, i=1,…,r 模M(=m1m2…mr)有唯一解 其中Mi=M/mi , yi Mi ? 1 mod mi. 定理: 存在整数s,t使得 gcd(m,n) = ms+nt. 定理:设m,n是正整数, 0?am, 0?bn, 则方程组 x ? a mod m, x ? b mod n (*) 有解当且仅当gcd(m,n)|(