抽屉原理(竞赛)[下学期]

课件22张PPT。抽屉原理 瑞安市安阳二中 陈朝敏 桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n＋1或多于n＋1个元素放到n个集合中去，其中必定至少有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽笼原理（“如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2只鸽子”）。它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原理。它是组合数学中一个重要的原理。一．? 抽屉原理最常见的形式原理1 ：如果把n+k(k≥1)个物体放进n只抽屉里，则至少有一只抽屉要放进两个或更多个物体。[证明]（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k≥1)，这不可能.原理2 ：如果把mn+k(k≥1)个物体放进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，2m＋1，3m＋1，….在研究与整除有关的问题时，常用剩余类作为抽屉. 根据抽屉原理，可以证明：任意n+1个自然数中，总有两个自然数的差是n的倍数。例1 证明：任取8个自然数，必有两个数的差是7的倍数。分析与解答: 在与整除有关的问题中有这样的性质，如果两个整数a、b，它们除以自然数m的余数相同，那么它们的差a-b是m的倍数. 根据这个性质，本题只需证明这8个自然数中有2个自然数，它们除以7的余数相同. 我们可以把所有自然数按被7除所得的7种不 同的余数0、1、2、3、4、5、6分成七类,也就是7个抽屉. 任取8个自然数，根据抽屉原理，必有两个数在同一个抽屉中，也就是它们除以7的余数相同，因此这两个数的差一定是7的倍数 ... ...