《2012江苏省数学竞赛《提优教程》教案：第10讲抽屉原理》由会员分享，可在线阅读，更多相关《2012江苏省数学竞赛《提优教程》教案：第10讲抽屉原理（14页珍藏版）》请在金锄头文库上搜索。
1、 第10讲 抽屉原理抽屉原理又叫鸽笼原理、狄里克雷( P. G. Dirchlet,18051895,德国)原理、重叠原理、鞋盒原理. 这一最简单的思维方式在解题过程中却可以演变出很多奇妙的变化和颇具匠心的运用. 抽屉原理常常结合几何、整除、数列和染色等问题出现, 抽屉原理I：把件东西任意放入n只抽屉里，那么至少有一个抽屉里有两件东西。抽屉原理II：把件东西放入个抽屉里，那么至少有一个抽屉里至少有件东西。抽屉原理III：如果有无穷件东西，把它们放在有限多个抽屉里，那么至少有一个抽屉里含无穷件东西。应用抽屉原理解题，关键在于构造抽屉。构造抽屉的常见方法有：图形分割、区间划分、整数分类（剩余类分类
2、、表达式分类等）、坐标分类、染色分类等等，下面举例说明。A类例题例1 如图，分别标有1到8的两组滚珠均匀放在内外两个圆环上，开始时相对的滚珠所标数字都不相同，当两个圆环按不同方向转动时，必有某一时刻，内外两环中至少有两对数字相同的滚珠相对分析 转动一周形成7个内外两环两对数字相同的时刻，以此构造抽屉。证明 内外两个圆环转动可把一个看成是相对静止的，只有一个外环在转动当外环转动一周后，每个滚珠都会有一次内环上标有相同数字的滚珠相对的时刻，这样的时刻将出现8次但一开始没有标有相同数字的滚珠相对，所以外环转动一周的过程中最多出现7个时刻内外标有相同数字的滚珠相对，故必有一个时刻内外两环中至少有两对数
3、字相同的滚珠相对说明 转动一周内外两环两对的8个时刻排除显然不合题意的初始时刻是本题的突破口。例2 7月份的天热得人都不想工作，只想呆在有空调的房间里可小张却没有办法休假，因为他是一个空调修理工，为了让更多人好好休息，他只能放弃自己的休息在过去的7月份里，小张每天至少修理了一台空调由于技术过硬，每一台空调都能在当天修理好8月1日结算的时候，大家发现小张在7月份一共修理了56台空调求证：存在连续的若干天（也可以是1天），在这些天里，小张恰好修理了5台空调分析 本题的难点在于将题中结论转化为抽屉原理的数学模型。证明 我们来考察“连续的若干天”里小张修理的空调台数设小张在第i天修理了xi台空调，其中
4、i=1，2，31则：x1x1+x2x1+x2+x3x1+x2+x31=56另外：x1+5x1+x2+5x1+x2+x3+5p)由此可见xp+1+xp+2+xq=5即从第p+1天开始到第q天修理的空调正好是5台例3 点为内任意一点，与点、的连线分别交对边于、求证：在、中必有一个不大于2，也必有一个不小于2分析 由寻求关于、的关系式展开分析。证明 利用以及，（其余两个类似）得：三个正数的和为1，必有一个不小于，也必有一个不大于不妨设，得，得所以在、中必有一个不大于2，也必有一个不小于2情景再现1在边长为1的正方形内任意放入九个点，求证：存在三个点，以这三个点为顶点的三角形的面积不超过。（1963年
5、北京市数学竞赛题）2质点沿直线方向往前跳，每跳一步前进米，而前进方向上距离起点每隔1米都有一个以此点为中心长为米的陷阱，证明该质点迟早要掉进某个陷阱里。3在坐标平面上任取5个整点（该点的横纵坐标都取整数），证明：其中一定存在两个整点，它们的连线中点仍是整点。B类例题例4（1）对于任意的5个正整数，证明其中必有3个数的和能被3整除；（2）对于任意的11个正整数，证明其中一定有6个数，它们的和能被6整除。分析 （1）可借助于3的同余类构造抽屉；（2）若仿造（1）借助于6的同余类构造抽屉情形较为烦琐，不妨借助于（1）的结论从中构造出能满足被2整除的数. 证明 （1）任何自然数除以3的余数只能是0、1
6、、2，不妨分别构造3个抽屉：，将这5个数按其余数放置到这3个抽屉中：若这5个正整数分布在这3个抽屉中，从3个抽屉中各取一个，其和必能被3整除；若这5个自然数分布在其中的2个抽屉中，则必有一个抽屉中含有至少3个数，取其3个，其和必能被3整除；若这5个自然数分布在其中的1个抽屉中，取其3个，其和必能被3整除。（2）设11个整数为，因为。先考虑被3整除的情形。由（1）知：在11个任意整数中，必存在：， 不妨设；同理，剩下的8个任意整数中，由（1）知，必存在：，不妨设；同理，其余的5个任意整数中，有：，设。 再考虑中存在两数之和被2整除。依据抽屉原理，这三个整数中，至少有两个是同奇或同偶，这两个同奇（
7、或同偶）的整数之和必为偶数.不妨设，则：，即。所以任意11个整数，其中必有6个数的和是6的倍数。例5910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种：1至少三行完全相同； 2至少有两组（四行），每组的两行完全相同。（北京市高中一年级数学竞赛1990年复赛试题）分析 每行7个位置有128种不同放置方式，以此构造抽屉.证明 910瓶红、蓝墨水，排成130行，每行7瓶。每行中的7个位置中的每个位置都有红、蓝两种可能，因而总计共有种不同的行式（当且仅当两行墨水瓶颜色及次序完全相同时称为“行式”相同） 任取130行中的129行，依抽屉原理可
8、知，必有两行（记为A，B）“行式”相同。在除A、B外的其余128行中若有一行P与A（B）“行式”相同，则P，A，B满足“至少有三行完全相同”；在其余（除A，B外）的128行中若没有与A（B）行式相同者，则128行至多有127种不同的行式，依抽屉原理，必有两行（不妨记为C、D）行式相同，这样便找到了（A，B）、（C，D）两组（四行），每组两行完全相同。说明 本题构造抽屉时用到分步计数原理，个“行式”是构造“抽屉”的关键。例6将平面上每个点以红蓝两色之一着色，证明：存在这样的两个相似三角形，它们的相似比为1995，并且每一个三角形的三个顶点同色。（1995年全国高中数学联赛试题）分析 构造相似比为
9、1995的9点组。证明 如图，作两个半径分别为1和1995的同心圆，在内圆上任取9个点，必有5点同色，记为A1，A2，A3，A4，A5。连半径交大圆于（），对B1，B2，B3，B4，B5，必有3点同色，记为，则与为三项点同色的相似三角形，相似比等于1995，满足题设条件。评析 这里连续用了两次抽屉原理（以染色作抽屉）。也可以一开始就取位似比为1995的9个位似点组（），对4个抽屉（红，红），（红，蓝），（蓝，红），（蓝，蓝）应用抽屉原理，得出必有3个位似点属于同一抽屉，从题目的证明过程中可以看出，相似比1995可以改换成另外一个任意的正整数、正实数。当然，不用同心圆也可证得，如在平面上取任三点
10、都不共线的9点，由抽屉原理必有5点同色，设为A、B、C、D、E；以A为位似中心，以1995为相似比作ABCDE的相似形ABCDE，则5点A,B,C,D,E中必有3点同色，设为BDE，则即为所求。情景再现4有苹果、梨、桔子若干个，任意分成9堆，求证一定可以找到两堆，其苹果数、梨数、桔子数分别求和都是偶数。5将平面上每个点以红蓝两色之一着色，证明：存在无数个内角为30，60，90的相似直角三角形，它们的相似比为1995，并且每一个三角形的三个顶点同色。6有17位科学家，其中每一个人和其他所有人通信，他们通信中讨论三个问题，且每两个科学家之间只讨论一个问题，求证至少有三个科学家相互之间讨论同一个问题
11、。C类例题例7给定一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。（第14届试题）分析 根据子集中各数之和构造抽屉.解 10个元素的集合就有个不同的构造子集的方法，也就是，它一共有1024个不同的子集，包括空集和全集在内。空集与全集显然不是考虑的对象，所以剩下个非空真子集。再看各个真子集中一切数字之和。用表示，则。这表明至多只有种不同的情况。由于非空真子集的个数是1022，1022846，所以一定存在两个子集A与B，使得A中各数之和=B中各数之和。若，则命题得证，若，即A与B有公共元素，这时只要剔除A与B中的一切公有元素，得出
12、两个不相交的子集A1与B1，很显然A1中各元素之和=B1中各元素之和，因此A1与B1就是符合题目要求的子集。例8设。求最小的自然数，使得的每个有个元素的子集都含有5个两两互素的数。（1991）分析 本题一方面要确定n的下界，另一方面须构造符合题意的集合.解 令，。记，利用容斥原理，容易算出。由于在中任取5个数必有两个数在同一个之中，从而它们不互素。所以。另一方面，令和中的一切素数，。易知。令，则，从而，在中任取217个数，由于，这217个数中必有25个数在中，于是一定存在，使得至少有个数在其中，这5个数显然是两两互素的。所以，于是可得。说明 在这个解法中，两次使用了抽屉原理，其关键都是构造抽屉
13、。由于第一步要确定的下界，既要找出尽可能大的的值，使得这个数中的任意五个数中至少有两个不互素。故这时必须构造4个“抽屉”，满足：每个“抽屉”中任意两个数都不互素；每个“抽屉”中包含尽可能多的数。在这些要求下构造出了集合，从而得到。在确定时，诸的构造要求是：中的任意两个数互素；。情景再现79条直线的每一条都把一个正方形分成两个梯形，而且它们的面积之比为23。证明：这9条直线中至少有3条通过同一个点。 8已知斐波那契数列：0，1，1，2，3，5，8，试问：在前100000002项中，是否会有某一项的末四位数字全是0？（不指第一项） 习题10 A1从集合中任取个数，证明：其中必有2个数互素。2任意给
14、定7个整数，求证：其中必有两个数，其和或差可被10整除。3任给7个实数，求证：其中必有至少两个数（记为） 满足。4某厂生产一种直径为的圆形零件，由加工水平可知零件直径之差不会超过，并且其直径不小于，现在要挑出两个零件，使它们的直径之差小于，若任意抽取，问至少要抽取多少件？5求证：在凸边形中，至少存在两个内角，使得。6我们称点为个点（）的重心。求证：平面上任意13个整点中，必有某4个点的重心为整点。 习题 B7从正整数集中，任意选出51个数。求证：其中一定有两个数，它们中的一个可以整除另一个。8从前39个正整数中任意取出8个数，证明：取出的数中一定有两个数，这两个数中大数不超过小数的倍。9已知整数。证明存在一个非零数列使得对和能被1001整除。10两两不等高的个人，随便排成一列，求证：可以从总挑选个人向前一步出列，使他们的身高从左到右是递增或递减的。 习题 C11某运动队的队员编号物重复地取自正整数1到100。如果其中任一队员的编号都不是另两队员编号之和，也不是另一队员编号的2倍，问这个运动队最多有几人？12我们称非空集合为集合的一个划分，如果：（1）；（2），。求最小的正整数，使得对的任意一个1
