【江苏省数学竞赛《提优教程》】第10讲 抽屉原理.doc

【江苏省数学竞赛提优教程】第10讲 抽屉原理抽屉原理又叫鸽笼原理、狄里克雷( P. G. Dirchlet,18051895,德国)原理、重叠原理、鞋盒原理. 这一最简单的思维方式在解题过程中却可以演变出很多奇妙的变化和颇具匠心的运用. 抽屉原理常常结合几何、整除、数列和染色等问题出现, 抽屉原理I：把 件东西任意放入n只抽屉里，那么至少有一个抽屉里有两件东西。抽屉原理II：把 件东西放入 个抽屉里，那么至少有一个抽屉里至少有 件东西。抽屉原理III：如果有无穷件东西，把它们放在有限多个抽屉里，那么至少有一个抽屉里含无穷件东西。应用抽屉原理解题，关键在于构造抽屉。构造抽屉的常见方法有：图形分割、区间划分、整数分类（剩余类分类、表达式分类等）、坐标分类、染色分类等等，下面举例说明。A类例题例1 如图，分别标有1到8的两组滚珠均匀放在内外两个圆环上，开始时相对的滚珠所标数字都不相同，当两个圆环按不同方向转动时，必有某一时刻，内外两环中至少有两对数字相同的滚珠相对分析 转动一周形成7个内外两环两对数字相同的时刻，以此构造抽屉。证明 内外两个圆环转动可把一个看成是相对静止的，只有一个外环在转动当外环转动一周后，每个滚珠都会有一次内环上标有相同数字的滚珠相对的时刻，这样的时刻将出现8次但一开始没有标有相同数字的滚珠相对，所以外环转动一周的过程中最多出现7个时刻内外标有相同数字的滚珠相对，故必有一个时刻内外两环中至少有两对数字相同的滚珠相对说明 转动一周内外两环两对的8个时刻排除显然不合题意的初始时刻是本题的突破口。例2 7月份的天热得人都不想工作，只想呆在有空调的房间里可小张却没有办法休假，因为他是一个空调修理工，为了让更多人好好休息，他只能放弃自己的休息在过去的7月份里，小张每天至少修理了一台空调由于技术过硬，每一台空调都能在当天修理好8月1日结算的时候，大家发现小张在7月份一共修理了56台空调求证：存在连续的若干天（也可以是1天），在这些天里，小张恰好修理了5台空调分析 本题的难点在于将题中结论转化为抽屉原理的数学模型。证明 我们来考察“连续的若干天”里小张修理的空调台数设小张在第i天修理了xi台空调，其中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年北京市数学竞赛题）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、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整除。依据抽屉原理， 这三个整数中，至少有两个是同奇或同偶，这两个同奇（或同偶）的整数之和必为偶数.不妨设 ，则： ，即 。所以任意11个整数，其中必有6个数的和是6的倍数。例5910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种：1至少三行完全相同； 2至少有两组（四行），每组的两行完全相同。（北京市高中一年级数学竞赛1990年复赛试题）分析 每行7个位置有128种不同放置方式，以此构造抽屉.证明 910瓶红、蓝墨水，排成130行，每行7瓶。每行中的7个位置中的每个位置都有红、蓝两种可能，因而总计共有 种不同的行式（当且仅当两行墨水瓶颜色及次序完全相同时称为“行式”相同） 任取130行中的129行，依抽屉原理可知，必有两行（记为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年全国高中数学联赛试题）分析 构造相似比为1995的9点组。证明 如图，作两个半径分别为1和1995的同心圆，在内圆上任取9个点，必有5点同色，记为A1，A2，A3，A4，A5。连半径 交大圆于 （ ），对B1，B2，B3，B4，B5，必有3点同色，记为 ，则 与 为三项点同色的相似三角形，相似比等于1995，满足题设条件。评析 这里连续用了两次抽屉原理（以染色作抽屉）。也可以一开始就取位似比为1995的9个位似点组 （ ），对4个抽屉（红，红），（红，蓝），（蓝，红），（蓝，蓝）应用抽屉原理，得出必有3个位似点属于同一抽屉，从题目的证明过程中可以看出，相似比1995可以改换成另外一个任意的正整数、正实数。当然，不用同心圆也可证得，如在平面上取任三点都不共线的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位科学家，其中每一个人和其他所有人通信，他们通信中讨论三个问题，且每两个科学家之间只讨论一个问题，求证至少有三个科学家相互之间讨论同一个问题。C类例题例7给定一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。（第14届 试题）分析 根据子集中各数之和构造抽屉.解 10个元素的集合就有 个不同的构造子集的方法，也就是，它一共有1024个不同的子集，包括空集和全集在内。空集与全集显然不是考虑的对象，所以剩下 个非空真子集。再看各个真子集中一切数字之和。用 表示，则 。这表明 至多只有 种不同的情况。由于非空真子集的个数是1022，1022846，所以一定存在两个子集A与B，使得A中各数之和=B中各数之和。若 ，则命题得证，若 ，即A与B有公共元素，这时只要剔除A与B中的一切公有元素，得出两个不相交的子集A1与B1，很显然A1中各元素之和=B1中各元素之和，因此A1与B1就是符合题目要求的子集。例8设 。求最小的自然数 ，使得 的每个有 个元素的子集都含有5个两两互素的数。（1991 ）分析 本题一方面要确定n的下界，另一方面须构造符合题意的集合.解 令 ， 。记 ，利用容斥原理，容易算出 。由于在 中任取5个数必有两个数在同一个 之中，从而它们不互素。所以 。另一方面，令 和 中的一切素数 ， ， ， ， ， 。易知 。令 ，则 ，从而 ，在 中任取217个数，由于 ，这217个数中必有25个数在 中，于是一定存在 ，使得至少有 个数在其中，这5个数显然是两两互素的。所以 ，于是可得 。说明 在这个解法中，两次使用了抽屉原理，其关键都是构造抽屉。由于第一步要确定 的下界，既要找出尽可能大的 的值，使得这 个数中的任意五个数中至少有两个不互素。故这时必须构造4个“抽屉”，满足：每个“抽屉”中任意两个数都不互素；每个“抽屉”中包含尽可能多的数。在这些要求下构造出了集合 ，从而得到 。在确定 时，诸 的构造要求是： 中的任意两个数互素； 。情景再现79条直线的每一条都把一个正方形分成两个梯形，而且它们的面积之比为23。证明：这9条直线中至少有3条通过同一个点。 8已知斐波那契数列：0，1，1，2，3，5，8，试问：在前100000002项中，是否会有某一项的末四位数字全是0？（不指第一项） 习题10 A1从集合 中任取 个数，证明：其中必有2个数互素。2任意给定7个整数，求证：其中必有两个数，其和或差可被10整除。3任给7个实数，求证：其中必有至少两个数（记为 ） 满足 。4某厂生产一种直径为 的圆形零件，由加工水平可知零件直径之差不会超过 ，并且其直径不小于 ，现在要挑出两个零件，使它们的直径之差小于 ，若任意抽取，问至少要抽取多少件？5求证：在凸 边形中，至少存在两个内角 ，使得 。6我们称点 为 个点 （ ）的重心。求证：平面上任意13个整点中，必有某4个点的重心为整点。 习题 B7从正整数集 中，任意选出51个数。求证：其中一定有两个数，它们中的一个可以整除另一个。8从前39个正整数中任意取出8个数，证明：取出的数中一定有两个数，这两个数中大数不超过小数的 倍。9已知整数 。证明存在一个非零数列 使得对 和 能被1001整除。10两两不等高的 个人，随便排成一列，求证：可以从总挑选 个人向前一步出列，使他们的身高从左到右是递增或递减的。 习题 C11某运动队的队员编号物重复地取自正整数1到100。如果其中任一队员的编号都不是另两队员编号之和，也不是另一队员编号的2倍，问这个运动队最多有几人？12我们称非空集合 为集合 的一个 划分，如果：（1） ；（2） ， 。求最小的正整数 ，使得对 的任意一个13划分 ，一定存在某个集合 ，在 中有两个元素 满足 。本节“情景再现”解答：1证明：根据题意，构造的“抽屉”中至少要有3点，且以这三个点为顶点的三角形的面积不超过 。如图，四等分正方形，得到4个矩形。在正方形内任意放入九个点，则一定存在一个矩形，其内至少存在 个点，设三点为A、B、C，具体考察其所在的矩形（如图），过三点分别作矩形长边的平行线，过A的平行线交BC于A点，设A点到矩形长边的距离为 ，则ABC的面积 。2证明：若该质点跳了 步后掉进了第 个陷阱里，则本题等价于：存在正整数 ，使得 。把区间 分成1000等分，每一等分都是左闭右开的小区间，它们的长都是 。考虑1001个实数 ， ，由于 ，则这1001个实数都在区间 内。由抽屉原理，必有两个实数设为 和 都在同一小区间内（不妨设 ）。于是有 ，即 ，设 ， ，则有 。从而当质点跳了 步后掉进了第 个陷阱里。3解：由中点坐标公式知，坐标平面两点 、 的中点坐标是 。欲使 都是整数，当且仅当 与 ， 与 的奇偶性相同。坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数，偶数），（奇数，偶数），（偶数，奇数）以此构造四个“抽屉”，则在坐标平面上任取五个整点，那么至少有两个整点，属于同一个“抽屉”因此它们连线的中点就必是整点。 4证明：因为每一堆里的每一种水果数或为奇数或为偶数（两个抽屉），而9=24+1，故对于苹果，9堆中必有5堆的奇偶性相同；这5堆对于梨数来说，由于5=22+1，故必有3堆的奇偶性相同；这3堆对于桔子数也必有2堆的奇偶性相同。于是，就找到这样的两堆，它们的苹果数、梨数，桔子数的奇偶性都分别相同，从而其和数分别都是偶数。 5任取aR+，以a为边作等边三角形，则必有两点同色，记为A，B同红色，以AB为直径作一圆，再作圆内接正六边形AC1C2BC3C4（如图），当Ci中有红点时ACiB即为所求；当Ci中无红点即 全为蓝色时，RtC1C2C3即为所求。再由a的任意性知，这样的三角形有无数个。 6科学家对应一个点，两科学家之间讨论的问题对应两点间连线的颜色，本题转化为染色问题：完全十七边形K17用红黄蓝三色染其边，必存在同色三角形。由A1出发有16条边，用三色染，必有六条同色（设为红色），不妨认为A1 A2，A1 A3，. A1 A7为红色；若A2，A3，. A7之间有红色连线，则存在红色三角形，否则六点A2，A3，. A7两两连线得K6，用黄蓝两色染边，必存在同色三角形。7证明：设正方形为ABCD，E、F分别是AB，CD的中点。设直线 把正方形ABCD分成两个梯形ABGH和CDHG，并且与EF相交于P（如图）。梯形ABGH的面积梯形CDHG的面积=23 ，EP是梯形ABGH的中位线，PF是梯形CDHG的中位线，由于梯形的面积=中位线梯形的高，并且两个梯形的高相等（AB=CD），所以梯形ABGH的面积梯形CDHG的面积=EPPF，也就是EPPF=23 。这说明，直线L通过EF上一个固定的点P，这个点把EF分成长度为23的两部分。这样的点在EF上还有一个，如图上的Q点（FQQE=23）。 同样地，如果直线 与AB、CD相交，并且把正方形分成两个梯形面积之比是23，那么这条直线必定通过AD、BC中点连线上的两个类似的点（五等分点）。 这样，在正方形内就有4个固定的点，凡是把正方形面积分成两个面积为23的梯形的直线，一定通过这4点中的某一个。根据抽屉原理，必有一个点，至少有 条直线通过此点。 8注意到斐波那契数列是严格递增的，故满足要求的项至少是五位以上的数再注意到斐波那契数列的特点是每一项等于前面两项的和，而100000002=? ，我们可以以相邻两项的末四位数字所成的有序对为抽屉，而末四位数字组成的数一共有 个（不足四位前面补0），抽屉的个数正好是 现有 个数对，至少有两个数对，它们的末四位完全相同设为 ， ，（ ）即有： ，且 于是 ，而 就是说 和 的末四位相同，从而数对 、 的末四位相同（事实上我们得到了两个连续三个数， 和 对应末四位全部相同）依次类推，我们可以得到 和 的对应末四位全部相同，从而 与 （即0）的末四位相同，所以 的末四位全为0 “习题10”解答：1构造 个抽屉： 、 、 ，则 个数中必有两个数属于同一个抽屉，即此两数互素2任意整数除以10的余数，只能是0，1，2，3，4，5，6，7，8，9这十个数中的一个。 不妨从余数角度出发，考虑构造合适的抽屉。（由题目分析，要求我们构造六个抽屉，并且抽屉中的余数和或差只能是0）由这10个余数，构造6个抽屉： ， ， ， ， ， 则任意7个不同整数除以10后所得余数（即7个元素），任意放入这6个抽屉，其中必有一个抽屉包含有其中2个不同整数除以10后所得的2个余数。若这两个余数同属于抽屉0或抽屉5，则此二余数差是0，即这两个余数对应的整数之差可以被10整除。若这两个余数同属于 ， ， ， 这四个抽屉中的任意一个，则这两个余数和是10，即这两个余数所对应整数之和是10的倍数。可见，任意7个不同的整数中，必有两个数的和或差是10的倍数。3记7个数为 、 、 ，其中 ，将区间 等分成6个区间： 、 、 、 、 、 ，则7个角必有两个属于同一区间，不妨设 ，设 ，则 ，即存在两个数 满足 。4首先指出取51件是不行的。当零件的直径成等差数列： 时，每两件的直径之差都不小于 。再证取52件时成立。将区间 作51等分，则52个零件中必有两件的直径属于同一等分区间，有直径之差 ，所以最少要取52件。5首先证明凸多边形至多有5个内角小于 。用反证法，若有6个内角小于 ，则其内角和 ，这与 矛盾。于是，凸 边形至少有 个内角在区间 内，它们的余弦值在 内。将区间 平均分成 个小区间，每个小区间的长为 。于是 个角的余弦值分布在 个小区间内，至少有两个角的余弦值在同一个小区间内，设为 、 ，因此 。6按照坐标的奇偶性构造4个抽屉：（奇数、奇数），（偶数，偶数），（奇数，偶数），（偶数，奇数），由抽屉原理必有一个抽屉里至少有 个点，这4点的重心显然是整点。7证明：因为任何一个正整数都能表示成一个奇数与2的方幂的积，并且表示方法唯一，所以我们可把 的正整数分成如下50个抽屉（因为 中共有50个奇数）：（1） ；（2） ；（3） ；（4） ；（5） ；（25） ；（26） ；（50） 。这就构造了50个抽屉， 中的每一个数都在其中的1个抽屉内。从中任取51个数，据抽屉原理，其中必定至少有两个数属于同一个抽屉，即属于 号中的某一个抽屉，显然在这25个抽屉中的任何同一个抽屉内的两个数，一个是另一个的倍数。8证明：把前39个正整数分成下面7组： 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； 26，27，28，29，30，31，32，33，34，35，36，37，38，39； 因为从前39个自然数中任意取出8个数，所以至少有两个数取自上面第组到第组中的某同一组，这两个数中大数就不超过小数的1.5倍。 评析：本题可以改造为如下一系列