《第十章鸽笼原理.ppt》由会员分享，可在线阅读，更多相关《第十章鸽笼原理.ppt（12页珍藏版）》请在三一文库上搜索。
1、第十章 鸽笼原理,组合数学或组合论是一门历史悠久的应用数学学科。 随着计算机的普及和发展，对计算机算法的研究变得日益重要。 计算机算法可分为两大类: 解决数值计算(如方程组求解、积分计算等)的计算方法， 解决非数值计算(如搜索、排序、组合优化等)的非数值计算方法(主要是组合算法)。 设计和分析组合算法的基础就是组合数学。,组合数学一般可分为四个方面: 判定所提出问题的解是否存在的存在性问题、 确定有解问题其不同解的个数的计数问题、 对可解问题去把解构造出来的构造性算法 从问题的多种构造性算法中择优改进的优化问题。 组合数学的内容是很丰富的，只涉及组合数学中的存在性问题和计数问题，为以后学习和研
2、究计算机算法的设计和分析打下基础。 鸽笼原理是解决组合数学中一些存在性问题的基本工具。 最早是由狄利克雷(Dirichlet)提出的，又称为抽屉原理、鞋盒原理。,10.1鸽笼原理的简单形式,定理10.1：n+1只鸽子飞回n个笼子，至少有一个鸽笼含有不少于2只的鸽子。 这个定理的证明是非常简单的 抽去具体的“鸽子”、“鸽笼”等物理属性 从数学上看，就是把s个元素分成t个组，当不能均匀分放时，必有一个组其元素个数要超出“平均数”。,定理10.2：s(s1)个元素分成t个组，那么必存在一个组至少含有s/t(这里 为“上整数”记号)个元素。 证明：用反证法证明。 若每个组至多含有(s/t-1)个元素，
3、则t个组最多有元素t*(s/t-1)， 因为s/ts/t(s/t)+1， 所以有t*(s/t-1)t*(s/t)+1)-1)s， 导致矛盾。故必存在一个组至少含有s/t个元素。 任意13个人中，至少有二人生日在同一个月; 任意70个人中，至少有s/t=70/12=6人生日同月;,例：在n+1个小于或等于2n的互不相等的正整数中，必存在两个互质的数。 证明：s=n+1,关键是如何构造鸽笼。 注意到这样的事实：任何相邻两数互质。 因此可以考虑把1,2,2n这2n个数分成n个组: 1,2,3,4,2n-1,2n， 例：在1,2,2n中任取n+1个互不相同的数中，必存在两个数，其中一个数是另一个数的倍
4、数。 证明：因为任何正整数n都可表示成n=2ab(这里a=0,1,2,，且b为奇数)。 设取出的n+1个数为k1,k2,kn+1，则ki=2aibi，,设a1,a2,an为整数，则存在k和l(0kln),使得ak+1+ak+2+al被n整除。 证明:构造Si=a1+a2+ai, 则有S1,S2,Sn, 余数有n个,但为0则表示被n整除,因此考虑分开讨论,例：一个国际象棋选手为参加国际比赛，突击练习77天，要求每天至少下一盘棋，每周至多下12盘棋。证明:无论如何安排总可使他在这77天里有连续几天共下了21盘棋。 证明：用ai表示从第1天到第i天下棋的总盘数(i=1,2,77)。 由于规定每天至少
5、下一盘棋，且每周至多下12盘棋，故有：1a1a2a7712(77/7) =132 现构造一个新的序列:a1+21a2+21a77+21。 现有这样的序列: a1,a77,a1+21,a77+21， 如果要求证明无论如何安排总可使他在这77天里有连续几天共下了22盘棋,怎样做?,10.2鸽笼原理的加强形式,定理10.3:设q1,q2,qn都是正整数，若把q1+q2+qn-n+1个元素分成n个组，则必然发生: 或者第一组中至少有q1个元素；或者第二组中至少有q2个元素；或者第n组中至少有qn个元素。 证明:用反证法证明。,推论10.1:若将n(r-1)+1个元素分成n个组，则至少有一个组中含有r个
6、或者更多的元素(这里n、r皆为正整数)。 推论10.2:若n个正整数m1,m2,mn的平均数满足不等式: (m1+m2+mn)/nr-1，则m1,m2,mn中至少有一个不小于r。,例10.5：两个同心圆盘的每个圆周均分为 200段，从大盘上任选100段涂上红色，其余涂上蓝色，而在小盘的每个小段上任意涂上红色或蓝色。证明在旋转小盘时可以找到某个位置，使得小盘上至少有100个小段与大盘上对应段颜色相同。 证明：固定大盘，对小盘上任一段，每转一格，因大盘不动，就与大盘某段组成一种颜色，旋转一周200格，就与大盘上的所有段构成200种颜色组合， 其中同色的有100组。 小盘上共有200段，故小盘上的所有段在旋转一周后，与大盘对应段构成的同色组共有 20000个。 设转i格的同色组为mi(这里i=1,2,200)，,例10.6：设a1,a2,an2+1，是n2+1个不同实数的序列，则必可从此序列中选出n+1个数的子序列，使这子序列为递增序列或递减序列。 证明:若存在长度为n+1的递增序列，结论成立。 若不存在长度为n+1的递增序列，目标证明存在长度为n+1的递减序列。 首先要找到一个长度为n+1的子序列，然后证明是递减序列,作业: P221 1,3,4,5,7 课件地址： ftp:/10.11.2.154 集合与图论,