第二节 鸽巢原理的加强形式.ppt

1.2鸽巢原理的加强形式,组合数学Chapter1,定理1设都是正整数,如果把个物品放入n个盒子,那么或者第1个盒子至少包含q1个物品，或者第2个盒子至少包含q2个物品,或者第n个盒子至少包含qn个物品.,证明若对所有的,第i个盒子至多只有个物品,则n个盒子中至多有,个物品，,故定理成立.,这与我们现有个物品,矛盾.,显然为结论成立的最小数,把这个数记为,令,则定理变成了鸽巢原理的简单形式.,令,则得到如下推论.,推论1若将个物品放入n个盒子中,则至少有一个盒子中有r个物品.,推论2设为个整数,且有,则在中至少存在一个.,证明因为，即有,所以,推论3若将m个物品放入n个盒子中,则至少有一个盒子中有不少于个物品.其中是不小于的最小整数.,证明（反证）若每个盒中物品个数皆小于，则n个盒子中所放入物品总数,产生矛盾，所以结论成立.,例1考试采用百分制，要使得必有10人同分,考生至少要多少人？,解这个问题相当于求把多少人放入101个盒子,必有10人同盒.所以,由推论1,当考生至少为,人时,必有10人同分.,证明使大小两盘中心重合，固定大盘，转动小盘,则有200个不同的位置使小盘上的每个小扇形含在大盘上的小扇形中.,例2设有大小两个圆盘,每个都划分成大小相等的200个小扇形,在大盘上任选100个小扇形漆成黑色,其余的100个漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色.现将大小两只圆盘的中心重合,转动小盘使小盘上的每个小扇形含在大盘上的小扇形之内.证明:有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色.,设mi(i=1,2,3,200)表示在第i个位置时大、小扇形同色的个数,由于大盘上的200个小扇形中有100个漆成黑色,100个漆成白色,所以小盘上的每个小扇形无论漆成黑色或白色,在200个可能的重合位置上恰好有100次与大盘上的小扇形同色,所以,小盘上200个小扇形在200个重合的位置上与大盘上的小扇形同色的个数为200100=20000个,所以,即有,即结论成立.,例3任意个实数组成的序列中,必有一个长为n+1的递增子序列,或必有一个长为n+1的递减子序列.,证明令表示从开始的最长递增子序列的长度.,若存在,则存在长为n+1的递增子序列,结论成立.,若对任意的,有,这相当于把个物品放入n个盒子1,2,n中，由鸽巢原理知,必有一盒子里面至少有n+1个物品,即存在,使得,则对应于这些下标的实数序列必满足,即存在长为n+1的递减子序列.,否则,若有某个使得,例3任意个实数组成的序列中,必有一个长为n+1的递增子序列,或必有一个长为n+1的递减子序列.,那么由从开始的最长递增子序列的长度,必大于从开始的最长递增子序列的长度,即有,因此结论成立.,例4把1至10这十数字随机的排成一个圆圈，证明必有一个三相邻数字之和大于等于17,证明把1至10这十个数字随机排成一个圆圈,从中任取三个相邻数字的方法有10种,设这10种三个相邻数字之和分别为m1,m2,m10,则有,m1+m2+m10=3(1+2+10)=,由推论2,必存在mi(0i10),使得mi17，即问题得证,例5边长为1的正方形中，任意放入9个点，求证这9个点中任取3个点组成的三角形中，至少有一个的面积不超过1/8.,解：将边长为1的正方形等分成边长为1/2的四个小正方形，视这四个正方形为鸽巢，9个点任意放入这四个正方形中，由鸽巢原理必有三点落入同一个正方形内.现特别取出这个正方形来加以讨论.,图1,把落在这个正方形中的三点记为D、E、F.如图1，通过这三点中的任意一点（如E）作正方形边平行线,SDEFSDEGSEFG,所以，结论成立。,例6(1995年全国高中数学联赛试题)将平面上每个点以红、蓝两色之一着色，证明：存在这样的两个相似三角形，它们的相似比为2013，并且每一个三角形的三个顶点同色。,证明：如图，作两个半径分别为1和2013的同心圆，在内圆上任取9个点，必有5点同色，不妨设为A1,A2,A3,A4,A5。如图所示，连半径0Ai交大圆于Bi（i=1,2,3,4,5），对B1，B2，B3，B4，B5必有3点同色,不妨设为B1,B2,B3，则B1B2B3与A1A2A3为三顶点同色的相似三角形，相似比等于对应的大圆弦长与小圆弦长之比，即为2013，所以结论成立.,例7将1到16这16个正整数任意分成三个部分,其中必有一部分中的一个元素是该部分某两个元素之差(三个元素不一定互不相同).,证明用反证法.假设结论不成立.,(1)将1到16这16个正整数任意分成三个部分P1,P2,P3,由鸽巢原理,其中必有一部分至少有6个元素,不妨设P1含有6个元素,为,显然,1bi16(i=1,2,3,4,5),根据假设b1,b2,b3,b4,b5无一属于P1,所以它们属于P2或P3,且P2或P3有一部分至少含有它们中三个元素.,(2)不妨设b1,b2,b3,b4,b5至少有3个元素属于P2,设为,下面再证明d1,d2也不属于P1.,且d1,d2不属于P2.,所以,d1,d2均不属于P1.因此,d1,d2元素属于P3.,(3)根据假设，在P3中不存在一元素是另两个元素之差