第二章抽屉原理课后题

1、第二章第二章 抽屉原理抽屉原理LOGOPage 2抽屉原理习题抽屉原理习题1在在1,4,7,10,13,100中任意选出中任意选出20个个数，证明其中至少有不同的两对数，每数，证明其中至少有不同的两对数，每对数的和都等于对数的和都等于104LOGOPage 3抽屉原理习题抽屉原理习题1分析分析:本题中要求选出本题中要求选出20个数个数,且至少有不同的两对数和为且至少有不同的两对数和为104,故应构造少于故应构造少于20个数组个数组,且同一组数的和为且同一组数的和为104解答解答:将本题中给出的数分成将本题中给出的数分成(4,100) (7,97) (49,55) (52) (1)共共1818个

2、数组个数组, ,每个数组中的数的和为每个数组中的数的和为104,104,从这从这1818个抽屉中任取个抽屉中任取2020个数个数, ,有下有下述两种情况：述两种情况： 1) 1)取到取到1 1和和52,52,则剩下的则剩下的1818个数取自余下的个数取自余下的1616个抽屉个抽屉, ,故至少有故至少有2 2对数对数取自某两个抽屉，即和为取自某两个抽屉，即和为104104 2) 2)不全取不全取1 1和和52,52,则有多于则有多于1818个数取自个数取自1616个抽屉中个抽屉中, ,同样至少同样至少有有2对数对数取自某两个抽屉，即和为取自某两个抽屉，即和为104LOGOPage 4抽屉原理习题

3、抽屉原理习题2在在1,2,2n中任取中任取n+1个数，证明其个数，证明其中必有两个数互素中必有两个数互素LOGOPage 5抽屉原理习题抽屉原理习题2分析分析:本题中要求选出本题中要求选出n+1个数个数,且必有两个数互素且必有两个数互素,故应构造至故应构造至多多n个数组个数组,且每组两数互素且每组两数互素解答解答:将本题中给出的数分成将本题中给出的数分成(1,2) (2,3) (2n-1,2n) 共共n n个数组个数组, ,每每个数组中两数互素个数组中两数互素, ,从这从这n n个抽屉中取个抽屉中取n+1n+1个数个数, ,必必有两数取自同一个抽有两数取自同一个抽屉，即取到的两数互素屉，即取到

4、的两数互素LOGOPage 6抽屉原理习题抽屉原理习题3从从1,2,3,2005中删去一些数，使得剩中删去一些数，使得剩下的数中任何一个数都不等于其余两个下的数中任何一个数都不等于其余两个不同数的积，问至少要删去多少个数才不同数的积，问至少要删去多少个数才能做到这一点？能做到这一点？LOGOPage 7抽屉原理习题抽屉原理习题3分析分析:本题较难本题较难,因难以据题意决断构造几个抽屉因难以据题意决断构造几个抽屉,但知道每个抽但知道每个抽屉需满足任何一个数等于其余两个不同数的积屉需满足任何一个数等于其余两个不同数的积解答解答:将本题中给出的数分成将本题中给出的数分成(44,45,4445) (4

5、3,46,4346) (3,86,386) (2,87,287)共共4343组组, ,故至少删去故至少删去4343个数个数, ,即即2,3,4,442,3,4,44后后, ,剩下的剩下的数就满足题中条件数就满足题中条件LOGOPage 8抽屉原理习题抽屉原理习题4在不超过在不超过91的正整数中任取的正整数中任取10个不同的个不同的数，证明这数，证明这10个数中一定有两个数的比个数中一定有两个数的比值在值在2/3,3/2内内LOGOPage 9抽屉原理习题抽屉原理习题4分析分析:本题中要求任取本题中要求任取10个数个数,且必有两个数的比值在且必有两个数的比值在2/3,3/2之间之间,故应构造至多

6、故应构造至多9个数组个数组,且同一组中任两个数的比值在且同一组中任两个数的比值在2/3,3/2之间之间解答解答:把不超过把不超过91的正整数分成的正整数分成(1)(2,3) (4,5,6)(7,8,9,10) (11,12,13,14,15,16) (17,18,19,20,21,22,23,24,25) (26,27,28,29,30,31,39) (40,41,42,60) (61,62,63,90)共共9 9个数组个数组, ,每个数组中的任意两数的每个数组中的任意两数的比值在比值在2/3,3/2之间之间, ,从这从这9 9个抽屉中任取个抽屉中任取1010个数个数, ,有下述两种情况：有下

7、述两种情况： 1) 1)取到取到1,1,则剩下的则剩下的9 9个数取自余下的个数取自余下的8 8个抽屉个抽屉, ,则必有两个数取自同一个抽屉，则必有两个数取自同一个抽屉，即即两数的比值在两数的比值在2/3,3/2之间之间 2) 2)不取不取1,1,则则1010个数取自余下的个数取自余下的8 8个抽屉个抽屉, ,必必有两个数取自同一个抽屉，即两有两个数取自同一个抽屉，即两数的比值在数的比值在2/3,3/2之间之间分情况讨论分情况讨论LOGOPage 10抽屉原理习题抽屉原理习题5任给任给7个实数，证明其中必有两个数个实数，证明其中必有两个数x,y满足满足3013xyxyLOGOPage 11抽屉

8、原理习题抽屉原理习题5分析分析:由要证明的不等式形式想到两角差的正切公式由要证明的不等式形式想到两角差的正切公式,且两角差且两角差小于小于/6解答解答:首先首先,7个实数中至少有个实数中至少有4个数同为非正或非负个数同为非正或非负(抽屉原理的抽屉原理的简单应用简单应用)不妨设不妨设4个数同为非负数个数同为非负数,设为设为tan1,tan2, tan3, tan4,因非负因非负i0,/2),i=1,2,3,4 4个数中必有个数中必有2个数的差满足条件个数的差满足条件,故将故将4个数分成个数分成3组组,故将故将0,/2)分分为为3个抽屉个抽屉0,/6), /6,/3), /3,/2).这样必有两个

9、这样必有两个m ,n取自同一取自同一个抽屉个抽屉,不妨设不妨设m n,则则0m n/6,0tan(m n)3/3.故故必存在数必存在数x= tanm, y= tann 满足条件满足条件多次运用抽屉原理多次运用抽屉原理LOGOPage 12抽屉原理习题抽屉原理习题6坐标平面内任给坐标平面内任给13个整点，其中任个整点，其中任3点点均不共线，求证必有以其中均不共线，求证必有以其中3点为顶点点为顶点的三角形其重心也是整点的三角形其重心也是整点LOGOPage 13抽屉原理习题抽屉原理习题6分析分析:因为三角形的重心公式为因为三角形的重心公式为(x1+x2+x3)/3, (y1+y2+y3)/3),若

10、若为整点则要求为整点则要求3/(x1+x2+x3) ,3/(y1+y2+y3),对于整除性问题通常按剩对于整除性问题通常按剩余类分组余类分组,即即012,当当x1,x2,x3或或y1,y2,y3取自同一个剩余类时，则取自同一个剩余类时，则3可以整除它们之和可以整除它们之和解答解答:设平面内设平面内13个点的坐标为个点的坐标为pn (xn ,yn) ,n=1,2,3,13, ,于是于是pn中必中必有有13/3+1=5个点的横坐标同在个点的横坐标同在3的一个剩余类中，为使重心为整点还需其纵的一个剩余类中，为使重心为整点还需其纵坐标之和也是坐标之和也是3的整数倍的整数倍,下面在这下面在这5个点中考虑其纵坐标个点中考虑其纵坐标,应有以下两种情况应有以下两种情况： 1)5 1)5个点的纵坐标中个点的纵坐标中,3,3的的3 3个剩余类均存在，即存在个剩余类均存在，即存在pi, pj, pk,使其纵坐标使其纵坐标yi3(0), yj3(1), yi3(2),则就取这三点组成三角形