抽屉原理的典型问题

《抽屉原理的典型问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、奥数探秘：奥数之抽屉原理桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1或多于n+1个元素放到n个集合中去，其中必定至少有一个集合里至少有两个元素。”　　一.抽屉原理最常见的形式　　原理1把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。　　[证明](反证法)：如果每个抽屉

2、至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k≥1)，这不可能.　　原理2把多于mn(m乘以n)个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。　　[证明](反证法)：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能.原理12都是第一抽屉原理的表述第二抽屉原理：　把(mn-1)个物体放入n个抽屉中，其中必有一个抽屉中至多有(m—1)个物体。　　[证明](反证法)：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能　　二.应用抽屉原理解题

3、　　　　例1：400人中至少有两个人的生日相同.　　解：将一年中的366天视为366个抽屉，400个人看作400个物体，由抽屉原理1可以得知：至少有两人的生日相同.　　又如：我们从街上随便找来13人，就可断定他们中至少有两个人属相相同.　　“从任意5双手套中任取6只，其中至少有2只恰为一双手套。”　　“从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同。”　　例2：幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道理.　　解：从三种玩

4、具中挑选两件，搭配方式只能是下面六种：(兔、兔)，(兔、熊猫)，(兔、长颈鹿)，(熊猫、熊猫)，(熊猫、长颈鹿)，(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉，把7个小朋友看作物体，那么根据原理1，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式，选的玩具相同.　　上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题，不错，这正是抽屉原则的主要作用.(需要说明的是，运用抽屉原则只是肯定了“存在”、“总有”、“至少有”，却不能确切地指出哪个抽屉里存在多少.)　　(一)整除问题　　把所有整数按照除以某个自然

5、数m的余数分为m类，叫做m的剩余类或同余类，用[0]，[1]，[2]，…，[m-1]表示.每一个类含有无穷多个数，例如[1]中含有1，m+1，2m+1，3m+1，….在研究与整除有关的问题时，常用剩余类作为抽屉.根据抽屉原理，可以证明：任意n+1个自然数中，总有两个自然数的差是n的倍数。　例1证明：任取8个自然数，必有两个数的差是7的倍数。分析与解答在与整除有关的问题中有这样的性质，如果两个整数a、b，它们除以自然数m的余数相同，那么它们的差a-b是m的倍数.根据这个性质，本题只需证明这8个自然数中有2个自然数，它们除以7的余数相同.我们

6、可以把所有自然数按被7除所得的7种不同的余数0、1、2、3、4、5、6分成七类.也就是7个抽屉.任取8个自然数，根据抽屉原理，必有两个数在同一个抽屉中，也就是它们除以7的余数相同，因此这两个数的差一定是7的倍数。　例2：对于任意的五个自然数，证明其中必有3个数的和能被3整除.　证明∵任何数除以3所得余数只能是0，1，2，不妨分别构造为3个抽屉：　　[0]，[1]，[2]　　①若这五个自然数除以3后所得余数分别分布在这3个抽屉中(即抽屉中分别为含有余数为0,1,2的数)，我们从这三个抽屉中各取1个(如1~5中取3,4,5)，其和(3+4+5

7、=12)必能被3整除.　②若这5个余数分布在其中的两个抽屉中，则其中必有一个抽屉，包含有3个余数(抽屉原理)，而这三个余数之和或为0，或为3，或为6，故所对应的3个自然数之和是3的倍数.　　③若这5个余数分布在其中的一个抽屉中，很显然，必有3个自然数之和能被3整除.　　例2′：对于任意的11个整数，证明其中一定有6个数，它们的和能被6整除.　　证明：设这11个整数为：a1，a2，a3……a11又6=2×3　　①先考虑被3整除的情形　　由例2知，在11个任意整数中，必存在：　　3

8、a1+a2+a3，不妨设a1+a2+a3=b1;　　同理，剩

9、下的8个任意整数中，由例2，必存在：3

10、a4+a5+a6.设a4+a5+a6=b2;　　同理，其余的5个任意整数中，有：3

11、a7+a8+a9，设：a7+a8+a9=b3　　②再考虑b1、b2、