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