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

【江苏省数学竞赛《提优教程》】第10讲 抽屉原理 抽屉原理又叫鸽笼原理、狄里克雷( P. G. Dirchlet,1805～1895,德国)原理、重叠原理、鞋盒原理. 这一最简单的思维方式在解题过程中却可以演变出很多奇妙的变化和颇具匠心的运用. 抽屉原理常常结合几何、整除、数列和染色等问题出现, 抽屉原理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+x3…x1+x2+…+x31=56． 另外：x1+5x1+x2+5x1+x2+x3+5…x1+x2+…+x31+5=61． 上面的两组数（共62个）均在1到61之间（包括这两个数），由抽屉原理，必有二个数是相等的，且相等的两个数应该来自不同的组．从而x1+x2+…+xq= x1+x2+…+xp+5．(qp) 由此可见 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个任意整数中