数学中的抽屉原理

先看简单的事实：把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的倍数，问题得证。（略）
　　
　　可以看到，如直接给出了分类对象，只要恰当制造抽屉就可以了；如果没有直接给出分类对象，就要根据题意先构造出分类对象。
　　
　　有些问题要多次应用抽屉原理才能解决。
　　
　　【例7】对任意给的84个互异的正整数，试证其中一定存在四个正整数，仅用减号、乘号和括号将它们适当综合为一个算式，其结果为1992的倍数。
　　
　　提示：1992=83×24
　　
　　证明：由例1可知，在这84个互异的正整数中，至少有两个数被83除的余数相同，不妨设，则：
　　
　　83|（）
　　
　　在这82个互异的正整数中，至少有两数被24除的余数相同，不妨设
　　
　　则24|（）
　　
　　因为（83，24）=1
　　
　　所以，83×24|（）（）
　　
　　即：1992|（）（）
　　
　　则、、、即为所求证存在的四个互异的正整数。
　　
　　【例8】从前30个自然数中最少要（不看这些数而以任意方式）取出几个数，才能保证取出的数中能找到两个数，其中较大的数是较小数的倍数？
　　
　　分析与解答：
　　
　　设想有30张分别写1、2、3、…、30的卡片，背面向上放在桌子上，从中任意抽取，如果抽取两张，譬如说可能抽到3，5，它们之间没有倍数关系，但也也许抽到2、4，它们之间就有倍数关系了。看来只抽两张，不能保证出现题设的结果。
　　
　　抽3张呢？如果抽出了4、5、22，那很遗憾。
　　
　　抽4张呢？如果抽出了16、3、7、11，也不成。这样想下去，不容易找出题目所说的“至少取几个数”中的最小数，看来要想个好办法。
　　
　　把前30个自然数分成下列15组：
　　
　　｛1，2，4，8，16｝
　　
　　｛3，6，12，24｝
　　
　　｛5，10，20｝
　　
　　｛7，14，28｝
　　
　　｛9，18｝
　　
　　｛11，22｝
　　
　　｛13，26｝
　　
　　｛15，30｝
　　
　　｛17｝；｛19｝；｛21｝；｛23｝；｛25｝；｛27｝；｛29｝。
　　
　　根据抽屉原则知：任意取出16个数，至少有两个取出的数落入同一个组内，当然是落入前面8组中的某组，这两个数就有倍数关系。这说明任意取出16个数后可以满足题目的要求，所以，从前30个自然数中至少取16个数，就可保证取出的数中有两个数，它们之间有倍数关系。
　　
　　【例9】能否在8行8列的方格表（如图）的每一个空格中分别填上1，2，3这3个数字中的任意一个，使得每行、每列及对角线AC、BD上的各个数字的和互不相等？并对你的结论加以说明。
　　
　　分析与解答：
　　
　　这个问题初看起来似乎与抽屉原则关系不密切，下面我们先看图：图中8行8列及两条对角线共18条“线”，每条线上都填有8个数字，要使各条线上的数字和都不相同，那么每条线上数字和取不同值的可能性必须超过18种。下面我们来看各条线上取不同值的可能情况有多少种。
　　
　　如果一条线上的8个数字都填3，那么数字和最大值24，由于数字和都是整数，所以从8到24共有17种不同的值。我们把数字和的17种不同的值当作17个抽屉，而把18条线分到17个抽屉里，一定有一个抽屉里有两条和两条以上的线，即18条线上的数字和至少有两个是相同的。
　　
　　因此，不可能使18条线上数字和互不相同。
　　
　　【例10】从前25个自然数中任意取出7个数，证明：取出的数中一定有两个数，这两个数中大数不超过小数的1.5倍。
　　
　　证明：把前25个自然数从1开始，连续的几个数为一组，其中最大的数小于最小的数的1.5倍，最少可以分成下面6组：
　　
　　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．
　　
　　因为从前25个自然数中任意取出7个数，所以至少有两个数取自上面第2组到第6组中的某同一组，这两个数中大数就不超过小数的1.5倍。
　　
　　说明：把前25个自然数分成的6组可以看成6个抽屉，所任意取的7个数看成7个苹果，那么至少有两个苹果要取自同一个抽屉。注意到每一组数中任何两个数的比值都不超过1.5，所以当判定一定有两个数取自同一组时，这两个数就符合题目要求。
　　
　　上面证明中，分组方法是关键，分组的目的就是为使用抽屉原则，分组是在构造抽屉。
　　
　　【例11】1010人考试，总分为50501（百分制），证明至少有11人同分。
　　
　　证明：考试的得分可能为0，1，2，…，99，100分，每一得分可以看作一个抽屉，那么共有101个抽屉。假设一个抽屉内最多10人，则总分最多为：
　　
　　10×（0＋1＋2＋…＋100）=50500＜50501
　　
　　与已知矛盾，故结论正确。
　　
　　说明：本题的证明使用的是反证法，就是先假设要证明的结论不成立，然后根据已知条件推出与已知相矛盾的结论，从而说明假设是错误的，要证结论是正确的。(来源：拥有梦想是幸福的的BLOG)