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

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

精品文档
第九讲 复杂抽屉原理
内容概述
运用抽屉原理求解的较为复杂的组合计算与证明问题．这里不仅“抽屉”与“苹果”需要恰当地设计与选取，而且有时还应构造出达到最佳状态的例子．
典型问题
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倍；
从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)，则无论怎么放，必定有一个抽屉至少有个元素．

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同余．
于是(mod 499)(m>n)．
有-=，所以499 ，因为(499，
)=l，所以499；于是有(499×4)（4），即1996
于是，就找到这样的全部都是由4组成的数字，是1996的倍数．
评注：、、、可整除不合2，5因数的任何整数；
、、、整除不含因数5(因数2分别只能含1，2，2，3个)的任何整数；
整除不含因数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)、(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个孩子．

10. 在边长为1的正方形内随意放进9个点，证明其中必有3个点构成的三角形的面积不大于．
【分析与解】 如下图，把正方形分成四个形状相同、大小相等的正方形．9个点任意放人这四个正方形中．
根据抽屉原理，多于2×4个点放入四个长方形中，至少有2+1个点(即3个点)落在某一个正方形之内．现在，特别取出这个正方形来加以讨论．

把落在这正方形中的三点组成的三角形记为△ABC，其面积不超过小正方形面积的，所以其面积不超过．这样就得到了需要证明的结论．
评注：在边长为1的等边三角形中有个点，这个点中一定有距离不大于的两点；
在边长为l的等边三角形内有个点，这个点中一定有距离小于的两点．
已知平行四边形中，其面积为l，现有个点，则必定有三点组成的三角形，其面积不大于；
已知三角形中，其面积为1，现有个点，则必定有三点组成的三角形，其面积不大于．

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个的扇形，每一个都恰好覆盖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人．

收集于网络，如有侵权请联系管理员删除