高中数学竞赛讲座抽屉原理.doc

抽屉原理抽屉原理又叫重叠原则或鸽原则，抽屉原则有如下几种情形。抽屉原则I 把件东西任意放入n只抽屉里，那么至少有一个抽屉里有两件东西。抽屉原则II 把件东西放入个抽屉里，那么至少有一个抽屉里至少有件东西。抽屉原则III 如果有无穷件东西，把它们放在有限多个抽屉里，那么至少有一个抽屉里含无穷件东西。利用抽屉原则解题时，其关键是如何利用题中已知条件构造出与题设密切相关的“抽屉”，下面通过例子说明抽屉原则的应用。例1在边长为1的正方形内任意放置5个点，试证：其中必有两个点，它们之间的距离不大于。证明：将边长为1的正方形划分成如图所示的四个边长为的小正方形，则每个小正方形中任意两点间的距离不大于，据抽屉原理：5个点放入四个正方形中，其中至少有一个正方形中至少有2个点，则这两个点间的距离不大于。例2证明：边长为1的的正三角形内任意放置5个点，其中必有两点，其距离不超过。证明：将边长为1的正三角形的各边中点连结起来，得到四个小正三角形，则每个小正三角形中任意两点间的距离不大于，据抽屉原理：5个点放入4个小正三角形中，其中至少有一个小正三角形中至少有2个点，则这两个点间的距离不超过。例3在边长为1的正方形中有任意九个点。试证：在以这些为顶点的各个三角形中，至少有一个三角形，其面积不大于。证明：将边长为1的正方形划分为如图所示的4个的小长方形，9个点放入4个小长方形中，则必有一个长方形中放入了至少3个点，设为,则三角形ABC的面积不大于过，证明如下：A作边的平行线交BC于，则：。例4求证：任给五个整数，必能从中选出三个，使得它们的和能被3整除。证明：因为任意一个整数被3除的余数只能是0，1，2，若任给的5个整数被3除的余数中0，1，2都出现，则余数为0，1，2的三个整数之和能被3整除；若5个数被3除的余数只出现0，1，2中的两个，则据抽屉原理知：必有3个整数的余数相同，而余数相同的3个数之和能被3整除。故任给五个整数，必能从中选出三个，使得它们的和能被3整除。例5求证：在中任选20个不同的整数，其中必有二整数之和为104。证明：将这34个自然数分成如下18个集合：，从中任选20个数，即从上述18个集合中选20个数，则必有一个集合中选了2个数，而这两个数的和为104。例6设是自然数随意打乱次序重新排列而成的一串数，是奇数。证明：总是偶数。证明：因为奇数，设，则中共有个奇数，从而，中共2（）=个奇数，这个奇数放入个括号中，则必有一个括号中的两个数均为奇数，从而这两个数之差为偶数，所以总是偶数。例7求证：对于任给的1987个自然数，从中总可以找到若干个数，使它们的和能被1987整除。证明：构造如下1987个和： ，若其中有一个和能被1987整除，则结论成立。否则上述1987个和除以1987的余数只能为，则其中必有两个和的余数相同，设为， （，则能被1987整除。例8在任意一次集会中，其中必有两个人，他们认识的人一样多，试证明之。证明：设参加集会的共有个人，制造如下抽屉：认识的人的人数为0的人属于集合；认识的人的人数为1的人属于集合；认识的人的人数为2的人属于集合，；认识的人的人数为的人属于集合这里得到个集合，可以证明，中至少有一个集合为空集。若中有一个元素，则其余个人最多认识个人，所以为空集；同理可证：若中有一个元素，则为空集。所以上述个集合，其实至多只有个集合。个人放入个集合中，其中必有一个集合中有两个人，结论得证。例9证明：在全世界所有人中任选六个人，其中一定有三个人，他们之间或者互相认识，或者互相不认识。证明：从6个人中任一个人记为，则其余5个同A或者认识，或者不认识，据抽屉原理：其中必有三个人同A认识，或者不认识；若有三个人同A认识，则这三个人或者互不认识，则结论成立。或者有两个人相互认识，则这两个人同A三人互相认识。若有三个人同A不认识，则这三个人或者互相认识，则结论成立，或者有两个人互不认识，则这两个人同A三人互不认识。结论成立。例10平面上有1987个点，任取三个点都有两点的距离小于1。求证：存在半径为1的圆，它至少盖住994个点。证明：在所给的1987个点中任选一点，记为，以为圆心作一个半径为1的圆，若其余的1986个点都在圆内，则结论成立；否则，在圆外的点中任一点，记为，以为圆心作一个半径为1的圆，则除去之外的其余1985个点必在圆或圆内，否则，至少存在一点在圆或圆的外部，则三点任两点间的距离均大于1，与条件矛盾，所以除去之外的其余1985个点必在圆或圆内。据抽屉原理：必有一个圆内至少有个点，加上圆心共994个点。知结论成立。例11十七个科学家，其中每一个和其他所有的人都通信。在他们的通信中，只讨论三个题目，而且每两个科学家之间只讨论一个题目。求证：至少有三个科学家相互之间在讨论同一个题目。证明：在17位科学家中任选一位，记为，则至少与其余16位科学家中的位科学家讨论同一题目，记为题目1，若这6位科学家中有两位科学家在讨论题目1，则结论成立；若这6位科学家都不讨论题目1，则他们只能讨论另外两题目，据抽屉原理：他们中至少有3位科学家在讨论同一题目。从而知：结论成立。例12一个国际社团的成员来自六个国家，共有1978人，用来编号。试证明：该社团至少有一个成员的编号与他的两个同胞的编号之和相等，或是其一个同胞编号的二倍。证明：证明：用反证法，即设每个国家成员编号中不存在我们将用抽屉原理引出矛盾。六个国家共有成员1978人，而1978=6，所以总有一个国家的成员至少有330人，设他们编号数为且作329个差 （1）由反证法假定，它们不能是国成员的编号数（若是国成员的编号，则，与反证法假定矛盾），所以这329个差数是另外五国成员的编号，由于329=5，因此有一个国家（记为）至少有66个成员的编号数落在差数（1）的范围，记这66个编号当选为由反证法假设又知道5个差为数 （2）不可能是国成员的编号数，也不可能是国的，因为若某国成员编号），则故，与反证假定型矛盾。于是（2）的数只能是另四国成员编号，由于 所以有某国的确良17位成员的编号数落在（2）中，记这些编，作6个差数 （3）则它们不是，也不是、国的成员的编号数，故必是另三个国家的。由于，因些有某国的6位成员的编数落在（3）中，记这6个编号数为，作五个差数， （4）同样道理知它们只能是其余两个国家成员的编号数，因些有国的3个成员编号数落在（4）中，这3个编号记为。又作差它不是国的成员编号数，所以是第六国成员的编号，此时不能是的成员编号，但总是某成员编号，这就矛盾了。可见原命题成立。例13在100个连续自然数中，任取51个数，试证明在这51个数中，一定有两个数，其中一个是另一个的倍数。证明：任意一个自然数都能表示成为（为自然数，为非负整数）的形式。将前100个自然数分为如下50个集合：，其中前100个自然数中的每个自然数都属于其中一个集合，而且只属于一个集合。据抽屉原理：从中选51个数，必有两个数是取自同一个集合，在同一个集合中，较大的数必是较小数的倍数。例14设是由1985个不同的自然数组成的集合，中的元素的素因子均不超26，求证：存在，使得是某个自然数的四次方。证明：不超过26的质数共9个：，所以这1985个正整数可表示为：的形式，考虑的奇偶性类型，共有种类型。在1985全正整数中可找出一对、有相同奇偶性，即与奇偶性相同，。然后在剩下的个数中又可以找出两个，他们的指数、也有相同的奇偶性。如此下去，由于，故可得513对、，且有（），最后，在上述的513个中，又必有两个、奇偶性相同，所以，设，则 ，。此时所求四个数为：,。例 15平面上有两个定点和及任意四点，求证：这四点中一定有两点（）使得。证明：显然：，（），即在内有四个实数，把分成三个子区间，由抽屉原理知：中必有两个数在同一区间中，不妨设为，则：，命题得证。例16任给7个实数，证明其中必有两个数，记为，满足证明：设7个实数为，令，将区间分为6个子区间，每个子区间的长度为，即为：，据抽屉原理知：必有两个角落在同一区间中，即其差在0与之间，由于这两个角的正切对应着7个实数中， 2个实数，则由，得，即：。练习1假设空间中有六个点，其中任意三点不共线，任意四点不共面，在每两点之间连结直线段后，将每一条线段或者染上红色，或者染上蓝色。求证：不论怎样染色，一定存在一个三角形，它的三边有相同的颜色。2任给无理数和正整数，一定可以找到一个有理数（其中），使得。3设是自然数，并且，则总能找到这样两个数与，使得。4设是任意一个具有性质的正整数的无穷序列，求证：这个序列中有无穷多个可以表示为，其中是适当的正整数，且。5设自然数有下面的性质：从中任取50个不同的数，这50个数中必有两个数之差等于7，这样的的最大的一个值是多少？6任何十个不同的两位数的集合必能选出两个不相交的子集，使每个子集内的各数之和相等。7设，求最小自然数使得的每个有个元素的子集含有5个两两互素的数（IMO（32）8设都是整数，则这些整数中必有一些相邻的项，如，使它们的和被100整除。9能否在行列的方格表的空格上分别填上三个数，使得每行每列及每条对角线上各数字之和各不相同。10在中，求证至少有一个数被整除，其中为大于1的奇数。11一个象棋大师有11个星期用来准备参加比赛，代决定每天至少下一盘棋，但为