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

《六年级奥数-第九讲.复杂抽屉原理.教师版(7页).doc》由会员分享，可在线阅读，更多相关《六年级奥数-第九讲.复杂抽屉原理.教师版(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-第 1 页六年级奥数六年级奥数-第九讲第九讲.复杂抽屉原理复杂抽屉原理.教师教师版版-第 1 页第九讲第九讲 复杂抽屉原理复杂抽屉原理内容概述内容概述运用抽屉原理求解的较为复杂的组合计算与证明问题这里不仅“抽屉”与“苹果”需要恰当地设计与选取，而且有时还应构造出达到最佳状态的例子典型问题典型问题1 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，所

2、以最多可以选 2484+4=996 个数评注评注：对于这类问题，一种方法是先尽可能的多选择，然后再找出这些数的规律，再计算出最多可以选出多少个.2 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 个数但

3、是此时最多只能选出 3982+l=797 个数3 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 是这

4、样的数所以，在满足题意情况下最多可以选出 8 个数4 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，

5、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 个数，则其中必有两个数，它们中一个是另一个的整数倍，

6、且至少是 3倍；从 1，2，3，mn 中任取(m-1)n+1 个数，则其中必有两个数，它们中一个是另一个的整数倍，且至少是 m 倍(m、n 为正整数).-第 2 页5 5证明：任给 12 个不同的两位数，其中一定存在着这样的两个数，它们的差是个位与十位数字相同的两位数【分析与解】因为两个不同的两位数相减得到的差不可能为三位或三位以上的数如果这个差是 1l 的倍数，那么一定有这个差的个位与十位数字相同两个数的差除以 1l 的余数有 0、1、2、3、10 这 11 种情况将这 11 种情况视为 11 个抽屉将 12 个数视为 12 个苹果，那么必定有两个苹果在同一抽屉，也就是说有两个数除以 11

7、的余数相同，那么它们的差一定是 11 的倍数而两个两位数的差一定是一个两位数，如果这个差是 11 的倍数，那么就有个数与十位数字相等问题得证评注评注：抽屉原理一：将 n+1 个元素放到 n 个抽屉中去，则无论怎么放，必定有一个抽屉至少有两个元素抽屉原理二：将 nr+1 个元素放到 n 个抽屉中去，则无论怎么放，必定有一个抽屉至少有 r+1 个元素抽屉原理三：将 m 个元素放到 n 个抽屉中去(mn)，则无论怎么放，必定有一个抽屉至少有11mn个元素6 6从 1，2，3，49，50 这 50 个数中取出若干个数，使其中任意两个数的和都不能被 7 整除，则最多能取出多少个数?【分析与解】利用除以

8、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 个数，所以最多可

9、以取 1+8+7+7=23 个数7 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)我们将 1

10、100 分成(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

11、个数分到第一、二两组内，那么至少有 9 个数在同一组所以这 9 个数的最大公约数为 2 或 3 或它们的倍数，显然大于 1问题得证8 8求证：可以找到一个各位数字都是 4 的自然数，它是 1996 的倍数【分析与解】注意到 1996=4499；-第 3 页对于 l，1l，11l，44011111个中必定有两个数关于 499 同余于是11111m个11111n个(mod 499)(mn)有11111m个-11111n个=111110000m n 个n个0，所以 499111110000m n 个n个0，因为(499，10000 n个0)=l，所以 4991111m-n个1；于是有(4994)（1

12、111m-n个14），即 19964444 m-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 9有 49 个小孩，每人胸前有一个号码，号码从 1 到 49 各不相同现在请你挑选若干个小孩，排成一个圆圈，使任何相邻两个小孩的号码数的乘积小于 1

13、00，那么你最多能挑选出多少个孩子?【分析与解】将 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)、(5

14、15)、(154)、(4 16)、(16 X 3)、(317)、(172)、(218)、(18 1)、(110)共出现 l18 号，共18 个孩子若随意选取出 19 个孩子，那么共有 19 个号码，由于每个号码数要与旁边两数分别相乘，则会形成 19个相乘的数对那么在 9 组中取出 19 个数时，有 19=92+1，由抽屉原则知，必有三个数对落入同一组中，这样某个数字会在数对中出现三次(或三次以上)，由分析知，这是不允许的故最多挑出 18 个孩子1010.在边长为 1 的正方形内随意放进 9 个点，证明其中必有 3 个点构成的三角形的面积不大于18【分析与解】如下图，把正方形分成四个形状相同、大

15、小相等的正方形9 个点任意放人这四个正方形中根据抽屉原理，多于 24 个点放入四个长方形中，至少有 2+1 个点(即 3 个点)落在某一个正方形之内现在，特别取出这个正方形来加以讨论把落在这正方形中的三点组成的三角形记为ABC，其面积不超过小正方形面积的12，所以其面积不超过18这样就得到了需要证明的结论评注：评注：在边长为 1 的等边三角形中有21n 个点，这21n 个点中一定有距离不大于1n的两点；在边长为 l 的等边三角形内有21n 个点，这21n 个点中一定有距离小于1n的两点-第 4 页已知平行四边形中，其面积为 l，现有221n 个点，则必定有三点组成的三角形，其面积不大于212n

16、；已知三角形中，其面积为 1，现有221n 个点，则必定有三点组成的三角形，其面积不大于21n1111某班有 16 名学生，每个月教师把学生分成两个小组问最少要经过几个月，才能使该班的任意两个学生总有某个月份是分在不同的小组里?【分析与解】经过第一个月，将 16 个学生分成两组，至少有 8 个学生分在同一组，下面只考虑这 8 个学生经过第二个月，将这 8 个学生分成两组，至少有 4 个学生是分在同一组，下面只考虑这 4 个学生经过第三个月，将这 4 个学生分成两组，至少有 2 个学生仍分在同一组，这说明只经过 3 个月是无法满足题目要求的如果经过四个月，将每个月都一直保持同组的学生一分为二，放

17、人两个组，那么第一个月保持同组的人数为 162=8 人，第二个月保持同组的人数为 82=4 人，第三个月保持同组人数为 42=2 人，这说明，照此分法，不会有 2 个人一直保持在同一组内，即满足题目要求，故最少要经过 4 个月1212上体育课时，21 名男、女学生排成 3 行 7 列的队形做操老师是否总能从队形中划出一个长方形，使得站在这个长方形 4 个角上的学生或者都是男生，或者都是女生?如果能，请说明理由；如果不能，请举出实例【分析与解】因为只有男生或女生两种情况，所以第 1 行的 7 个位置中至少有 4 个位置同性别为了确定起见，不妨设前 4 个位置同是男生，如果第二行的前 4 个位置有

18、 2 名男生，那么 4 个角同是男生的情况已经存在，所以我们假定第二行的前 4 个位置中至少有 3 名女生，不妨假定前 3 个是女生又第三行的前 3 个位置中至少有 2 个位置是同性别学生，当是 2 名男生时与第一行构成一个四角同性别的矩形，当有 2 名女生时与第二行构成四角同性别的矩形所以，不论如何，总能从队形中划出一个长方形，使得站在这个长方形 4 个角上的学生同性别问题得证13138 个学生解 8 道题目(1)若每道题至少被 5 人解出，请说明可以找到两个学生，每道题至少被过两个学生中的一个解出(2)如果每道题只有 4 个学生解出，那么(1)的结论一般不成立试构造一个例子说明这点.【分析

19、与解】(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 道

20、题，则另 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

21、=32 次，可以使每名学生都解出 4 次，那么每人解出 4 道题随便找一名学生，必有 4 道未被他解出，这 4 道题共被 7 名同学解出 44=16 次，由于 16=27+2，可以使每名同学解出题目不超过 3 道，这样就无法找到两名学生，使每道题目至少被其中一人解出具体构造如下表，其中汉字代表题号，数字代表学生，打代表该位置对应的题目被该位置对应的学生解出-第 5 页1414时钟的表盘上按标准的方式标着 1，2，3，11，12 这 12 个数，在其上任意做 n 个120的扇形，每一个都恰好覆盖 4 个数，每两个覆盖的数不全相同如果从这任做的 n 个扇形中总能恰好取出 3 个覆盖整个钟面的全部

22、12 个数，求 n 的最小值【分析与解】如下图，只要从某个数字对应的位置开始，做出的120扇形，一定能覆盖 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 个数，如：(

23、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 个数1515试卷上共有 4 道选择题，每题有 3 个可供选择的答案一群学生参加考试，结果是对于其中任何 3 人，都有一个题目的答案互不相同问参加考试的学生最多有多少人?【分析与解】设总人数为 A，再由分析可设第一题筛选取出的人数为1A，第二题筛选的人数为2A，第三题筛选取的人数为3A，第四题筛选的人数为4A如果不能满足题目要求，则：4A至少是 3，即 3 个人

24、只有两种答案由于4A是3A人做第四题后筛选取出的人数，则由抽屉原则知，(两种答案)中至少放有333AA个苹果(即4A).333AA=4A=3，则 A3 至少为 4，即 4 人只有两种答案由于3A是2A人做第三题后筛选的人数，则由抽屉原则知，将2A个苹果放久三个抽屉(三种答案)，那么必然有两个抽屉(两种答案)中至少放有223AA个苹果(即3A)223AA=3A=4，则2A至少为 5，即 5 人只有两种答案同理，有113AA=2A=5 则1A至少为 7，即做完第一道题必然有 7 个人只有两种答案；则有003AA=1A=7则0A至少为 10，即当有 10 人参加考试时无法满足题目的要求考虑 9 名学生参加考试，令每人答题情况如下表所示(汉字表示题号，数字表示学生)-第 6 页故参加考试的学生最多有 9 人