抽屉原理教案范文

抽屉原理教案范文 抽屉原理及其应用钟韬在数学问题中有一类与“存在性”有关的问题，例如“13个人中至少有两个人出生在相同月份”；“某校400名学生中，一定存在两名学生，他们在同一天过生日”；“xx个人任意分成200个小组，一定存在一组，其成员数不少于11”；“把0，1内的全部有理数放到100个集合中，一定存在一个集合，它里面有无限多个有理数”。 这类存在性问题中，“存在”的含义是“至少有一个”。 在解决这类问题时，只要求指明存在，一般并不需要指出哪一个，也不需要确定通过什么方式把这个存在的东西找出来。 这类问题相对来说涉及到的运算较少，依据的理论也不复杂，我们把这些理论称之为“抽屉原理”。 “抽屉原理”最先是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题的，所以又称“迪里赫莱原理”，也有称“鸽巢原理”的。 这个原理可以简单地叙述为“把10个苹果，任意分放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。 这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异的结果。 一抽屉原理最常见的形式原理1如果把n+k(k1)个物体放进n只抽屉里，则至少有一只抽屉要放进两个或更多个物体。 证明（反证法）如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k1)，这不可能.原理2如果把mn+k(k1)个物体放进n个抽屉，则至少有一个抽屉至多放进m+1个物体。 证明（反证法）若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能.二应用抽屉原理解题抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。 许多有关存在性的证明都可用它来解决。 例400人中至少有两个人的生日相同.解将一年中的366天视为366个抽屉，400个人看作400个物体，由抽屉原理1可以得知至少有两人的生日相同.又如“我们从街上随便找来13人，就可断定他们中至少有两个人属相相同.”，“从任意5双手套中任取6只，其中至少有2只恰为一双手套。 ，“从数1，2，.，10中任取6个数，其中至少有2个数为奇偶性不同。 例2幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道理.解从三种玩具中挑选两件，搭配方式只能是下面六种（兔、兔），（兔、熊猫），（兔、长颈鹿），（熊猫、熊猫），（熊猫、长颈鹿），（长颈鹿、长颈鹿）。 把每种搭配方式看作一个抽屉，把7个小朋友看作物体，那么根据原理1，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式，选的玩具相同.上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题，不错，这正是抽屉原则的主要作用.（需要说明的是，运用抽屉原则只是肯定了“存在”、“总有”、“至少有”，却不能确切地指出哪个抽屉里存在多少.）抽屉原理虽然简单，但应用却很广泛，它可以解答很多有趣的问题，其中有些问题还具有相当的难度。 下面我们来研究有关的一些问题。 （一）整除问题把所有整数按照除以某个自然数m的余数分为m类，叫做m的剩余类或同余类，用0，1，2，?，m-1表示.每一个类含有无穷多个数，例如1中含有1，m+1，2m1，3m1，?.在研究与整除有关的问题时，常用剩余类作为抽屉.根据抽屉原理，可以证明任意n+1个自然数中，总有两个自然数的差是n的倍数。 例3证明任取8个自然数，必有两个数的差是7的倍数。 分析与解答在与整除有关的问题中有这样的性质，如果两个整数a、b，它们除以自然数m的余数相同，那么它们的差a-b是m的倍数.根据这个性质，本题只需证明这8个自然数中有2个自然数，它们除以7的余数相同.我们可以把所有自然数按被7除所得的7种不同的余数 0、 1、 2、 3、 4、 5、6分成七类.也就是7个抽屉.任取8个自然数，根据抽屉原理，必有两个数在同一个抽屉中，也就是它们除以7的余数相同，因此这两个数的差一定是7的倍数。 例4对于任意的五个自然数，证明其中必有3个数的和能被3整除.证明任何数除以3所得余数只能是0，1，2，不妨分别构造为3个抽屉0，1，2若这五个自然数除以3后所得余数分别分布在这3个抽屉中，我们从这三个抽屉中各取1个，其和必能被3整除.若这5个余数分布在其中的两个抽屉中，则其中必有一个抽屉，包含有3个余数（抽屉原理），而这三个余数之和或为0，或为3，或为6，故所对应的3个自然数之和是3的倍数.若这5个余数分布在其中的一个抽屉中，很显然，必有3个自然数之和能被3整除.例4对于任意的11个整数，证明其中一定有6个数，它们的和能被6整除.证明设这11个整数为a1，a2，a3?a11，又6=23先考虑被3整除的情形由例4知，在11个任意整数中，必存在3|a1+a2+a3，不妨设a1+a2+a3=b1；同理，剩下的8个任意整数中，由例4，必存在3|a4+a5+a6.设a4+a5+a6=b2；同理，其余的5个任意整数中，有3|a7+a8+a9，设a7+a8+a9=b3再考虑b 1、b 2、b3被2整除.依据抽屉原理，b 1、b 2、b3这三个整数中，至少有两个是同奇或同偶，这两个同奇（或同偶）的整数之和必为偶数.不妨设2|b1+b2则6|b1+b2，即6|a1+a2+a3+a4+a5+a6任意11个整数，其中必有6个数的和是6的倍数.例5任意给定7个不同的自然数，求证其中必有两个整数，其和或差是10的倍数.分析注意到这些数队以10的余数即个位数字，以0，1，?，9为标准制造10个抽屉，标以0，1，?，9.若有两数落入同一抽屉，其差是10的倍数，只是仅有7个自然数，似不便运用抽屉原则，再作调整6，7，8，9四个抽屉分别与4，3，2，1合并，则可保证至少有一个抽屉里有两个数，它们的和或差是10的倍数.（二）面积问题例6:在边长为1的正方形内任意放入九个点，求证存在三个点，以这三个点为顶点的三角形的面积不超过（1963年北京市数学竞赛题）。 分析与解答如图3，四等分正方形，得到A1，A2，A3，A4四个矩形。 在正方形内任意放入九个点，则至少有一个矩形Ai内存在+1=3个或3个以上的点，设三点为A、B、C，具体考察Ai（如图4），过A、B、C三点分别作矩形长边的平行线，过A点的平行线交BC于A点，A点到矩形长边的距离为h=(0h)，则ABC的面积SABC=SAAC+SAAB1h+1（-h）=说明把正方形分成四个区域，可以得出“至少有一个区域内有3个点”的结论，这就为确定三角形面积的取值范围打下了基础。 本题构造“抽屉”的办法不是唯一的，还可以将正方形等分成边长为的四个小正方形等。 但是如将正方形等分成四个全等的小三角形却是不可行的（想一想为什么？）。 所以适当地构造“抽屉”，正是应用抽屉原则解决问题的关键所在。 图5以下两个题目可以看作是本例的变式 （1）在边长为2的正方形内，随意放置9个点，证明必有3个点，以它们为顶点的三角形的面积不超过。 （2）在边长为1的正方形内任意给出13个点。 求证必有4个点，以它们为顶点的四边形的面积不超过1/4。 证明（如下图）把正方形分成四个相同的小正方形.因13=34+1，根据原理2，总有4点落在同一个小正方形内（或边界上），以此4点为顶点的四边形的面积不超过小正方形的面积，也就不超过整个正方形面积的1/4。 例79条直线的每一条都把一个正方形分成两个梯形，而且它们的面积之比为23。 证明这9条直线中至少有3条通过同一个点。 证明设正方形为ABCD，E、F分别是AB，CD的中点。 设直线L把正方形ABCD分成两个梯形ABGH和CDHG，并且与EF相交于P（如图6），梯形ABGH的面积梯形CDHG的面积=23EP是梯形ABGH的中位线，PF是梯形CDHG的中位线，由于，梯形的面积=中位线梯形的高，并且两个梯形的高相等（AB=CD），所以，梯形ABGH的面积梯形CDHG的面积=EPPF，也就是EPPF=23。 这说明，直线L通过EF上一个固定的点P，这个点把EF分成长度为23的两部分。 这样的点在EF上还有一个，如图上的Q点（FQQE=23）。 同样地，如果直线L与AB、CD相交，并且把正方形分成两个梯形面积之比是23，那么这条直线必定通过AD、BC中点连线上的两个类似的点（三等分点）。 这样，在正方形内就有4个固定的点，凡是把正方形面积分成两个面积为23的梯形的直线，一定通过这4点中的某一个。 我们把这4个点看作4个抽屉，9条直线看作9个物体，由抽屉原理可知，必有一个抽屉内至少放有3个物体，也就是，必有三条直线要通过同一个点。 说明本例中的抽屉比较隐蔽，正方形两双对边中点连线上的4个三等分点的发现是关键，而它的发现源于对梯形面积公式S梯形=中位线梯形的高的充分感悟。 （三）染色问题例8用黑、白两种颜色把一个25（即2行5列）的长方形中的每个小方格都随意染一种颜色.证明必有两列，它们的涂色方式完全相同。 分析与解答因为每列只有两格，而这两格的染法只有（右图）四种，将这4种染色方式当作4个抽屉，题中所有的方格共有5列，根据抽屉原理，至少有两列的染色方式完全相同。 例9如果有一个3n的方格阵列，每一列的三个方格都任意用红、黄、蓝、绿四色之三染成三种不同颜色，问n至少是多少时，才能保证至少有3列的染色方式完全相同。 分析与解答每一列都从4种颜色中选出三种分别染上这列中的三个小格，染色的方式共有432=24（种）.若要保证至少有3列的染色方式完全相同，那么n至少是242+149。 下面研究另一类长方形阵列小格的染色的问题。 例10对一块3行7列的长方形阵列中的小方格的每一格任意染成黑色或白色，求证在这个长方形中，一定有一个由小方格组成的长方形，它的四个角上的小方格同色。 证法1每一列的三个格用黑、白两种颜色染色.所有可能的染法只有如下图中的八种如果在所染色的3行7列阵列中某一列是第 （1）种方式，即三格均为白色，则其余6列中只要再有第 （1） （2） （3） （4）种方式之一（即该列中至少有两个白格），那么显然存在一个四角格都是白色的长方形.若第 （1）、 （2）、 （3）、 （4）种方式均未出现，那么其余6列就只能是 （5）、 （6）、 （7）、 （8）这四种方式，根据抽屉原理，其中至少有两列染色方式完全一样.又 （5） （8）中每一列至少有两格染黑色，所以一定存在一个长方形，它的四角格颜色都是黑色。 同理可知，如果有一列是第 （8）种方式，即三格均为黑色，那么也存在四角同色的长方形。 如果在7列中 （1）、 （8）两种方式都未出现，则只有 （2）、 （3）、 （4）、 （5）、 （6）、 （7）这六种方式染这7列，根据抽屉原理，至少有两列染色方式完全一样，所以仍然存在四角同色的长方形。 证法2第一行有7个小方格，用黑白两种颜色去染，根据抽屉原理，至少有四个方格所染颜色相同，不妨设第一行有4个黑方格.再看第二行，如果在第一行的四个黑方格下面的四格中有两格是黑色，则结论显然成立.否则第二行这四个格中至少有3个白色方格。 再看第三行.根据抽屉原理，在第三行的位于第二行的3个白格下面的3个格中必至少有两格同色.如果有两格为白色，则与第二行构成四角白色的长方形；如果没有两格白色，那么必有两格为黑色，则与第一行构成四角黑色的长方形。 例11用黑、白两种颜色将一个55的长方形中的小方格随意染色.求证在这个长方形中一定有一个由小方格组成的长方形，它的四个角上的小方格同色。 分析与解答第一行中的5个小方格用黑、白两种颜色去染，根据抽屉原理，至少有3个小方格同色.不妨设第一行的前3个为白格.现在考虑位于这3个白格下面的那个34的长方形（如下图），用黑、白两种颜色去染这个34的长方形，有以下两种情况A BD EF若在某一行的3个方格中出现两个白格，则它们与上方第一行相应的两个白格可组成四角同为白色的长方形。 若在43的长方形的任意一行的3个小方格中都不含两个白格，也就是每一行的3个小方格所涂的颜色只有一白二黑或三黑，则只有下面 （1）、 （2）、 （3）、 （4）共4种可能.如果 （4）出现在某一行中，那么不管其他三行为 （1）、 （2）、 （3）、 （4）中的哪种情况，必有一个四角为黑色小方格的长方形.如果 （4）未出现，则在这四行中只能出现 （1）、 （2）、 （3）这3种情况，由抽屉原理可知，必有两行染色方式完全相同，显然这两行中的4个黑色小方格可构成四角同黑的长方形.例12假设在一个平面上有任意六个点，无三点共线，每两点用红色或蓝色的线段连起来，都连好后，问你能不能找到一个由这些线构成的三角形，使三角形的三边同色？解首先可以从这六个点中任意选择一点，然后把这一点到其他五点间连五条线段，如图，在这五条线段中，至少有三条线段是同一种颜色，假定是红色，现在我们再单独来研究这三条红色的线。 这三条线段的另一端或许是不同颜色，假设这三条线段（虚线）中其中一条是红色的，那么这条红色的线段和其他两条红色的线段便组成了我们所需要的同色三角形，如果这三条线段都是蓝色的，那么这三条线段也组成我们所需要的同色三角形。 因而无论怎样着色，在这六点之间的所有线段中至少能找到一个同色三角形。 例13（第6届国际中学生数学奥林匹克试题）17名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个题目，证明其中至少有三名科学家，他们相互通信时讨论的是同一个题目。 证明视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。 三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。 考虑科学家A，他要与另外的16位科学家每人通信讨论一个问题，相应于从A出发引出16条线段，将它们染成3种颜色，而16=35+1，因而必有6=5+1条同色，不妨记为AB1，AB2，AB3，AB4，AB5，AB6同红色，若Bi（i=1，2，?，6）之间有红线，则出现红色三角线，命题已成立；否则B1，B2，B3，B4，B5，B6之间的连线只染有黄蓝两色。 考虑从B1引出的5条线，B1B2，B1B3，B1B4，B1B5，B1B6，用两种颜色染色，因为5=22+1，故必有3=2+1条线段同色，假设为黄色，并记它们为B1B2，B1B3，B1B4。 这时若B2，B3，B4之间有黄线，则有黄色三角形，命题也成立，若B2，B3，B4，之间无黄线，则B2，B3，B4，必为蓝色三角形，命题仍然成立。 说明 （1）本题源于一个古典问题-六人集会问题:在任意6个人的集会上，或者有3个人以前彼此相识，或者有三个人以前彼此不相识。 （美国普特南数学竞赛题）。 （2）将互相认识用红色表示，将互相不认识用蓝色表示， （1）将化为一个染色问题，成为一个图论问题空间六个点，任何三点不共线，四点不共面，每两点之间连线都涂上红色或蓝色。 求证存在三点，它们所成的三角形三边同色。 （3）问题 （2）可以往两个方向推广其一是颜色的种数，其二是点数。 本例便是方向一的进展，其证明已知上述。 如果继续沿此方向前进，可有下题在66个科学家中，每个科学家都和其他科学家通信，在他们的通信中仅仅讨论四个题目，而任何两个科学家之间仅仅讨论一个题目。 证明至少有三个科学家，他们互相之间讨论同一个题目。 （4）回顾上面证明过程，对于17点染3色问题可归结为6点染2色问题，又可归结为3点染一色问题。 反过来，我们可以继续推广。 从以上（3，1）（6，2）（17，3）的过程，易发现6=（3-1）2+2，17=（6-1）3+2，66=（17-1）4+2，同理可得（66-1）5+2=327，（327-1）6+2=1958?记为r1=3，r2=6，r3=17，r4=66，r5=327，r6=1958，?我们可以得到递推关系式r n=n(r n-1-1)+2，n=2,3,4?这样就可以构造出327点染5色问题，1958点染6色问题，都必出现一个同色三角形。 三制造抽屉是运用原理的关键例14从 2、 4、 6、?、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34。 分析与解答我们用题目中的15个偶数制造8个抽屉凡是抽屉中有两个数的，都具有一个共同的特点这两个数的和是34。 现从题目中的15个偶数中任取9个数，由抽屉原理（因为抽屉只有8个），必有两个数在同一个抽屉中.由制造的抽屉的特点，这两个数的和是34。 例15从 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个抽屉（每个括号看成一个抽屉）.只要有两个数取自同一个抽屉，那么它们的差就等于