数学中的抽屉原理

先看简单的事实：把3本书放到两个抽屉里，只有两种情况：一个一本一个二本，或一个三本一个没有。无论哪种情况，都至少有一个抽屉里有两本或两本以上的书。更一般地说，只要被放置的书数比抽屉数目大，就一定会有两本或两本以上的书放进同一抽屉。
　　
　　（一）抽屉原理的常见式
　　
　　【原理一】：如果把n个东西放进n（m>n）只抽屉里，则至少有一只抽屉要放进两个或两个以上的东西。
　　
　　【例1】求证：在任意选取的n+1个整数中，至少存在两个整数，它们的差能被n整除。
　　
　　证明：对于n+1个整数，被除所得的余数为0，1，…，n－1共n类，按余数的不同分成的n类中，至少有两个在同一类里，即这两个数被n除时所得的余数相同，那么它们的差就一定能被n整除。
　　
　　【例2】幼儿园有三种塑料玩具（白兔、熊猫、长颈鹿）各若干个，每个小朋友任意选择两件。证明：不管怎样挑选，在七个小朋友中总有两个人选的玩具相同。
　　
　　证明：从三种玩具中挑选两件，搭配方式共有下列六种：（兔、兔）、（兔、熊猫）、（兔、长颈鹿）、（熊猫、熊猫）、（熊猫、长颈鹿）、（长颈鹿、长颈鹿），每一种可以看作一个抽屉，七人的7种选法中，只有6种不同的搭配，由抽屉原理，七人中至少有两人挑选玩具时搭配方式相同。
　　
　　【原理二】：如果把多于m×n件东西，任意放进n个抽屉，那么至少有一个抽屉里有不少于m+1件东西。
　　
　　【例3】在口袋里有红色、蓝色和黄色的小球若干个，21个人轮流从袋中取球，每人每次取3个球。求证：这21个人中至少有3个人取出的颜色相同。
　　
　　证明：取出的三个球颜色是同一色的（即全红、全蓝或全黄）有三种不同的情况，是两色的（如两红一蓝等）有6种情况，是三色的（即红、蓝、黄三色小球各一个）只有一种情况，故共可分成10类。由抽屉原理二知道，把21个人所取出的球按颜色可归为这10类中，则必有一类至少有（个）。
　　
　　所以，21个人中至少有3人取出的球的颜色相同。
　　
　　运用抽屉原理只是肯定了“存在”、“总有”、“至少有”，却不能确切地指出哪个抽屉里存在多少。
　　
　　（二）怎样应用抽屉原理
　　
　　应用抽屉原理解题，一般有三个步骤：
　　
　　（1）列出分类对象；
　　
　　（2）找出分类规则（即构造抽屉）并证明每一类中的东西符合题意；
　　
　　（3）根据题意应用抽屉原理证明结论成立。
　　
　　【例4】给定997个整数1，3，5，…，1993，求证：从中任取500个不同的数，其中必有两个整数的和为1994。
　　
　　证明：把这997个整数中两数相加和为1994的每两个数分为一组，剩余的数为一组，可分为499组，为：
　　
　　｛1，1993｝，｛3，1991｝，…，｛995，999｝，｛997｝
　　
　　根据原理一，从这499组中任取500个数，必有两个数取自同一组中，那么这两个数之和为1994，问题得证。
　　
　　【例5】有21个自然数，且，求证：所有的差数中至少有四个相等。
　　
　　证明：以所有可能的差1，2，3，…，69作为抽屉扣住“差”，构成下列差数作为分类对象。
　　
　　对于可作出20个差数（即），对于可作出19个差数（即）…直至可作出一个差数，即（），因此共有1+2+3+…+19+20=210个差数。根据原理二，由[]+1=4，即至少有4个差相等，于是命题得证。
　　
　　【例6】求证：从任意n个自然数中可以找到若干个数，使它们的和是n的倍数。
　　
　　证明：以自然数被n除所得的余数0，1，2，…，n－1分类制造抽屉，扣住“和”构造下列和数：
　　
　　…
　　
　　若中有一个是n的倍数，问题得证。（略）
　　
　　可以看到，如直接给出了分类对象，只要恰当制造抽屉就可以了；如果没有直接给出分类对象，就要根据题意先构造出分类对

[1] [2] [3] 下一页