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

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

六年级奥数总复习2(教师版)6第九讲复杂抽屉原理内容概述运用抽屉原理求解的较为复杂的组合计算与证明问题.这里不仅“抽屉”与“苹果”需要恰当地设计与选取,而且有时还应构造出达到最佳状态的例子.典型问题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个数.评注:当然还可以是1,4,6,9,11,14,16,19,21,…,这些数满足条件,是每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倍;六年级奥数总复习2(教师版)6从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个抽屉中去(m≥n),则无论怎么放,必定有一个抽屉至少有11mn个元素.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个元素.六年级奥数总复习2(教师版)6最不利的情况下,51个数中有33个元素在第三组,那么剩下的18个数分到第一、二两组内,那么至少有9个数在同一组.所以这9个数的最大公约数为2或3或它们的倍数,显然大于1.问题得证8.求证:可以找到一个各位数字都是4的自然数,它是1996的倍数.【分析与解】注意到1996=4×499;对于l,1l,11l,…,44011111个中必定有两个数关于499同余.于是11111m个11111n个(mod499)(mn).有11111m个-11111n个=111110000mn个n个0,所以499111110000mn个n个0,因为(499,10000n个0)=l,所以4991111m-n个1;于是有(499×4)(1111m-n个14),即19964444m-n个4于是,就找到这样的全部都是由4组成的数字,是1996的倍数.评注:11111k个、33333k个、77777k个、99999k个可整除不合2,5因数的任何整数;22222k个、44444k个、66666k个、88888k个整除不含因数5(因数2分别只能含1,2,2,3个)的任何整数;55555k个整除不含因数2(因数5只能含1个)的任何整数.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)、(16X3)、(3×17)、(17×2)、(2×18)、(18×1)、(1×10).共出现l~18号,共18个孩子.若随意选取出19个孩子,那么共有19个号码,由于每个号码数要与旁边两数分别相乘,则会形成19个相乘的数对.那么在9组中取出19个数时,有19=9×2+1,由抽屉原则知,必有三个数对落入同一组中,这样某个数字会在数对中出现三次(或三次以上),由分析知,这是不允许的.故最多挑出18个孩子.10.在边长为1的正方形内随意放进9个点,证明其中必有3个点构成的三角形的面积不大于18.【分析与解】如下图,把正方形分成四个形状相同、大小相等的正方形.9个点任意放人这四个正方形中.根据抽屉原理,多于2×4个点放入四个长方形中,至少有2+1个点(即3个点)落在某六年级奥数总复习2(教师版)6一个正方形之内.现在,特别取出这个正方形来加以讨论.把落在这正方形中的三点组成的三角形记为△ABC,其面积不超过小正方形面积的12,所以其面积不超过18.这样就得到了需要证明的结论.评注:在边长为1的等边三角形中有21n个点,这21n个点中一定有距离不大于1n的两点;在边长为l的等边三角形内有21n个点,这21n个点中一定有距离小于1n的两点.已知平行四边形中,其面积为l,现有221n个点,则必定有三点组成的三角形,其面积不大于212n;已知三角形中,其面积为1,现有221n个点,则必定有三点组成的三角形,其面积不大于21n.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名女生时与第二行构成四角同性别的矩形.所以,不论如何,总能从队形中划

1 / 6
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功