复杂的抽屉原理

复杂的抽屉原理 运用抽屉原理求解的较为复杂的组合计算与问题(这里不仅“抽屉”与“苹果”需要恰当地设计与选取，而且有时还应构造出达到最佳状态的例子( 1(从1，2，3，„，1988，1989这些自然数中，最多可以取出多少个数，使得其中每两个数的差不等于4, 【分析与解】1，2，3，4，9，10，1l，12，17，18，19，20，25，„， 这些数中任何两个数的差都不为4，这些数是每8个连续的数中选取前4个连续的数( 有1989?8=248„„5，所以最多可以选248×4+4=996个数( 评注:对于这类问题，一种是先尽可能的多选择，然后再找出这些数的规律，再计算出最多可以选出多少个. 2(从1至1993这1993个自然数中最多能取出多少个数，使得其中任意的两数都不连续且差不等于4, 【分析与解】1，3，6，8，11，13，16，18，21，„， 这些数中任何两个数不连续且差不等于4，这些数是每5个连续的数中选择第1、3个数( 1993?5=398„„3.所以最多可以选398×2+2=798个数( ，4，6，9，1 1，14，16，19，21，„， 评注:当然还可以是1 这些数满足条件，是每5个连续的数中选择第1、4个数( 但是此时最多只能选出398×2+l=797个数( 3. 从1，2，3，4，5，6，7，8，9，10，11，12中最多能选出几个数，使得在选出的数中，每一个数都不是另一个数的2倍? 【分析与解】 方法一:直接从1开始选1，3，4，5，7，9，11，12，这样可以选出8个数; 而从2开始选2，3，5，7，8，9，11，12，这样也是可以选出8个数( 3包含在组内，因此只用考虑这两种情况即可( 所以，在满足题意情况下，最多可以选出8个数( 方法二:我们知道选多少个奇数均满足，有1，3，5，7，9，11均为奇数，并且有偶数中4的倍数，但不是8的倍数的也满足，有4，12是这样的数( 所以，在满足题意情况下最多可以选出8个数( 4(从1，3，5，7，„，97，99中最多可以选出多少个数，使得选出的数中，每一个数都不是另一个数的倍数? 【分析与解】 方法一:因为均是奇数，所以如果存在倍数关系，那么也一定是3、5、7等奇数倍. 3×33:99，于是从35开始，199的奇数中没有一个是35,99的奇数倍(不包括1倍)，所以选出35，37，39，„，99这些奇数即可( 共可选出33个数，使得选出的数中，每一个数都不是另一个数的倍数( 方法二:利用3的若干次幂与质数的乘积对这50个奇数分组( (1，3，9，27，81)，(5，15，45)，(7，21，63)，(11，33)，(13，39)，(17，51)，(19，57)， (23，69)，(25，75)，(29，87)，(31，93)，(35)，(37)，(41)，(43)，„，(97)共33组( 前11组，每组内任意两个数都存在倍数关系，所以每组内最多只能选择一 个数( 即最多可以选出33个数，使得选出的数中，每一个数都不是另一个数的 倍数( 评注:12n个自然数中，任意取出n+1个数，则其中必定有两个数，它们一个是另一个的整数倍; 从2，3(„„，2n+1中任取n+2个数，必有两个数，它们一个是另一个的整数倍; 从1，2，3(„„3n中任取2n+1个数，则其中必有两个数，它们中一个是另一个的整数倍，且至少是3倍; 从1，2，3，„„， mn中任取(m-1)n+1个数，则其中必有两个数，它们中一个是另一个的整数倍，且至少是m倍(m、n为正整数). 5(证明:任给12个不同的两位数，其中一定存在着这样的两个数，它们的差是个位与十位数字相同的两位数( 【分析与解】 因为两个不同的两位数相减得到的差不可能为三位或三位以上的数(如果这个差是1l的倍数，那么一定有这个差的个位与十位数字相同( 两个数的差除以1l的余数有0、1、2、3、„、10这11种情况(将这11种情况视为11个抽屉( 将12个数视为12个苹果，那么必定有两个苹果在同一抽屉，也就是说有两个数除以11的余数相同，那么它们的差一定是11的倍数( 而两个两位数的差一定是一个两位数，如果这个差是11的倍数，那么就有个数与十位数字相等(问题得证( 评注:抽屉原理一:将n+1个元素放到n个抽屉中去，则无论怎么放，必定有一个抽屉至少有两个元素( 抽屉原理二:将nr+1个元素放到n个抽屉中去，则无论怎么放，必定有一个抽屉至少有r+1个元素( m,1，，，1抽屉原理三:将m个元素放到n个抽屉中去(m?n)，则无论怎么放，必定有一个抽屉至少有个,,n，，元素( 6(从1，2，3，„，49，50这50个数中取出若干个数，使其中任意两个数的和都不能被7整除，则最多能取出多少个数? 【分析与解】 利用除以7的余数分类: 余0:(7，14，21，28，35，42，49); 余1:(1，8，15，22，29，36，43，50); 余2:(2，9，16，23，30，37，44); 余3:(3，10，17，24，31，38，45); 余4:(4，11，18，25，32，39，46); 余5:(5，12，19，26，33，40，47); 余6:(6，13，20，27，34，41，48)( 第一组内的数最多只能取1个;如果取第二组，那么不能取第七组内任何一个数;取第三组，不能取第六组内任何一个数;取第四组，不能取第五组内任意一个数( 第二、三、四、五、六、七组分别有8、7、7、7、7、7个数，所以最多可以取1+8+7+7=23个数( 7(从1，2，3，„，99，100这100个数中任意选出51个数(证明: (1)在这51个数中，一定有两个数互质; (2)在这51个数中，一定有两个数的差等于50; (3)在这51个数中，一定存在9个数，它们的最大公约数大于1( 【分析与解】 (1)我们将1,100分成(1，2)，(3，4)，(5，6)，(7，8)，„，(99，100)这50组，每组内的数相邻(而相邻的两个自然数互质( 将这50组数作为50个抽屉，同一个抽屉内的两个数互质( 而现在51个数，放进50个抽屉，则必定有两个数在同一抽屉，于是这两个数互质(问题得证( (2)我们将1—100分成(1，51)，(2，52)，(3，53)，„，(40，90)，„(50，100)这50组，每组内的数相差50(将这50组数视为抽屉，则现在有51个数放进50个抽屉内，则必定有2个数在同一抽屉，那么这两个数的差为50(问题得证( (3)我们将1—100按2的倍数、3的奇数倍、既不是2又不是3的倍数的情况分组，有(2，4，6，8，„，98，100)，(3，9，15，21，27，„，93，99)，(5，7，11，13，17，19，23，„，95，97)这三组(第一、二、三组分别有50、17、33个元素( 最不利的情况下，51个数中有33个元素在第三组，那么剩下的18个数分到第一、二两组内，那么至少有9个数在同一组(所以这9个数的最大公约数为2或3或它们的倍数，显然大于1(问题得证 8(求证:可以找到一个各位数字都是4的自然数，它是1996的倍数( 【分析与解】注意到1996=4×499; 对于l，1l，11l，„， 中必定有两个数关于499同余( 1111 4401个 , 于是(mod 499)(m>n)( 11111111 m个1n个1 有-=，所以499 ，因为(499， 111100001111000011111111 mn,个1mn,个1m个1n个1n个0n个0 )=l，所以499;于是有(499×4)(4)，即1996 10000111111114444 m-n个1m-n个1m-n个4n个0 于是，就找到这样的全部都是由4组成的数字，是1996的倍数( 评注:、、、可整除不合2，5因数的任何整数; 1111333377779999 k个1k个7k个9k个3 、、、整除不含因数5(因数2分别只能含1，2，2，3个)的任何整数; 2222444466668888 k个2k个4k个6k个8 整除不含因数2(因数5只能含1个)的任何整数( 5555 k个5 9(有49个小孩，每人胸前有一个号码，号码从1到49各不相同(现在请你挑选若干个小孩，排成一个圆圈，使任何相邻两个小孩的号码数的乘积小于100，那么你最多能挑选出多少个孩子? 【分析与解】 将1至49中相乘小于100的两个数，按被乘数分成9组， 如下: (1×2)、(1×3)、(1×4)、„、(1×49); (2×3)、(2×4)、(2×5)、„、(2×49); (8×9)、(8×10)、(8 ×11)、(8×12); (9×10)、(9×11). 因为每个数只能与左右两个数相乘，也就是每个数作为被乘数或乘数最多两次，所以每一组中最多会有两对数出现在圆圈中，最多可以取出18个数对，共18 ×2=36次，但是每个数都出现两次，故出现了18个数( 例如:(10×9)、(9×11)、(1×8)、(8×12)、(12×7)、(7×13)、(13×6)、(6×14)、(14×5)、(5×15)、 (15×4)、(4 ×16)、(16 X 3)、(3×17)、(17×2)、(2×18)、(18 ×1)、(1×10)(共出现l,18号，共18个孩子( 若随意选取出19个孩子，那么共有19个号码，由于每个号码数要与旁边两数分别相乘，则会形成19个相乘的数对( 那么在9组中取出19个数时，有19=9×2+1，由抽屉原则知，必有三个数对落入同一组中，这样某个数字会在数对中出现三次(或三次以上)，由分析知，这是不允许的(故最多挑出18个孩子( 110. 在边长为1的正方形内随意放进9个点，证明其中必有3个点构成的三角形的面积不大于( 8 【分析与解】 如下图，把正方形分成四个形状相同、大小相等的正方形(9个点任意放人这四个正方形中( 根据抽屉原理，多于2×4个点放入四个长方形中，至少有2+1个点(即3个点)落在某一个正方形之内(现在，特别取出这个正方形来加以讨论( 1 把落在这正方形中的三点组成的三角形记为?ABC，其面积不超过小正方形面积的，所以其面积不2 1超过(这样就得到了需要证明的结论( 8 122 评注:在边长为1的等边三角形中有个点，这个点中一定有距离不大于的两点; n，1n，1n 122 在边长为l的等边三角形内有n，1个点，这n，1个点中一定有距离小于的两点( n 12 已知平行四边形中，其面积为l，现有21n，个点，则必定有三点组成的三角形，其面积不大于; 22n 12 已知三角形中，其面积为1，现有21n，个点，则必定有三点组成的三角形，其面积不大于( 2n 11(某班有16名学生，每个月教师把学生分成两个小组(问最少要经过几个月，才能使该班的任意两个学生总有某个月份是分在不同的小组里? 【分析与解】经过第一个月，将16个学生分成两组，至少有8个学生分在同一组，下面只考虑这8个学生( 经过第二个月，将这8个学生分成两组，至少有4个学生是分在同一组，下面只考虑这4个学生( 经过第三个月，将这4个学生分成两组，至少有2个学生仍分在同一组，这说明只经过3个月是无法满 足题目要求的( 如果经过四个月，将每个月都一直保持同组的学生一分为二，放人两个组，那么第一个月保持同组的人数为16?2=8人，第二个月保持同组的人数为8?2=4人，第三个月保持同组人数为4?2=2人，这说明，照此分法，不会有2个人一直保持在同一组内，即满足题目要求，故最少要经过4个月( 12(上体育课时，21名男、女学生排成3行7列的队形做操(老师是否总能从队形中划出一个长方形，使得站在这个长方形4个角上的学生或者都是男生，或者都是女生?如果能，请说明理由;如果不能，请举出实例( 【分析与解】 因为只有男生或女生两种情况，所以第1行的7个位置中至少有4个位置同性别( 为了确定起见，不妨设前4个位置同是男生，如果第二行的前4个位置有2名男生，那么4个角同是男生的情况已经存在，所以我们假定第二行的前4个位置中至少有3名女生，不妨假定前3个是女生( 又第三行的前3个位置中至少有2个位置是同性别学生，当是2名男生时与第一行构成一个四角同性别的矩形，当有2名女生时与第二行构成四角同性别的矩形( 所以，不论如何，总能从队形中划出一个长方形，使得站在这个长方形4个角上的学生同性别(问题得证( 13(8个学生解8道题目( (1)若每道题至少被5人解出，请说明可以找到两个学生，每道题至少被过两个学生中的一个解出( (2)如果每道题只有4个学生解出，那么(1)的结论一般不成立(试构造一个例子说明这点. 【分析与解】 (1)先设每道题被一人解出称为一次，那么8道题目至少共解 ，出58=40次，分到8个学生身上，至少有一个学生解出了5次或5次以上题目，即这个学生至少解出5道题，称这个学生为4，我们讨论以下4种可能: ， 第一种可能:若4只解出5道题，则另3道题应由其他7个人解出，而3道题至少共被解出35=15次，分到7个学生身上，至少有一名同学解出了3次或3次以上的题目(15=27+1，由抽屉原则便知)由于只有3， 道题，那么这3道题被一名学生全部解出，记这名同学为B( 那么，每道题至少被A、B两名同学中某人解出( 第二种可能:若A解出6道题，则另2道题应由另7人解出，而2道题至少共被解出2×5=10次，分到 ，7个同学身上，至少有一名同学解出2次或2次以上的题目(10=17+3，由抽屉原则便知)(与l第一种可能I同理，这两道题必被一名学生全部解出，记这名同学为C( 那么，每道题目至少被A、C学生中一人解出( 第三种可能:若A解出7道题目，则另一题必由另一人解出，记此人为D(那么，每道题目至少被A、D两名学生中一人解出( 第四种可能:若A解出8道题目，则随意找一名学生，记为E，那么，每道题目至少被A、E两名学生中一人解出，所以问题(1)得证( ， (2)类似问题(1)中的想法，题目共被解出84=32次，可以使每名学生都解出4次，那么每人解出4道题( ， 随便找一名学生，必有4道未被他解出，这4道题共被7名同学解出44=16次，由于16=2×7+2，可以使每名同学解出题目不超过3道，这样就无法找到两名学生，使每道题目至少被其中一人解出( 具体构造如下，其中汉字代表题号，数字代表学生，打?代表该位置对应的题目被该位置对应的学生解出( 14(时钟的表盘上按的方式标着1，2，3，„，11，12这12个数，在其上任意做n个的扇形，每一120个都恰好覆盖4个数，每两个覆盖的数不全相同(如果从这任做的n个扇形中总能恰好取出3个覆盖整个钟面的全部12个数，求n的最小值( 【分析与解】 如下图，只要从某个数字对应的位置开始，做出的扇形，一定能覆盖4个数( 120 从最不利的情况出发，n个扇形中最大程度的重叠，需做(12，1，2，3)，(1，2，3，4)，(2，3，4，5)，(3，4，5，6)，(4，5，6，7)，(5，6，7，8)，(6，7，8，9)，(7，8，9，10)，(8，9，10，11)这 9个120。扇形才能将整个钟面覆盖(从中可以挑出3个覆盖整个钟面全部12个数( 也就是说n最小取9时，才能保证题意的满足( 评注:如果n取8那么就能给出一种做法，使得选不出3个扇形覆盖整个钟面的全部12个数，如:(12，1，2，3)，(1，2，3，4)，(2，3，4，5)，(3，4，5，6)，(4，5，6，7)，(5，6，7，8)，(6，7，8，9)，(7，8，9，10)，这8个扇形对应的数中都不包含11这个数，当然没办法取得全部的12个数( 15(试卷上共有4道选择题，每题有3个可供选择的答案(一群学生参加考试，结果是对于其中任何3人，都有一个题目的答案互不相同(问参加考试的学生最多有多少人? AA 【分析与解】 设总人数为A，再由分析可设第一题筛选取出的人数为，第二题筛选的人数为，第21 AA三题筛选取的人数为，第四题筛选的人数为( 43 如果不能满足题目要求，则: A 至少是3，即3个人只有两种答案( 4 A，，3A,AA 由于是人做第四题后筛选取出的人数，则由抽屉原则知，(两种答案)中至少放有个苹果343,,3，， A(即). 4 A，，3A,A ==3，则A3至少为4，即4人只有两种答案( 34,,3，， AAA 由于是人做第三题后筛选的人数，则由抽屉原则知，将个苹果放久三个抽屉(三种答案)，那么223 A，，2A,A必然有两个抽屉(两种答案)中至少放有个苹果(即)( 23,,3，， A，，2A,AA ==4，则至少为5，即5人只有两种答案( 223,,3，， A，，1A,AA 同理，有==5则至少为7，即做完第一道题必然有7个人只有两种答案;则有121,,3，， A，，0A,AA==7(则至少为10，即当有10人参加考试时无法满足题目的要求( 001,,3，， 考虑9名学生参加考试，令每人答题情况如下表所示(汉字表示题号，数字表示学生)( 故参加考试的学生最多有9人(