资源预览内容
第1页 / 共60页
第2页 / 共60页
第3页 / 共60页
第4页 / 共60页
第5页 / 共60页
第6页 / 共60页
第7页 / 共60页
第8页 / 共60页
第9页 / 共60页
第10页 / 共60页
亲,该文档总共60页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
组合数学初步,第十章 鸽笼原理 第十一章 排列与组合 第十二章 生成函数与递推关系,组合数学/组合论,组合数学/组合论:应用数学学科,对于算法研究变得日益重要。,计算机算法分类,数值计算:方程组求解、积分计算 非数值计算:搜索、排序、组合优化(主要是组合算法) 设计和分析组合算法的基础是组合数学,组合数学的四个方面,判定所提出问题的解是否存在的存在性问题 确定有解问题其不同解的个数的计数问题 对可解问题去把解构造出来的构造性算法 从问题的多种构造性算法中择优改进的优化问题。,讲授内容,组合数学中的存在性问题和计数问题,组合数学经典教材,组合数学(第3版),卢开澄,卢华明著,清华大学出版社。(有课件,可拷贝) 组合数学(英文版.第3版),(美)Richard A. Brualdi,译者:冯舜玺、罗平、裴伟东。校:卢开澄、冯舜玺。Prentice Hall,机械工业出版社。,组合数学,一、组合数学的历史和发展原因 二、组合数学两类一般性问题 三、组合学另外两种问题 四、组合数学的定义,一、组合数学的历史和发展原因,1. 组合数学的历史渊源扎根于数学娱乐和游戏之中。 2. 组合数学的历史和发展原因 1) 计算机的发展, 程序的基础往往是求解问题的组合学算法. 2) 组合数学对于过去很少与数学正式接触的学科的适用性,二、组合数学两类一般性问题,组合数学涉及将一个集合的物体排列成满足一些指定规则的格式。 1.排列的存在性: 排列在什么样的(充分和必要)条件下能够实现? 2.排列的计数和分类: 如果一个排列是可能的, 那么就会存在多种方法实现它. 此时, 就可以计数并将它们分类.,组合学问题形式: 能否排列? 存在一个吗? 能用多少方法? 计算的数目.,三、组合学另外两种问题,研究一个已知的排列 构造一个最优的排列,四、组合数学的定义,组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。,第十章 鸽笼原理,10.1 鸽笼原理的简单形式 10.2 鸽笼原理的加强形式,10.1 鸽笼原理的简单形式,1, 问题的引入 实例: 某次会议有n位代表参加,每位代表认识其他代表中某些人,则至少有两个人认识的人数是一样的。,10.1 鸽笼原理的简单形式,2, 鸽笼 定理10.1 n+1只鸽子飞回n个笼子,至少有一个鸽笼含有不少于2只鸽子。 证明方法:反证,例 367人中至少有人的生日相同。 例 10双手套中任取11只,其中至少有两只是完整配对的。,3, 鸽笼的扩展(抽象) 定理10.2 s(s1)个元素分成t个组,那么必存在一个组至少含有s/t(这里 为“上整数”记号)个元素。 证明方法:反证法。,证明:若每个组至多含有(s/t-1)元素,则t个组共有元素t(s/t-1),因为s/t s/t(s/t)+1,所以有t(s/t-1)s,这就导致矛盾。所以必存在一个组至少含有s/t个元素。,4, 实例 1)例10.1 设f是D到R的函数,这里|D|R|,令i= |D|/ |R|,则D中存在i个元素d1, d2, , di,使得f(d1)=f(d2)=f(di)。 证明方法:此问题相当于定理10.2,把|D|个元素分到|R|个组中去。,证明:在这|R|个组中有一个组至少含有i= |D|/ |R|个元素。在同一组中对应的函数值是相等的。所以在D中至少存在i个元素d1, d2, , di,使得f(d1)=f(d2)= f(di) 。,2)例10.2 在n+1个小于或等于2n的互不相等的正整数中,必存在两个互质的数。,证明:把1, 2, , 2n这2n个数分成n个组:1, 2, 3, 4, , 2n-1, 2n;则问题归结为从n个组中取n+1个数,由定理10.1知,至少有2个数取自同一组,由于这两个数是相邻的正整数,故互质。,3)例10.3 1, 2, , 2n中任取n+1个互不相同的数中,必存在两个数,其中一个数是另一个数的倍数。,证明:因为任何正整数n可以表示成n=2ab(这里a=0, 1, 2,,且b为奇数)。设取出的n+1个数为k1, k2, , kn+1,则ki=2aibi。 由于b1, b2, , bn+1是奇数,共有n+1个,而在1, 2, , 2n中只有n个不同的奇数,所以必存在i, j,使得bi=bj。 不妨设kikj,则有ki / kj =2ai-aj为正整数,因此ki是kj的倍数。,4)例10.4 一个国际象棋选手为参加国际比赛,突击训练77天,要求每天至少下一盘棋,每周至多下12盘棋。 证明:无论如何安排总可以使他在这77天里有连续几天共下21盘棋。,证明:用ai表示从第1天到第i天下棋的总盘数(i=1, 2, , 77)。由于规定每天至少下一盘棋,每周至多下12盘棋,所以 1a1a2a7712(77/7)=132 构造新序列: a1+21, a2+21, a77+21 则有这样的序列: a1, a2, a77, a1+21, a2+21, a77+21 共有154个,但每个不超过153,所以必存在i, j (ji),使得ai=aj+21,则有ai-aj=21,即在j+1, j+2, , j+(i-j)的连续i-j天中下了21盘棋。,学生思考题: 证明对于k=1, 2, , 21存在连续若干天,在此期间国际象棋大师将恰好下完k局棋(k=21为上题处理的情况)。能否推断:存在连续若干天,在此期间国际象棋大师将恰好下完22局棋?,5) 中国余数定理 令m和n为二互素的正整数,并令a和b为两整数,且0am-1以及0bn-1。于是,存在一个正整数x,使得x除以m的余数为a,并且x除以n的余数为b;即x可以写成x=pm+a的同时又可以写成x=qn+b的形式,这里,p和q是两个整数。,证明:考虑n个整数a, m+a, 2m+a, , (n-1)m+a,这些整数中的每一个除以m都余a。 假设其中的两个除以n有相同的余数r。令这两个数为im+a和jm+a,其中0ijn-1。因此,存在两整数qi和qj,使得im+a=qin+r及jm+a=qjn+r。则有(j-i)m=(qj-qi)n。 所以n是(j-i)m的一个因子。由于n与m没有除1以外的公因子,因此n是j-i的一个因子,然而, 0ijn-1意味着0j-in-1,也就是说n不可能是j-i的因子。该矛盾产生于我们的假设: a, m+a, 2m+a, , (n-1)m+a中有两个除以n有相同的余数。因此,这n个数中每个除以n有不同的余数。,根据鸽巢原理: n个整数0, 1, 2, , n-1中每一个作为余数都要出现;特别是数b也是如此。令p为整数,满足0pn-1,且使数x=pm+a除以n余数为b。则对于某个适当的q,x=qn+b。因此,x=pm+a且x=qn+b,从而x具有所要求的性质。,学生思考题: 举例证明:当m和n不互素时,中国余数定理的结论未必成立。,解题要点:确定哪些对象为“鸽子”,哪些对象为“鸽笼” 练习,10.2 鸽笼原理的加强形式,1 定理10.3 设q1, q2, , qn都是正整数,若把q1+q2+qn-n+1个元素分成n个组,则必然发生:或者第一组中至少有q1个元素;或者第二组中至少有q2个元素;或者第n组中至少有qn个元素。 证明方法:反证法。,证明:若结论不成立,则对于i=1, 2, , n,第i组中至多有qi-1个元素,则n个组的元素个数的总和不超过q1+q2+ +qn-n个,这就导致矛盾。,2 推论 1)推论10.1 若将n(r-1)+1个元素分成n个组,则至少有一个组含有r个或更多的元素(这里n、r皆为正整数)。,2)推论10.2 若n个正整数m1, m2, ,mn的平均数满足不等式: 则m1, m2, ,mn中至少有一个不小于r。,3 例题 1)例10.5 两个同心圆盘的每个圆周均分为200段, 从大盘上任选100段涂上红色, 其余涂上蓝色, 而在小盘的每个小段上任意涂上红色或蓝色. 证明: 在旋转小盘时可以找到某个位置,使得小盘上至少有100个小段与大盘上对应段颜色相同.,证明:固定大盘,对小盘上任一段,在它旋转过程中,可有200个可能旋转位置,与大盘上的所有段构成200种颜色组合,其中同色的有100组,因小盘上共有200段,故小盘上的所有段在旋转一周后,与大盘对应段构成的同色组共有20000个。而旋转一周后,共可转去200段,设i段的同色组为mi(I=1, 2, , 200),而总的同色组就是m1 + m2 + m200 =20000,因此200个整数m1, m2 , m200的平均数满足不等式:20000/200=100100-1,所以,由推论10.2,某个位置,使得小盘上至少有100个小段与大盘上对应段颜色相同。,习题解析,鸽笼原理 用于判断是否存在满足鸽笼原理条件的对象,若鸽笼原理的条件成立,则存在满足条件的对象。 运用鸽笼原理时必须确定哪些对象相当于鸽子,而哪些对象相当于鸽笼。,鸽笼原理形式,设函数f是从有限集X到有限集Y的映射,且|X|Y|,则必存在x1, x2X,x1x2,满足f(x1)=f(x2)。,鸽笼原理形式例题 1. 20个处理器连成网络,证明至少有两个处理器与相同数目的处理器直接相连。,解题分析: 20个处理器编号分别为1, 2, 3, , 20,(定义域X=1, 2, 3, 20);ai表示与第i个处理器直接相连的处理器的数目(f(X))。 证明:对于某两个i, j,ij,ai=aj。,解: X=1, 2, 3, 20, Y=0, 1, 2, 19; 0和19不能同时作为函数值存在,即不存在两个i, j,ij,ai=0,aj=19。所以|X|=20, |Y|20。 根据鸽笼原理形式1,命题成立。,2. 列表中有80件物品,每个物品的属性为“可用”或“不可用”,共有45个“可用”的物品,证明至少有两件可用物品的编号差恰为9。,解题分析: ai表示第i个可用物品的编号; 证明:对于某两个i, j,ij,ai-aj=9。,证明: 考虑下列两组数字: a1, a2, , a45 a1+9, a2+9, , a45+9 这两组共90个数字,取值范围为1-89。 因为第一组数字两两不同,第二组数字也是两两不同,所以必存在两个i, j,ij,ai-aj=9。,习题解析,10.1 在边长为2的正三角形中任意放置5个点, 证明至少有两个点之间的距离不大于1. 解题要点:确定鸽子和鸽笼,/*将三角形分成边长为1的4个正三角形*/,10.4 将一个圆盘分为36段,将1, 2, , 36这36个数字任意标在每一段上,使得每一段恰有一个数字。证明:必存在相继的3段,它们的数字之和不小于56。,证明:设36个小扇形分别为a1, a2, , a36。ai中放的数为xi,i=1, 2, , 36。1 xi 36,且当时ij,xixj。将36个小扇形合并成12个大扇形:A1=a1a2a3, A2=a4a5a6, , A12=a34a35a36,并设Aj中3数之和为yj,j=1, 2, , 12。则,将1837个元素分配给12个扇形,由鸽巢原理,至少存在一个扇形,分配给它的元素个数至少是 1837 / 12=56。 所以命题成立。,例 设 a1, a2, a3为任意个整数,b1 ,b2, b3为a1, a2, a3的任一排列,则 a1-b1, a2-b2, a3- b3中至少有一个是偶数,证明: 由鸽巢原理, a1, a2, a3为任意个整数,设这个数被除的余数为 xxy,于是b1,b2, b3 中被除的余数有个x,一个y
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号