六年级奥数-第九讲复杂抽屉原理教师版.doc

第九讲 复杂抽屉原理内容概述运用抽屉原理求解的较为复杂的组合计算与证明问题这里不仅“抽屉”与“苹果”需要恰当地设计与选取，而且有时还应构造出达到最佳状态的例子典型问题1从1，2，3，1988，1989这些自然数中，最多可以取出多少个数，使得其中每两个数的差不等于4？ 【分析与解】1，2，3，4，9，10，1l，12，17，18，19，20，25， 这些数中任何两个数的差都不为4，这些数是每8个连续的数中选取前4个连续的数 有19898=2485，所以最多可以选2484+4=996个数 评注：对于这类问题，一种方法是先尽可能的多选择，然后再找出这些数的规律，再计算出最多可以选出多少个.2从1至1993这1993个自然数中最多能取出多少个数，使得其中任意的两数都不连续且差不等于4？ 【分析与解】1，3，6，8，11，13，16，18，21， 这些数中任何两个数不连续且差不等于4，这些数是每5个连续的数中选择第1、3个数 19935=3983.所以最多可以选3982+2=798个数 评注：当然还可以是1，4，6，9，11，14，16，19，21， 这些数满足条件，是每5个连续的数中选择第1、4个数但是此时最多只能选出3982+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等奇数倍. 333：99，于是从35开始，199的奇数中没有一个是3599的奇数倍(不包括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，33n中任取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个元素放到n个抽屉中去(mn)，则无论怎么放，必定有一个抽屉至少有个元素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)我们将1100分成(1，2)，(3，4)，(5，6)，(7，8)，(99，100)这50组，每组内的数相邻而相邻的两个自然数互质 将这50组数作为50个抽屉，同一个抽屉内的两个数互质 而现在51个数，放进50个抽屉，则必定有两个数在同一抽屉，于是这两个数互质问题得证 (2)我们将1100分成(1，51)，(2，52)，(3，53)，(40，90)，(50，100)这50组，每组内的数相差50将这50组数视为抽屉，则现在有51个数放进50个抽屉内，则必定有2个数在同一抽屉，那么这两个数的差为50问题得证 (3)我们将1100按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=4499； 对于l，1l，11l， 中必定有两个数关于499同余 于是(mod 499)(mn) 有-=，所以499 ，因为(499，)=l，所以499；于是有(4994)（4），即1996 于是，就找到这样的全部都是由4组成的数字，是1996的倍数 评注：、可整除不合2，5因数的任何整数； 、整除不含因数5(因数2分别只能含1，2，2，3个)的任何整数； 整除不含因数2(因数5只能含1个)的任何整数9有49个小孩，每人胸前有一个号码，号码从1到49各不相同现在请你挑选若干个小孩，排成一个圆圈，使任何相邻两个小孩的号码数的乘积小于100，那么你最多能挑选出多少个孩子? 【分析与解】 将1至49中相乘小于100的两个数，按被乘数分成9组，如下： (12)、(13)、(14)、(149)； (23)、(24)、(25)、(249)； (89)、(810)、(8 11)、(812)； (910)、(911). 因为每个数只能与左右两个数相乘，也就是每个数作为被乘数或乘数最多两次，所以每一组中最多会有两对数出现在圆圈中，最多可以取出18个数对，共18 2=36次，但是每个数都出现两次，故出现了18个数 例如：(109)、(911)、(18)、(812)、(127)、(713)、(136)、(614)、(145)、(515)、(154)、(4 16)、(16 X 3)、(317)、(172)、(218)、(18 1)、(110)共出现l18号，共18个孩子 若随意选取出19个孩子，那么共有19个号码，由于每个号码数要与旁边两数分别相乘，则会形成19个相乘的数对 那么在9组中取出19个数时，有19=92+1，由抽屉原则知，必有三个数对落入同一组中，这样某个数字会在数对中出现三次(或三次以上)，由分析知，这是不允许的故最多挑出18个孩子10. 在边长为1的正方形内随意放进9个点，证明其中必有3个点构成的三角形的面积不大于 【分析与解】 如下图，把正方形分成四个形状相同、大小相等的正方形9个点任意放人这四个正方形中 根据抽屉原理，多于24个点放入四个长方形中，至少有2+1个点(即3个点)落在某一个正方形之内现在，特别取出这个正方形来加以讨论 把落在这正方形中的三点组成的三角形记为ABC，其面积不超过小正方形面积的，所以其面积不超过这样就得到了需要证明的结论 评注：在边长为1的等边三角形中有个点，这个点中一定有距离不大于的两点； 在边长为l的等边三角形内有个点，这个点中一定有距离小于的两点 已知平行四边形中，其面积为l，现有个点，则必定有三点组成的三角形，其面积不大于； 已知三角形中，其面积为1，现有个点，则必定有三点组成的三角形，其面积不大于11某班有16名学生，每个月教师把学生分成两个小组问最少要经过几个月，才能使该班的任意两个学生总有某个月份是分在不同的小组里? 【分析与解】经过第一个月，将16个学生分成两组，至少有8个学生分在同一组，下面只考虑这8个学生 经过第二个月，将这8个学生分成两组，至少有4个学生是分在同一组，下面只考虑这4个学生 经过第三个月，将这4个学生分成两组，至少有2个学生仍分在同一组，这说明只经过3个月是无法满足题目要求的 如果经过四个月，将每个月都一直保持同组的学生一分为二，放人两个组，那么第一个月保持同组的人数为162=8人，第二个月保持同组的人数为82=4人，第三个月保持同组人数为42=2人，这说明，照此分法，不会有2个人一直保持在同一组内，即满足题目要求，故最少要经过4个月12上体育课时，21名男、女学生排成3行7列的队形做操老师是否总能从队形中划出一个长方形，使得站在这个长方形4个角上的学生或者都是男生，或者都是女生?如果能，请说明理由；如果不能，请举出实例 【分析与解】 因为只有男生或女生两种情况，所以第1行的7个位置中至少有4个位置同性别 为了确定起见，不妨设前4个位置同是男生，如果第二行的前4个位置有2名男生，那么4个角同是男生的情况已经存在，所以我们假定第二行的前4个位置中至少有3名女生，不妨假定前3个是女生 又第三行的前3个位置中至少有2个位置是同性别学生，当是2名男生时与第一行构成一个四角同性别的矩形，当有2名女生时与第二行构成四角同性别的矩形 所以，不论如何，总能从队形中划出一个长方形，使得站在这个长方形4个角上的学生同性别问题得证138个学生解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道题至少共被解出25=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=27+2，可以使每名同学解出题目不超过3道，这样就无法找到两名学生，使每道题目至少被其中一人解出 具体构造如下表，其中汉字代表题号，数字代表学生，打代表该位置对应的题目被该位置对应的学生解出14时钟的表盘上按标准的方式标着1，2，3，11，12这12个数，在其上任意做n个的扇形，每一个都恰好覆盖4个数，每两个覆盖的数不全相同如果从这任做的n个扇形中总能恰好取出3个覆盖整个钟面的全部12个数，求n的最小值 【分析与解】 如下图，只要从某个数字对应的位置开始，做出的扇形，一定能覆盖4个数 从最不利的情况出发，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人，都有一个题目的答案互不相同问参加考试的学生最多有多少人? 【分析与解】 设总人数为A，再由分析可设第一题筛选取出的人数为，第二题筛选的人数为，第三题筛选取的人数为，第四题筛选的人数为 如果不能满足题目要求，则： 至少是3，即3个人只有两种答案 由于是人做第四题后筛选取出的人数，则由抽屉原则知，(两种答案)中至少放有个苹果(即). =3，则A3至少为4，即4人只有两种答案 由于是人做第三题后筛选的人数，则由抽屉原则知，将个苹果放久三个抽屉(三种答案)，那么必然有两个抽屉(两种答案)中至少放有个苹果(即) =4，则至少为5，即5人只有两种答案 同理，有=5则至少为7，即做完第一道题必然有7个人只有两种答案；则有=7则至少为10，即当有10人参加考试时无法满足题目的要求 考虑9名学生参加考试，令每人答题情况如下表所示(汉字表示题号，数字表示学生)故参加考试的学生最多有9人