十章鸽笼原理.ppt
十章鸽笼原理 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望组合数学一般可分为四个方面组合数学一般可分为四个方面:判定所提出问题的解是否存在的存在性问题、判定所提出问题的解是否存在的存在性问题、确定有解问题其不同解的个数的计数问题、确定有解问题其不同解的个数的计数问题、对可解问题去把解构造出来的构造性算法对可解问题去把解构造出来的构造性算法从从问问题题的的多多种种构构造造性性算算法法中中择择优优改改进进的的优优化化问问题。题。组组合合数数学学的的内内容容是是很很丰丰富富的的，只只涉涉及及组组合合数数学学中中的的存存在在性性问问题题和和计计数数问问题题，为为以以后后学学习习和和研研究计算机算法的设计和分析打下基础。究计算机算法的设计和分析打下基础。鸽鸽笼笼原原理理是是解解决决组组合合数数学学中中一一些些存存在在性性问问题题的的基本工具。基本工具。最最早早是是由由狄狄利利克克雷雷(Dirichlet)提提出出的的，又又称称为抽屉原理、鞋盒原理。为抽屉原理、鞋盒原理。10.1鸽笼原理的简单形式鸽笼原理的简单形式定定理理10.1：n+1只只鸽鸽子子飞飞回回n个个笼笼子子，至至少有一个鸽笼含有不少于少有一个鸽笼含有不少于2只的鸽子。只的鸽子。这个定理的证明是非常简单的这个定理的证明是非常简单的抽抽去去具具体体的的“鸽鸽子子”、“鸽鸽笼笼”等等物物理理属性属性从从数数学学上上看看，就就是是把把s个个元元素素分分成成t个个组组，当当不不能能均均匀匀分分放放时时，必必有有一一个个组组其其元元素素个数要超出个数要超出“平均数平均数”。定定理理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)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个互不相同的数中，个互不相同的数中，必存在两个数，其中一个数是另一个数的倍数。必存在两个数，其中一个数是另一个数的倍数。证明：因为任何正整数证明：因为任何正整数n都可表示成都可表示成n=2ab(这这里里a=0,1,2,，且，且b为奇数为奇数)。设取出的设取出的n+1个数为个数为k1,k2,kn+1，则，则ki=2aibi，设设a1,a2,an为为整整数数，则则存存在在k和和l(0 kl n),使得使得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)。由由于于规规定定每每天天至至少少下下一一盘盘棋棋，且且每每周周至至多多下下12盘盘棋，故有：棋，故有：1a1a2a7712(77/7)=132现构造一个新的序列现构造一个新的序列:a1+21a2+21r-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集合与图论集合与图论
