第13讲第十三讲抽屉原理进阶知识站牌六年级春季六年级寒假组合模块选讲（二）组合模块选讲（一）六年级秋季抽屉原理进阶六年级秋季数字谜中的计数六年级暑期最值问题综合复杂的抽屉原理构造问题，重点是数论中抽屉原理的应用漫画释义第11级下优秀A版教师版1\n教学目标1.理解抽屉原理1和2的联系和区别2.掌握数论中抽屉的构造技巧知识点回顾1.某班32名同学是在5月份出生的，能否找到两个生日是在同一天的小朋友？【分析】5月有31天，学生人数＞天数，把31天看作31个抽屉，将32名同学看作32个苹果．这样，把32个苹果放进31个抽屉里，至少有一个抽屉里放至少两个苹果．因此至少有2名同学是同一天出生．2.班上有50名小朋友，老师至少拿几本书，随意分给小朋友，才能保证至少有一个小朋友能得到不少于两本书？【分析】根据抽屉原理，至少要拿50151本书．3.教室里有5名学生正在做作业，今天只有数学、英语、语文、地理四科作业试说明：这5名学生中，至少有两个人在做同一科作业．【分析】将5名学生看作5个苹果将数学、英语、语文、地理作业各看成一个抽屉，共4个抽屉由抽屉原理，一定存在一个抽屉，在这个抽屉里至少有2个苹果．即至少有两名学生在做同一科的作业．4.一个口袋中装有500粒珠子，共有5种颜色，每种颜色各100粒．如果你闭上眼睛，至少取出多少粒珠子才能保证其中有5粒颜色相同？【分析】至少要取(51)5121（粒）5.有红、黄、白三种颜色的小球各10个，混合放在一个布袋中，一次至少摸出个，才能保证有5个小球是同色的．【分析】根据最不利原则，至少需要摸出43113（个）．课堂引入“任意367个人中，必有生日相同的人．”“从任意5双手套中任取6只，其中至少有2只恰为一双手套．”“从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同．”......大家都会认为上面所述结论是正确的．这些结论是依据什么原理得出的呢？这就是我们今天要学习的抽屉原理2第11级下优秀A版教师版\n第13讲经典精讲抽屉原理有时也被称为鸽笼原理，它由德国数学家狄利克雷首先明确提出来并用来证明一些数论中的问题，因此，也被称为狄利克雷原则．抽屉原理是组合数学中一个重要而又基本的数学原理，利用它可以解决很多有趣的问题，并且常常能够起到令人惊奇的作用．许多看起来相当复杂，甚至无从下手的问题，在利用抽屉原则后，能很快使问题得到解决．抽屉原理推广到一般情形有以下两种表现形式：抽屉原理1：将多于n件的物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件；抽屉原理2：将多于mn件的物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于m1件．应用抽屉原理解题的步骤：第一步：分析题意．分清什么是“苹果”，什么是“抽屉”，也就是什么作“苹果”，什么可作“抽屉”．第二步：制造抽屉．这个是关键的一步，这一步就是如何设计抽屉．根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽屉及其个数，为使用抽屉铺平道路．第三步：运用抽屉原理．观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，以求问题之解决．把所有整数按照除以某个自然数m的余数分为m类，叫做m的剩余类或同余类，用[0]，[1]，[2]，…，[m1]表示.每一个类含有无穷多个数，例如[1]中含有1，m1，2m1，3m1，….在研究与整除有关的问题时，常用剩余类作为抽屉.根据抽屉原理，可以证明：任意n1个自然数中，总有两个自然数的差是n的倍数．例题思路模块一：抽屉原理的基本应用例1：最不利原则例2：抽屉原理的基本应用模块二：抽屉原理在数论中的应用例3：数论中和或差是固定值的构造例4：数论中剩余类的构造例5：数论中剩余类的构造例1试说明400人中至少有两个人的生日相同.【分析】将一年中的366天或365天视为366个或365个抽屉，400个人看作400个苹果，从最极端的情况考虑，即每个抽屉都放一个苹果，还有35个或34个苹果必然要放到有一个苹果的抽屉里，所以至少有一个抽屉有至少两个苹果，即至少有两人的生日相同.第11级下优秀A版教师版3\n【想想练练】五年级数学小组共有20名同学，他们在数学小组中都有一些朋友，请你说明：至少有两名同学，他们的朋友人数一样多．【分析】数学小组共有20名同学，因此每个同学最多有19个朋友；又由于他们都有朋友，所以每个同学至少有1个朋友．因此，这20名同学中，每个同学的朋友数只有19种可能：1，2，3，……，19．把这20名同学看作20个“苹果”，又把同学的朋友数目看作19个“抽屉”，根据抽屉原理，至少有2名同学，他们的朋友人数一样多．例2（A版（1）~（2））一副扑克牌，共54张，问：至少从中摸出多少张牌才能保证：⑴至少有5张牌的花色相同；⑵四种花色的牌都有；⑶至少有3张牌是红桃．⑷至少从中取出几张牌，才能保证至少有2张梅花和3张红桃．（学案对应：学案1）【分析】一副扑克牌有四种花色，每种花色各13张，另外还有两张王牌，共54张．⑴为了“保证”5张牌花色相同，我们应从最“坏”的情况去分析，即先摸出了两张王牌，再把四种花色看作4个抽屉，要想有5张牌属于同一个抽屉，只需再摸出44117(张)，也就是共摸出19张牌．即至少摸出19张牌，才能保证其中有5张牌的花色相同．⑵因为每种花色有13张牌，若考虑最“坏”的情况，即摸出了2张王牌和三种花色的所有牌共计133241(张)，这时，只需再摸一张即一共42张牌，就保证四种花色的牌都有了．即至少摸出42张牌才能保证四种花色的牌都有．⑶最“坏”的情形是先摸出了2张王牌和黑桃、梅花、方块三种花色所有牌共计133241张，只剩红桃牌．这时只需再摸3张，就保证有3张牌是红桃了，即至少摸出44张牌，才能保证其中至少有3张红桃牌．⑷因为每种花色有13张牌，若考虑最“坏”的情况，即摸出2张王牌、方块和黑桃两种花色的所有牌共计：132228(张)，然后是摸出所有的梅花和3张红桃(想想若摸出所有的红桃和2张梅花，是最坏的情况么？)，共计：2813344张．例3从1，4，7，10，…，37，40这14个数中任取8个数，试证：其中至少有2个数的和是41.（学案对应：学案2）【分析】构造和为41的抽屉：(1,40)，(4,37)，(7,34)，(10,31)，(13,28)，(16,25)，(19,22)，现在取8个数，一定有两个数取在同一个抽屉，所以至少有2个数的和是41.【想想练练】请证明：在1，4，7，10，…，100中任选20个数，其中至少有不同的两组数其和都等于104．【分析】1，4，7，10，…，100共有34个数，将其分为(4，100)，(7，97)，…，(49，55)，(1)，(52)，共有18个抽屉．从这18个抽屉里面任意抽取20个数，则至少有18个数取自前16个抽屉，所以至少有4个数取自某两个抽屉中，而属于同一“抽屉”的两个数，其和是104．4第11级下优秀A版教师版\n第13讲1958年6月7号的《美国数学月刊》上有这样一道题目：“证明在任意6个人的集会上，或者有3个人以前彼此相识，或者有三个人以前彼此不相识．”这个问题可以用如下方法简单明了地证出：在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人．如果两人以前彼此认识，那么就在代表他们的两点间连成一条红线；否则连一条蓝线．考虑A点与其余各点间的5条连线AB，AC，...，AF，它们的颜色不超过2种．根据抽屉原理可知其中至少有3条连线同色，不妨设AB，AC，AD同为红色．如果BC，BD，CD3条连线中有一条（不妨设为BC）也为红色，那么三角形ABC即一个红色三角形，A、B、C代表的3个人以前彼此相识：如果BC、BD、CD三条连线全为蓝色，那么三角形BCD即一个蓝色三角形，B、C、D代表的3个人以前彼此不相识．不论哪种情形发生，都符合问题的结论．例4证明：任取8个自然数，必有两个数的差是7的倍数．（学案对应：学案3）【分析】在与整除有关的问题中有这样的性质，如果两个整数a、b，它们除以自然数m的余数相同，那么它们的差ab是m的倍数.根据这个性质，本题只需证明这8个自然数中有2个自然数，它们除以7的余数相同.我们可以把所有自然数按被7除所得的7种不同的余数0、1、2、3、4、5、6分成七类.也就是7个抽屉.任取8个自然数，根据抽屉原理，必有两个数在同一个抽屉中，也就是它们除以7的余数相同，因此这两个数的差一定是7的倍数．例5（小学数学奥林匹克决赛）从1，2，3，4，…，1988，1989这些自然数中，最多可以取____个数，其中每两个数的差不等于4．（学案对应：学案4）【分析】将1～1989排成四个数列：1，5，9，…，1985，1989第11级下优秀A版教师版5\n2，6，10，…，19863，7，11，…，19874，8，12，…，1988每个数列相邻两项的差是4，因此，要使取出的数中，每两个的差不等于4，每个数列中不能取相邻的项．因此，第一个数列只能取出一半，因为有(19891)41498项，所以最多取出249项，例如1，9，17，…，1985．同样，后三个数列每个最多可取249项．因而最多取出2494996个数，其中每两个的差不等于4．【想想练练】(南京市首届“兴趣杯”少年数学邀请赛)从1至36个数中，最多可以取出___个数，使得这些数中没有两数的差是5的倍数．【分析】构造公差为5的数列，如图，有五条链，看成5个抽屉，每条链上取1个数，最多取5个数．1－6－11－16－21－26－31－362－7－12－17－22－27－323－8－13－18－23－28－334－9－14－19－24－29－345－10－15－20－25－30－35据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很重视手指纹，希望通过手指纹来破案或检定犯人．可是你知道不知道：在12亿中国人当中，最少有两个人的头发是一样的多？道理是很简单，人的头发数目是不会超过12亿这么大的数目字！假定人最多有N根头发．现在我们想像有编上号码1，2，3，4，…一直到N的房子．谁有多少头发，谁就进入编号和他的头发数相同的房子去．因此张乐平先生的“三毛”应该进入“3号房子”．现在假定每间房巳进入一个人，那么还剩下“12亿减N”个人，这数目不会等于零，我们现在随便挑一个放进一间和他头发数相同的房子，他就会在里面遇到和他有相同头发数目的同志了．下面来解决下面一个实际问题有一个晚上你的房间的电灯忽然间坏了，伸手不见五指，而你又要出去，于是你就摸床底下的袜子．你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜就乱丢，在黑暗中不能知道哪一双是颜色相同的．你想拿最少数目的袜子出去，在外面借街灯配成同颜色的一双．这最少数目应该是多少？答案：4只袜子6第11级下优秀A版教师版\n第13讲杯赛提高（2006年华罗庚金杯数学邀请赛）自制的一副玩具牌共计52张（含四种牌：红桃、红方、黑桃、黑梅．每种牌都有1点，2点，…，13点牌各一张）．洗好后背面向上放好，⑴一次至少抽取张牌，才能保证其中必定有2张牌的点数和颜色都相同．⑵如果要求一次抽出的牌中必定有3张牌的点数是相邻的（不计颜色），那么至少要取张牌．【分析】⑴由于点数有13种情况，颜色有黑、红两种情况，根据最不利的原则，我们可以取黑、红颜色的1,2,3,,12,13点各一张，共计13226张，那么再取一张必然会出现颜色相同，因此至少取26127张牌，才能保证其中必定有2张牌的点数和颜色都相同．⑵可以构造点数相邻的抽屉如下(1,2,3),(4,5,6),(7,8,9),(10,11,12),(13)，根据最不利原则，可以取点数分别为1,2,4,5,7,8,10,11,13各四张，共计9436张，如果再取一张必然必定有3张牌的点数是相邻的（不计颜色）.思考题1.某次数学、英语测试，所有参加测试者的得分都是自然数，最高得分198，最低得分169，没有得193分、185分和177分，并且至少保证有6人得同一分数，参加测试的至少人．【分析】1981691327种得分，2751136人．2.一次测验共有10道问答题，每题的评分标准是：回答完全正确，得5分；回答不完全正确，得3分；回答完全错误或不回答，得0分．至少____人参加这次测验，才能保证至少有3人得得分相同．【分析】根据评分标准可知，最高得分为50分，最低得分为0分，在0～50分之间，1分，2分，4分，7分，47分，49分不可能出现．共有51645（种）不同得分．根据抽屉原理，至少有452191（人）参赛，才能保证至少有3人得分相同．3.证明：任给12个不同的两位数，其中一定存在着这样的两个数，它们的差是个位与十位数字相同的两位数．【分析】两位数除以11的余数有11种：0，1，2，3，4，5，6，7，8，9，10，按余数情况把所有两位数分成11种．12个不同的两位数放入11个抽屉，必定有至少2个数在同一个抽屉里，这2个数除以11的余数相同，两者的差一定能整除11．两个不同的两位数，差能被11整除，这个差也一定是两位数（如11，22……），并且个位与十位相同．所以，任给12个不同的两位数，其中一定存在着这样的两个数，它们的差是个位与十位数字相同的两位数．第11级下优秀A版教师版7\n4.（第八届《小数报》数学竞赛决赛）将全体自然数按照它们个位数字可分为10类：个位数字是1的为第1类，个位数字是2的为第2类，…，个位数字是9的为第9类，个位数字是0的为第10类．任意取出6个互不同类的自然数，其中一定有2个数的和是10的倍数吗？任意取出7个互不同类的自然数，其中一定有2个数的和是10的倍数吗？如果一定，请简要说明理由；如果不一定，请举出一个反例．【分析】（1）不一定有．例如1、2、3、4、5、10这6个数中，任意两个数的和都不是10的倍数．（2）一定有．将第1类与第9类合并，第2类与第8类合并，第3类与第7类合并，第4类与第6类合并，制造出4个抽屉；把第5类、第10类分别看作1个抽屉，共6个抽屉．任意7个互不同类的自然数，放到这6个抽屉中，至少有1个抽屉里放2个数．因为7个数互不同类，所以后两个抽屉中每个都不可能放两个数．当两个互不同类的数放到前4个抽屉的任何一个里面时，它们的和一定是10的倍数．5.在任意的五个自然数中，是否其中必有三个数的和是3的倍数？【分析】任何整数除以3的余数只能是0，1，2三种情形之一．现在，对于任意的五个自然数，根据抽屉原理，至少有一个抽屉里有两个或两个以上的数，于是可分下面两种情形来加以讨论．第一种情形：有三个数在同一个抽屉里，即这三个数除以3后具有相同的余数．因为这三个数的余数之和是其中一个余数的3倍，故能被3整除，所以这三个数之和能被3整除．第二种情形：至多有两个数在同一个抽屉里，那么每个抽屉里都有数，在每个抽屉里各取一个数，这三个数被3除的余数分别为0，1，2．因此这三个数之和能被3整除．综上所述，在任意的五个自然数中，其中必有三个数的和是3的倍数．6.求证：对于任意的8个自然数，一定能从中找到6个数a，b，c，d，e，f，使得(abcde)()(f)是105的倍数．【分析】105357．对于任意的8个自然数，必可选出2个数，使它们的差是7的倍数；在剩下的6个数中，又可选出2个数，使它们的差是5的倍数；在剩下的4个数中，又可选出2个数，使它们的差是3的倍数．知识点总结抽屉原理1：将多于n件的物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件；抽屉原理2：将多于mn件的物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于m1件．任意n1个自然数中，总有两个自然数的差是n的倍数．家庭作业1.有一个布袋中有40个相同的小球，其中编上号码1、2、3、4的各有10个，问：一次至少要取出多少个小球，才能保证其中至少有3个小球的号码相同？【分析】将1、2、3、4四种号码看作4个抽屉，要保证一个抽屉中至少有3个苹果，最“坏”的情8第11级下优秀A版教师版\n第13讲况是每个抽屉里有2个“苹果”，共有：428(个)，再取1个就能满足要求，所以一次至少要取出9个小球，才能保证其中至少有3个小球的号码相同．2.一副扑克牌有54张，最少要抽取几张牌，方能使其中至少有2张牌有相同的点数？【分析】如果不算大、小王，每个花色13张牌，只需14张便一定有两张相同点数的牌，加上大、小王，则需要16张牌．3.从2、4、6、…、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34．【分析】我们用题目中的15个偶数制造8个抽屉，(2),(4,30)，(6,28)，…，(16,18),凡是抽屉中的有两个数，都具有一个共同的特点：这两个数的和是34．现从题目中的15个偶数中任取9个数，由抽屉原理（因为抽屉只有8个），必有两个数在同一个抽屉中.由制造的抽屉的特点，这两个数的和是34．4.从1，2，3，，100这100个数中任意挑出51个数来，证明在这51个数中，一定有两个数的差为50．【分析】将100个数分成50组：{1,51}，{2,52}，{3,53}，，{50,100}，将其看作50个抽屉，在选出的51个数中，必有两个属于一组，这一组的差为50．这道题也同样可以从小数入手考虑5.从1，2，3，4，5，6，7，8，9，10，11，12中最多能选出几个数，使得在选出的数中，每一个数都不是另一个数的2倍？【分析】这12个数分成6个组：第1组：1，2，4，8第2组：3，6，12第3组：5，10第4组：7第5组：9第6组：11每组中相邻两数都是2倍关系，不同组中没有2倍关系．选没有2倍关系的数，第1组最多2个（1，4或2，8或1，8），第2组最多2个（3，12），第3组只有1个，第4，5，6组都可以取，一共2211118个．如果任意取9个数，因为第3，4，5，6组一共5个数中，最多能取4个数，剩下945个数在2个组中，根据抽屉原理，至少有3个数是同一组的，必有2个数是同组相邻的数，是2倍关系．6.证明：任取6个自然数，必有两个数的差是5的倍数．【分析】把自然数按照除以5的余数分成5个剩余类，即5个抽屉.任取6个自然数，根据抽屉原理，至少有两个数属于同一剩余类，即这两个数除以5的余数相同，因此它们的差是5的倍数．A版学案【学案1】有红、黄、白三种颜色的小球各10个，混合放在一个布袋中，一次至少摸出个，才能保证有5个小球是同色的？【分析】根据最不利原则，至少需要摸出43113（个）．第11级下优秀A版教师版9\n【学案2】从1、2、3、4、…、19、20这20个自然数中，至少任选几个数，就可以保证其中一定包括两个数，它们的差是12．【分析】在这20个自然数中，差是12的有以下8对：｛20，8｝，｛19，7｝，｛18，6｝，｛17，5｝，｛16，4｝，｛15，3｝，｛14，2｝，｛13，1｝．另外还有4个不能配对的数｛9｝，｛10｝，｛11｝，｛12｝，共制成12个抽屉（每个括号看成一个抽屉）.只要有两个数取自同一个抽屉，那么它们的差就等于12，根据抽屉原理至少任选13个数，即可办到（取12个数：从12个抽屉中各取一个数（例如取1，2，3，…，12），那么这12个数中任意两个数的差必不等于12）．【学案3】在任意的四个自然数中，是否其中必有两个数，它们的差能被3整除？【分析】因为任何整数除以3，其余数只可能是0，1，2三种情形．我们将余数的这三种情形看成是三个“抽屉”．一个整数除以3的余数属于哪种情形，就将此整数放在那个“抽屉”里．将四个自然数放入三个抽屉，至少有一个抽屉里放了不止一个数，也就是说至少有两个数除以3的余数相同（需要对学生利用余数性质进行解释：为什么余数相同，则差就能被整除）．这两个数的差必能被3整除【学案4】从1，2，3，4，…，1994这些自然数中，最多可以取个数，能使这些数中任意两个数的差都不等于9．【分析】方法一：把1994个数一次每18个分成一组，最后14个数也成一组，共分成111组．即1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18；19，20，21，22，23，24，25，26，27，28，29，30，31，32，33，34，35，36；…………………1963，1964，…，1979，1980；1981，1982，…，1994．每一组中取前9个数，共取出9111999（个）数，这些数中任两个的差都不等于9．因此，最多可以取999个数．方法二：构造公差为9的9个数列（除以9的余数）1,10,19,28,,1990，共计222个数2,11,20,29,,1991，共计222个数3,12,21,30,,1992，共计222个数4,13,22,31,,1993，共计222个数5,14,23,32,,1994，共计222个数6,15,24,33,,1986，共计221个数7,16,25,34,,1987，共计221个数8,17,26,35,,1988，共计221个数9,18,27,36,,1989，共计221个数每个数列相邻两项的差是9，因此，要使取出的数中，每两个的差不等于9，每个数列中不能取相邻的项．因此，前五个数列只能取出一半，后四个数列最多能取出一半多一个数，所以最多取1119999个数1第11级下优秀A版教师版