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

1、1.2 鸽巢原理的加强形式,组合数学 Chapter 1,定理1 设 都是正整数, 如果把 个物品放入n个盒子, 那么或者第1个盒子至少包含q1个物品，或者第2个盒子至少包含q2个物品,或者第n个盒子至少包含qn个物品.,证明 若对所有的 ,第i个盒子至多只有 个物品, 则n个盒子中至多有,个物品，,故定理成立.,这与我们现有 个物品, 矛盾.,显然 为结论成立的最小数,把这个数记为,令 , 则定理变成了鸽巢原理的简单形式.,令 , 则得到如下推论.,推论1 若将 个物品放入n个盒子中,则至少有一个盒子中有r个物品.,推论2 设 为个整数, 且有,则在 中至少存在一个 .,证明因为 ，即有,所

2、以,推论3 若将m个物品放入n个盒子中, 则至少有一个盒 子中有不少于 个物品. 其中 是不小于 的最小整数.,证明（反证） 若每个盒中物品个数皆小于 ，则n个盒子中所放入物品总数,产生矛盾，所以结论成立.,例1 考试采用百分制，要使得必有10人同分, 考生至少要多少人？,解 这个问题相当于求把多少人放入101个盒子, 必有10人同盒.所以, 由推论1, 当考生至少为,人时,必有10人同分.,证明 使大小两盘中心重合，固定大盘，转动小盘,则有200个不同的位置使小盘上的每个小扇形含在大盘上的小扇形中.,例2 设有大小两个圆盘,每个都划分成大小相等的200个小扇形,在大盘上任选100个小扇形漆成

3、黑色,其余的100个漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色.现将大小两只圆盘的中心重合,转动小盘使小盘上的每个小扇形含在大盘上的小扇形之内.证明:有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色.,设mi (i=1,2,3,200)表示在第i个位置时大、小扇形同色的个数,由于大盘上的200个小扇形中有100个漆成黑色,100个漆成白色,所以小盘上的每个小扇形无论漆成黑色或白色,在200个可能的重合位置上恰好有100次与大盘上的小扇形同色,所以,小盘上200个小扇形在200个重合的位置上与大盘上的小扇形同色的个数为200100=20000个,所以,即有,即结论成立.

4、,例3 任意 个实数 组成的序列中, 必有一个长为n+1的递增子序列, 或必有一个长为n+1的递减子序列.,证明 令 表示从 开始的最长递增子序列的长度.,若存在 ,则存在长为n+1的递增子序列, 结论成立.,若对任意的 , 有,这相当于把 个物品 放入n个盒子1,2,n 中，由鸽巢原理知, 必有一盒子里面至少有n+1个物品, 即存在,使得,则对应于这些下标的实数序列必满足,即存在长为n+1的递减子序列.,否则,若有某个 使得,例3 任意 个实数 组成的序列中, 必有一个长为n+1的递增子序列, 或必有一个长为n+1的递减子序列.,那么由从 开始的最长递增子序列的长度,必大于从 开始的最长递增

5、子序列的长度,即有,因此结论成立.,例4 把1至10这十数字随机的排成一个圆圈，证明必有一个三相邻数字之和大于等于17,证明把1至10这十个数字随机排成一个圆圈,从中任取三个相邻数字的方法有10种,设这10种三个相邻数字之和分别为m1,m2,m10,则有,m1+m2+m10=3(1+2+10)=,由推论2, 必存在mi(0i 10), 使得mi17，即问题得证,例5 边长为1的正方形中，任意放入9个点，求证这9个点中任取3个点组成的三角形中，至少有一个的面积不超过1/8.,解：将边长为1的正方形等分成边长为1/2的四个小正方形，视这四个正方形为鸽巢，9个点任意放入这四个正方形中，由鸽巢原理必有

6、三点落入同一个正方形内.现特别取出这个正方形来加以讨论.,图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点同

7、色,不妨设为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中不存在一元素是另两个元素之差，