抽屉问题

网上购物 就到“淘宝网购物” http://www.66gw.com.cn 抽屉原理最先是由 19 世纪的德国数学家迪里赫莱(Dirichlet)运用于解决数学问题的,所以又称"迪里赫莱原理",也有 称"鸽巢原理"的.这个原理可以简单地叙述为"把10个苹果,任意分放在 9个抽屉里,则至少有一个抽屉里含有两个或两 个以上的苹果".这个道理是非常明显的,但应用它却可以解决许多有趣的问题,并且常常得到一些令人惊异的结果.抽 屉原理是国际国内各级各类数学竞赛中的重要内容,本讲就来学习它的有关知识及其应用. 抽屉原理的基本形式 定理 1,如果把 n+1个元素分成 n 个集合,那么不管怎么分,都存在一个集合,其中至少有两个元素. 证明:(用反证法)若不存在至少有两个元素的集合,则每个集合至多 1 个元素,从而 n 个集合至多有 n 个元素,此与共有 n+1个元素矛盾,故命题成立. 在定理 1 的叙述中,可以把"元素"改为"物件",把"集合"改成"抽屉",抽屉原理正是由此得名 . 同样,可以把"元素"改成"鸽子",把"分成 n 个集合"改成"飞进 n 个鸽笼中"."鸽笼原理"由此得名. 解答抽屉原理的关键： 假设有 3 个苹果放入 2 个抽屉中，则必然有一个抽屉中有 2 个苹果，她的一般模型可以表述为： 第一抽屉原理：把（mn+1）个物体放入 n 个抽屉中，其中必有一个抽屉中至少有（m+1）个物体。 若把 3 个苹果放入 4 个抽屉中，则必然有一个抽屉空着，她的一般模型可以表述为： 第二抽屉原理：把（mn－1）个物体放入 n 个抽屉中，其中必有一个抽屉中至多有（m—1）个物体。 抽屉原理一 把 4 只苹果放到 3 个抽屉里去，共有 4 种放法，不论如何放，必有一个抽屉里至少放进两个苹果。 同样，把 5 只苹果放到 4 个抽屉里去，必有一个抽屉里至少放进两个苹果。 更进一步，我们能够得出这样的结论：把 n＋1 只苹果放到 n 个抽屉里去，那么必定有一个抽屉里至少放进两 个苹果。这个结论，通常被称为抽屉原理。 利用抽屉原理，可以说明（证明）许多有趣的现象或结论。不过，抽屉原理不是拿来就能用的，关键是要应用所 学的数学知识去寻找“抽屉”，制造“抽屉”，弄清应当把什么看作“抽屉”，把什么看作“苹果”。 抽屉原理二 这里我们讲抽屉原理的另一种情况。先看一个例子：如果将 13 只鸽子放进 6 只鸽笼里，那么至少有一只笼子要放 3 只或更多的鸽子。道理很简单。如果每只鸽笼里只放 2 只鸽子，6 只鸽笼共放 12 只鸽子。剩下的一只鸽子无论放入哪 只鸽笼里，总有一只鸽笼放了 3 只鸽子。这个例子所体现的数学思想，就是下面的抽屉原理 2。 抽屉原理 2：将多于 m×n 件的物品任意放到 n 个抽屉中，那么至少有一个抽屉中的物品的件数不少于 m+1。 说明这一原理是不难的。假定这 n 个抽屉中，每一个抽屉内的物品都不到（m＋1）件，即每个抽屉里的物品都不 多于 m 件，这样，n 个抽屉中可放物品的总数就不会超过 m×n 件。这与多于 m×n 件物品的假设相矛盾。这说明一开 始的假定不能成立。所以至少有一个抽屉中物品的件数不少于 m＋1。 从最不利原则也可以说明抽屉原理 2。为了使抽屉中的物品不少于（m＋1）件，最不利的情况就是 n 个抽屉中每 个都放入 m 件物品，共放入（m×n）件物品，此时再放入 1 件物品，无论放入哪个抽屉，都至少有一个抽屉不少于（m ＋1）件物品。这就说明了抽屉原理 2。 不难看出，当 m＝1 时，抽屉原理 2 就转化为抽屉原理 1。即抽屉原理 2 是抽屉原理 1 的推广。 我们很容易理解这样一个事实：把 3 只苹果放到两个抽屉中，肯定有一个抽屉中有 2 只或 2 只以上的苹果。用数学语 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 言表达这一事实，就是：将n+1 个元素放入 n 个集合内，则一定有一个集合内有两个或两个以上的元素（n 为正整数）。 这就是抽屉原理，也称为“鸽笼（巢）”原理。这一原理最先是由德国数学家狄里克雷明确提出来的，因此，称之为狄 里克雷原理。 抽屉原理还有另外的常用形式： 抽屉原理 2：把 m 个元素任意放入 个集合里，则一定有一个集合里至少有 k 个元素，其中： n n m( )< 抽屉原理 3：把无穷多个元素放入有限个集合里，则一定有一个集合里含有无穷多个元素。 抽屉原理又叫重叠原则，抽屉原则有如下几种情形。 抽屉原则①：把 n+1件东西任意放入 n 只抽屉里，那么至少有一个抽屉里有两件东西。 抽屉原则②：把 m 件东西放入 n 个抽屉里，那么至少有一个抽屉里至少有[m/n]件东西。 抽屉原则③：如果有无穷件东西，把它们放在有限多个抽屉里，那么至少有一个抽屉里含无穷件东西。 利用抽屉原则解题时，其关键是如何利用题中已知条件构造出与题设密切相关的“抽屉” 基础班 1. 证明：从 1，3，5，……，99中任选 26个数，其中必有两个数的和是 100。 2. 某旅游车上有 47 名乘客，每位乘客都只带有一种水果。如果乘客中有人带梨，并且其中任何两位乘客中至少有 一个人带苹果，那么乘客中有______人带苹果。 （A）46 （B）24 （C）23 （D）1 3. 一些苹果和梨混放在一个筐里，小明把这筐水果分成了若干堆，后来发现无论怎么分，总能从这若干堆里找到两 堆，把这两堆水果合并在一起后，苹果和梨的个数是偶数，那么小明至少把这些水果分成了_______堆。 （A）3 （B）4 （C）5 （D）6 4. 有黑色、白色、蓝色手套各 5 只（不分左右手），至少要拿出_____只（拿的时候不许看颜色），才能使拿出的手 套中一定有两双是同颜色的。 （A）4 （B）5 （C）6 （D）7 5. 在边长为 2 厘米的正方形中至少放入几个点，可以保证其中必定有三个点，使得以它们为顶点的三角形的面积不 大于 0.5平方厘米。 1. 解析：将这 50 个奇数按照和为 100，放进 25个抽屉：（1，99），（ 3，97），（ 5，95），……，（49 ，51）。根据抽 屉原理，从中选出 26 个数，则必定有两个数来自同一个抽屉，那么这两个数的和即为 100。 2. 解析：由题意，不带苹果的乘客不多于一名，但又确实有不带苹果的乘客，所以不带苹果的乘客恰有一名，所以 带苹果的就有 46 人。 3. 解析：要求把其中两堆合并在一起后，苹果和梨的个数一定是偶数，那么这两堆水果中，苹果和梨的奇偶性必须 相同。对于每一堆苹果和梨，奇偶可能性有 4 种：（奇，奇），（奇，偶），（偶，奇），（偶，偶），所以根据抽屉原理可 知最少分了 4+1=5 筐。 4. 解析：考虑最坏情况，假设拿了 3 只黑色、1 只白色和 1 只蓝色，则只有一双同颜色的，但是再多拿一只，不论 什么颜色，则一定会有两双同颜色的，所以至少要那 6 只。 5. 解析：将大正方形分成四个以 1 厘米为边长的小正方形。要使得存在一个三角形的面积不超过 0.5 平方厘米，只 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 要保证存在三个点在小正方形的内部或小正方形的边上，因此，根据抽屉原理，至少需要 个点。 例 1. 已知在边长为 1 的等边三角形内(包括边界)有任意五个点(图 1).证明:至少有两个点之间的距离不大于 分析:5 个点的分布是任意的.如果要证明"在边长为 1 的等边三角形内(包括边界)有 5 个点,那么这 5 个点中一定有距 离不大于的两点",则顺次连接三角形三边中点,即三角形 的三条中位线,可以分原等边三角形为 4 个全等的边长为的小等边三角形,则 5 个点中必有 2 点位于同一个小等边三角 形中(包括边界),其距离便不大于. 以上结论要由定理"三角形内(包括边界)任意两点间的距离不大于其最大边长 "来保证,下面我们就来证明这个定理. 如图 2,设 BC是△ABC的最大边,P,M 是△ABC内(包括边界)任意两点,连接 PM,过 P 分别作 AB,BC边的平行线,过 M作 AC 边的平行线,设各平行线交点为 P,Q,N,那么 ∠PQN=∠C,∠QNP=∠A 因为 BC≥AB,所以∠A≥∠C,则∠QNP≥∠PQN,而∠QMP≥∠QNP≥∠PQN(三角形的外角大于不相邻的内角 ),所以 PQ≥ PM.显然 BC≥PQ,故 BC≥PM. 由此我们可以推知,边长为的等边三角形内 (包括边界)两点间的距离不大于. 说明: (1)这里是用等分三角形的方法来构造"抽屉".类似地,还可以利用等分线段,等分正方形的方法来构造"抽屉". 例如"任取 n+1 个正数 ai,满足 0n,由抽屉 原则,结论就是必然的了.给 n 以具体值,就可以构造出不同的题目.例 2 中的 n 取值是 50,还可以编制相反的题目,如:" 从前 30 个自然数中最少要(不看这些数而以任意方式地)取出几个数,才能保证取出的数中能找到两个数,其中较大的 数是较小的数的倍数 " (2)如下两个问题的结论都是否定的(n均为正整数)想一想,为什么 ①从 2,3,4,…,2n+1 中任取 n+1 个数,是否必有两个数,它们中的一个是另一个的整数倍 ②从 1,2,3,…,2n+1 中任取 n+1 个数,是否必有两个数,它们中的一个是另一个的整数倍 你能举出反例,证明上述两个问题的结论都是否定的吗 (3)如果将(2)中两个问题中任取的 n+1个数增加 1个,都改成任取 n+2个数,则它们的结论是肯定的还是否定的 你能判 断证明吗 例 3.从前 25 个自然数中任意取出 7 个数,证明:取出的数中一定有两个数,这两个数中大数不超过小数的 1.5倍. 证明:把前 25 个自然数分成下面 6 组: 1; ① 2,3; ② 4,5,6; ③ 7,8,9,10; ④ 11,12,13,14,15,16; ⑤ 17,18,19,20,21,22,23, ⑥ 因为从前 25个自然数中任意取出 7个数,所以至少有两个数取自上面第②组到第⑥组中的某同一组,这两个数中大数就 不超过小数的 1.5 倍. 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 说明: (1)本题可以改变叙述如下:在前 25 个自然数中任意取出 7 个数,求证其中存在两个数,它们相互的比值在内. 显然,必须找出一种能把前 25个自然数分成 6(7-1=6)个集合的方法,不过分类时有一个限制条件:同一集合中任两个数 的比值在内,故同一集合中元素的数值差不得过大 .这样,我们可以用如上一种特殊的分类法:递推分类法: 从 1 开始,显然 1 只能单独作为 1 个集合{1};否则不满足限制条件. 能与 2 同属于一个集合的数只有 3,于是{2,3}为一集合. 1．一副扑克牌有四种花色，每种花色各有 13 张，现在从中任意抽牌。问最少抽几张牌，才能保证有 4 张牌是同一种 花色的？ A．12 B．13 C．15 D．16 【解析】根据抽屉原理，当每次取出 4 张牌时，则至少可以保障每种花色一样一张，按此类推，当取出 12 张牌时， 则至少可以保障每种花色一样三张，所以当抽取第 13张牌时，无论是什么花色，都可以至少保障有 4 张牌是同一种花 色，选 B。 2．从 1、2、3、4……、12 这 12 个自然数中，至少任选几个，就可以保证其中一定包括两个数，他们的差是 7？ A．7 B．10 C．9 D．8 【解析】在这 12 个自然数中，差是 7 的自然树有以下 5 对：｛12，5｝｛11，4｝｛10，3｝｛ 9，2｝｛ 8，1｝。另外， 还有 2 个不能配对的数是｛6｝｛7｝。可构造抽屉原理，共构造了 7 个抽屉。只要有两个数是取自同一个抽屉，那么它 们的差就等于 7。这 7 个抽屉可以表示为｛12，5｝｛11，4｝｛ 10，3｝｛9，2｝｛ 8，1｝｛ 6｝｛ 7｝，显然从 7 个抽屉中取 8 个数，则一定可以使有两个数字来源于同一个抽屉，也即作差为 7，所以选择 D。 例 1 某幼儿班有 40 名小朋友，现有各种玩具 122 件，把这些玩具全部分给小朋友，是否会有小朋友得到 4 件或4 件以上的玩具？ 分析与解：将40 名小朋友看成 40 个抽屉。今有玩具 122 件，122=3×40＋2。应用抽屉原理 2，取n＝40，m＝3， 立即知道：至少有一个抽屉中放有 4 件或 4 件以上的玩具。也就是说，至少会有一个小朋友得到 4 件或 4 件以上 的玩具。 例 2 一个布袋中有 40 块相同的木块，其中编上号码 1，2，3，4 的各有 10 块。问：一次至少要取出多少木块， 才能保证其中至少有 3 块号码相同的木块？ 分析与解：将 1，2，3，4 四种号码看成 4 个抽屉。要保证有一个抽屉中至少有 3 件物品，根据抽屉原理 2，至 少要有 4×2＋1=9（件）物品。所以一次至少要取出 9 块木块，才能保证其中有 3 块号码相同的木块。 例 3 六年级有 100 名学生，他们都订阅甲、乙、丙三种杂志中的一种、二种或三种。问：至少有多少名学生订阅 的杂志种类相同？ 分析与解：首先应当弄清订阅杂志的种类共有多少种不同的情况。 订一种杂志有：订甲、订乙、订丙 3 种情况； 订二种杂志有：订甲乙、订乙丙、订丙甲 3 种情况； 订三种杂志有：订甲乙丙 1 种情况。 总共有 3＋3＋1=7（种）订阅方法。我们将这 7 种订法看成是 7 个“抽屉”，把 100 名学生看作 100 件物品。 因为 100＝14×7＋2。根据抽屉原理 2，至少有 14＋1＝15（人）所订阅的报刊种类是相同的。 例 4 篮子里有苹果、梨、桃和桔子，现有 81 个小朋友，如果每个小朋友都从中任意拿两个水果，那么至少有多 少个小朋友拿的水果是相同的？ 分析与解：首先应弄清不同的水果搭配有多少种。两个水果是相同的有 4 种，两个水果不同有 6 种：苹果和梨、 苹果和桃、苹果和桔子、梨和桃、梨和桔子、桃和桔子。所以不同的水果搭配共有 4＋6＝10（种）。将这 10 种 搭配作为 10 个“抽屉”。 81÷10=8……1（个）。 根据抽屉原理 2，至少有 8＋1＝9（个）小朋友拿的水果相同。 例 5 学校开办了语文、数学、美术三个课外学习班，每个学生最多可以参加两个（可以不参加）。问：至少有多 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 少名学生，才能保证有不少于 5 名同学参加学习班的情况完全相同？ 分析与解：首先要弄清参加学习班有多少种不同情况。不参加学习班有 1 种情况，只参加一个学习班有 3 种情况 ， 参加两个学习班有语文和数学、语文和美术、数学和美术 3 种情况。共有 1＋3＋3＝7（种）情况。将这 7 种情 况作为 7 个“抽屉”，根据抽屉原理 2，要保证不少于 5 名同学参加学习班的情况相同，要有学生 7×（5-1）＋ 1＝29（名）。 有人说：“13 个人中至少有两个人出生在相同月份”；又说 ：“某校一个年级的 400 名学生中，一定存在两名学生 ， 他们在同一天过生日”，你认为他的说法对吗？你能说明为什么对或为什么不对吗？ 例 1. 在 1，4，7，10，…，100 中任选 20 个数，其中至少有不同的两对数，其和等于 104。 分析：解这道题，可以考虑先将 4 与 100，7 与 97，49 与 55……，这些和等于 104 的两个数组成一组，构成 16 个抽屉，剩下 1 和 52 再构成 2 个抽屉，这样，即使 20 个数中取到了 1 和 52，剩下的 18 个数还必须至少有两个 数取自前面 16 个抽屉中的两个抽屉，从而有不同的两组数，其和等于 104；如果取不到 1 和 52，或1 和 52 不全 取到，那么和等于 104 的数组将多于两组。 解：1，4，7，10，……，100 中共有 34 个数，将其分成{4，100}，{7，97}，……，{49，55}，{1}，{52}共 18 个抽屉，从这 18 个抽屉中任取 20 个数，若取到 1 和 52，则剩下的 18 个数取自前 16 个抽屉，至少有 4 个数取 自某两个抽屉中，结论成立；若不全取 1 和 52，则有多于 18 个数取自前 16 个抽屉，结论亦成立。 试一试：从 2，5，8，11，……，101 中任取 20 个数，其中必有两对数，它们的和为 106。 （例 1）提示构造抽屉{5，101}，{8，98}，{50，56}，{2}，{53}共 18 个抽屉。 例 2. 任意 5 个自然数中，必可找出 3 个数，使这三个数的和能被 3 整除。 分析：解这个问题，注意到一个数被 3 除的余数只有 0，1，2 三个，可以用余数来构造抽屉。 解：以一个数被 3 除的余数 0、1、2 构造抽屉，共有 3 个抽屉。任意五个数放入这三个抽屉中，若每个抽屉内均 有数，则各抽屉取一个数，这三个数的和是 3 的倍数，结论成立；若至少有一个抽屉内没有数，那么 5 个数中必 有三个数在同一抽屉内，这三个数的和是 3 的倍数，结论亦成立。 例 3. 在边长为 1 的正方形内，任意放入 9 个点，证明在以这些点为顶点的三角形中，必有一个三角形的面积不 超过 1/8. 解：分别连结正方形两组对边的中点，将正方形分为四个全等的小正方形，则各个小正方形的面积均为 1/4 。把 这四个小正方形看作 4 个抽屉，将 9 个点随意放入 4 个抽屉中，据抽屉原理，至少有一个小正方形中有 3 个点。 显然，以这三个点为顶点的三角形的面积不超过 1/8 。 反思：将边长为 1 的正方形分成 4 个面积均为 1/4 的小正方形，从而构造出 4 个抽屉，是解决本题的关键。我们 知道。将正方形分成面积均为 1/4 的图形的方法不只一种，如可连结两条对角线将正方形分成 4 个全等的直角三 角形，这4 个图形的面积也都是 1/4 ，但这样构造抽屉不能证到结论。可见，如何构造抽屉是利用抽屉原理解决 问题的关键。 试一试：在边长为 1 的等边三角形中有 10 个点，证明其中必有两个点之间的距离不大于 1/3 。 例 3）把等边三角形分成边长为 的 9 个小等边三角形，每个小三角形中，任意两点之间的距离都不大于 ，这样 构造成 9 个抽屉。由抽屉原理可知，肯定有两个点在同一个抽屉中，这两个点之间的距离不大于 。 例 4. 有一个圆，经过圆心任意作 993 条直径，它们与圆共有 1986 个交点，在每个交点上分别填上从 1 到 496 中的一个整数（可以重复）。证明：一定可以找到两条直径，它们两端的数的和相等。 分析：由于结果与直径两端的和有关，因此考虑直径两端数的和共有从 1+1 到 496+496 的 991 种情况，可以将 这 991 种情况作为 991 个抽屉，而直径两端的和共有 993 个数，由抽屉原理，一定存在两条直径，它们的两端数 的和相等。 证明：因为直径两端的和从 2 到 992 共有 991 种不同的结果，993 条直径两端的和共有 993 个数，由抽屉原理可 知，一定存在两条直径，它们的两端数的和相等。 圆桌周围均匀地放了 10 个座位，桌边上放有 10 位客人的名字。当客人随意入座后，发现没有一个人对着自己的 名字，试证明，可以转动圆桌，使得至少有两位客人同时对着自己的名字。 例 4）对每位客人而言，恰好有一种转动使得他正对着圆桌上自己的名字，除去刚入座的全坐错的情况，在圆桌 其余 9 种转动中，应有 10 位客人各有一次对着自己的名字，因此结论成立，上述 9 种转动即为 9 个抽屉。 应该注意的是用抽屉原理解决问题，只能证明具有某种性质的对象的“存在性”，却不一定能具体指出这些对象 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 是谁。 一般来说，题目中不会明确什么是“抽屉”，有几个“抽屉”，确定“抽屉”是用抽屉原理解题时需要做的工作。 某班 50 名学生，在第一次测验中 26 人满分，在第二次测验中 21 人满分，如果两次测验中都没得到满分的学生 有 17 人，那么两次测验中都获得满分的人数是_____________。 在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重 叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计 算的结果既无遗漏又无重复，这种计数的方法称为容斥原理，也叫做包含排除原理。 【抽屉原理】练习题（答题时间：30 分钟） 1. 某班 37 名同学，至少有几个同学在同一个月过生日？ 2. 42 只鸽子飞进 5 个笼子里，可以保证至少有一个笼子中可以有几只鸽子？ 3. 口袋中有红、黑、白、黄球各 10 个，它们的外型与重量都一样，至少要摸出几个球，才能保证有 4 个颜色相 同的球？ 4. 饲养员给 10 只猴子分苹果，其中至少要有一只猴子得到 7 个苹果，饲养员至少要拿来多少个苹果？ 5. 从 13 个自然数中，一定可以找到两个数，它们的差是 12 的倍数。 6. 一个班有 40 名同学，现在有课外书 125 本。把这些书分给同学，是否有人会得到 4 件或 4 件以上的玩具？ 【试题答案】 1. 某班 37 名同学，至少有几个同学在同一个月过生日？ 4 个 2. 42 只鸽子飞进 5 个笼子里，可以保证至少有一个笼子中可以有几只鸽子？ 9 只 3. 口袋中有红、黑、白、黄球各 10 个，它们的外型与重量都一样，至少要摸出几个球，才能保证有 4 个颜色 相同的球？ 13 个 4. 饲养员给 10 只猴子分苹果，其中至少要有一只猴子得到 7 个苹果，饲养员至少要拿来多少个苹果？ 61 个 5. 从 13 个自然数中，一定可以找到两个数，它们的差是 12 的倍数。 确定成立 6. 一个班有 40 名同学，现在有课外书 125 本。把这些书分给同学，是否有人会得到 4 件或 4 件以上的玩具？ 是 例 1、 教室里有 5 名学生正在做作业，今天只有数学、英语、语文、地理四科作业 求证：这 5 名学生中，至少有两个人在做同一科作业。 证明：将 5 名学生看作 5 个苹果 将数学、英语、语文、地理作业各看成一个抽屉，共 4 个抽屉 由抽屉原理 1，一定存在一个抽屉，在这个抽屉里至少有 2 个苹果。 即至少有两名学生在做同一科的作业。 例 2、 木箱里装有红色球 3 个、黄色球 5 个、蓝色球 7 个，若蒙眼去摸，为保证取出的球中有两个球的颜色相 同，则最少要取出多少个球？ 解：把 3 种颜色看作 3 个抽屉 若要符合题意，则小球的数目必须大于 3 大于 3 的最小数字是 4 故至少取出 4 个小球才能符合要求 答：最少要取出 4 个球。 例 3、 班上有 50 名学生，将书分给大家，至少要拿多少本，才能保证至少有一个学生能得到两本或两本以上的 书。 解：把 50 名学生看作 50 个抽屉，把书看成苹果 根据原理 1，书的数目要比学生的人数多 即书至少需要 50+1=51 本 答：最少需要 51 本。 例 4、 在一条长 100 米的小路一旁植树 101 棵，不管怎样种，总有两棵树的距离不超过 1 米。 解：把这条小路分成每段 1 米长，共 100 段 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 每段看作是一个抽屉，共 100 个抽屉，把 101 棵树看作是 101 个苹果 于是 101 个苹果放入 100 个抽屉中，至少有一个抽屉中有两个苹果 即至少有一段有两棵或两棵以上的树 例 5 11 名学生到老师家借书，老师是书房中有 A、B、C、D 四类书，每名学生最多可借两本不同类的书，最少 借一本 试证明：必有两个学生所借的书的类型相同 证明：若学生只借一本书，则不同的类型有 A、B、C、D 四种 若学生借两本不同类型的书，则不同的类型有 AB、AC、AD、BC、BD、CD 六种 共有 10 种类型 把这 10 种类型看作 10 个“抽屉” 把 11 个学生看作 11 个“苹果” 如果谁借哪种类型的书，就进入哪个抽屉 由抽屉原理，至少有两个学生，他们所借的书的类型相同 例 6、 有 50 名运动员进行某个项目的单循环赛，如果没有平局，也没有全胜 试证明：一定有两个运动员积分相同 证明：设每胜一局得一分 由于没有平局，也没有全胜，则得分情况只有 1、2、3……49，只有 49 种可能 以这 49 种可能得分的情况为 49 个抽屉 现有 50 名运动员得分 则一定有两名运动员得分相同 例 7、 体育用品仓库里有许多足球、排球和篮球，某班 50 名同学来仓库拿球，规定每个人至少拿 1 个球，至多 拿 2 个球，问至少有几名同学所拿的球种类是一致的？ 解题关键：利用抽屉原理 2。 解：根据规定，多有同学拿球的配组方式共有以下 9 种： ｛足｝｛排｝｛蓝｝｛足足｝｛排排｝｛蓝蓝｝｛足排｝｛足蓝｝｛排蓝｝ 以这 9 种配组方式制造 9 个抽屉 将这 50 个同学看作苹果 ＝5.5……5 由抽屉原理 2k＝〔 〕＋1 可得，至少有 6 人，他们所拿的球类是完全一致的 容斥原理 1 如果被计数的事物有 A、B 两类，那么，A 类或 B 类元素个数=A 类元素个数+B 类元素个数一既是 A 类又是 B 类的元素个数。 例 5. 从 1 到 200 中能被 3 或 5 整除的整数共有_____________个。 分析与解：依题意，被计数的事物有能被 3 整除和能被 5 整除两类，把“能被 3 整除”称为“A 类元素”，“能被 5 整除”称为“B 类元素”，“能被 3 整除又能被 5 整除”称为“既是 A 类又是 B 类元素”， A 类元素的个数 B 类元素的个数 既是 A 类又是 B 类元素的个数= ⎡ ⎣⎢ ⎤ ⎦⎥ = 200 3 66 = ⎡ ⎣⎢ ⎤ ⎦⎥ = 200 5 40 = ⎡ ⎣⎢ ⎤ ⎦⎥ = 200 15 13 所以，由容斥原理知，从 1 到 200 中能被 3 或 5 整除的整数的个数=66+40-13=93。 试一试：一次测试，某班有 15 人语文得满分，有 12 人数学得满分，并且有 4 人语文、数学都是满分，那么这个 班至少有一门得满分的有多少人？ 例 6. 某班 50 名学生，在第一次测验中 26 人满分，在第二次测验中 21 人满分，如果两次测验中都没得到满分的 学生有 17 人，那么，两次测验中都获得满分的人数是___________。 分析与解：依题意，被计数的事物有两类：第一次测验得满分和第二次测验得满分。把“第一次测验得满分”称 为“A 类元素”，“第二次测验得满分”称为“B 类元素”，“两次测验都得满分”称为“既是 A 类又是 B 类元素”。 因为两次测验都没有得满分的学生有 17 人，所以，两次测验中至少有一次得满分的学生有 人，即 A 类或 B 类 元素的个数是 33。又 A 类元素个数=26，B 类元素个数=21，根据容斥原理， 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 既是 A 类又是 B 类的元素个数=A 类元素个数+B 类元素个数－A 类或 B 类元素的个数=26+21－33=14。 即两次测验中都获得满分的人数是 14。 容斥原理 2 如果被计数的事物有 A、B、C 三类，那么，A 类或 B 类或 C 类元素个数=A 类元素个数+B 类元素个数+C 类元 素个数－既是 A 类又是 B 类的元素个数－既是 A 类又是 C 类的元素个数－既是 B 类又是 C 类的元素个数+既是 A 类又是 B 类而且是 C 类的元素个数。 例 7. 某次考试，某班语文成绩优秀的有 28 人，数学成绩优秀的有 32 人，英语成绩优秀的有 34 人，语文、数学 成绩都是优秀的有 22 人，语文、英语成绩都是优秀的有 24 人，数学、英语成绩都是优秀的有 25 人，语文、数 学、英语成绩都达到优秀的有 18 人，那么，该班语文、数学、英语三科中至少有一科成绩是优秀的有几人？ 分析与解：依题意，被计数的事物有语文成绩优秀、数学成绩优秀、英语成绩优秀三类，把“语文成绩优秀”称 为“A 类元素”，“数学成绩优秀”称为“B 类元素”，“英语成绩优秀”称为“C 类元素”，“语文和数学成绩都是 优秀”称为“既是 A 类又是 B 类的元素”，“语文和英语成绩都是优秀”称为“既是 A 类又是 C 类的元素”，“数 学和英语成绩都是优秀”称为“既是 B 类又是 C 类的元素”，“语文、数学、英语三科成绩都是优秀”称为“既 是 A 类又是 B 类而且是 C 类的元素”，“语文、数学、英语三科中至少有一科成绩是优秀”称为“A 类或 B 类或 C 类的元素”。 A 类元素的个数=28，B 类元素的个数=32，C 类元素的个数=34， 既是 A 类又是 B 类的元素的个数=22，既是 A 类又是 C 类的元素的个数=24， 既是 B 类又是 C 类的元素的个数=25，既是 A 类又是 B 类而且是 C 类的元素的个数=18， 所以，A 类或 B 类或 C 类元素的个数=A 类元素的个数+B 类元素的个数+C 类元素的个数－既是 A 类又是 B 类 的元素个数－既是 A 类又是 C 类的元素的个数－既是 B 类又是 C 类的元素的个数+既是 A 类又是 B 类而且是 C 类的元素的个数=28+32+34－22－24－25+18=41。 所以，该班语文、数学、英语三科中至少有一科成绩是优秀的有 41 人。 例 1、在边长为 1 的正方形内任意放置 5 个点，试证：其中必有两个点，它们之间的距离不大于 。 证明：将边长为 1 的正方形划分成如图所示的四个边长为 的小正方形，则每个小正方形中任意两点间的距离不 大于 ，据抽屉原理：5 个点放入四个正方形中，其中至少有一个正方形中至少有 2 个点，则这两个点间的距离 不大于 。 例 2、证明：边长为 1 的的正三角形内任意放置 5 个点，其中必有两点，其距离不超过 。 证明：将边长为 1 的正三角形的各边中点连结起来，得到四个小正三角形，则每个小正三角形中任意两点间的距 离不大于 ，据抽屉原理：5 个点放入 4 个小正三角形中，其中至少有一个小正三角形中至少有 2 个点，则这两 个点间的距离不超过 。 例 3、求证：任给五个整数，必能从中选出三个，使得它们的和能被 3 整除。 证明：因为任意一个整数被 3 除的余数只能是 0、1、2，若任给的 5 个整数被 3 除的余数中 0、1、2 都出现，则 余数为 0、1、2 的三个整数之和能被 3 整除；若5 个数被 3 除的余数只出现 0、1、2 中的两个，则据抽屉原理知 ： 必有 3 个整数的余数相同，而余数相同的 3 个数之和能被 3 整除。故任给五个整数，必能从中选出三个，使得它 们的和能被 3 整除。 例 4、求证：在 1,4,7,10,……,97,100 中任选 20 个不同的整数，其中必有二整数之和为 104。 证明：将 1,4,7,10,……,97,100 这 34 个自然数分成如下 18 个集合： {1},{4,100},{7,97},…,{49,55},{52}，从1,4,7,…,97,100 中任选 20 个数，即从上述 18 个集合中选 20 个数，则必有 一个集合中选了 2 个数，而这两个数的和为 104。 例 5、设a1,a 2,a3 ,…,an是自然数 1,2,3,…,n 随意打乱次序重新排列而成的一串数，n 是奇数。证明：(a1-1)(a 2-2)…(an-n) 总是偶数。 证明：因 n 为奇数，设n=2k+1，则 1,2,3,…,n 中共有 k+1 个奇数，从而 1,2,3,…,n，a1 ,a2,a 3,…,a 中共 2(k+1)=2k+2=n+1 个奇数，这n+1 个奇数放入 n 个括号中，则必有一个括号中的两个数均为奇数，从而这两个数之差为偶数，所以 (a1-1)(a 2-2)…(an-n)总是偶数。 例 6、求证：对于任给的 1987 个自然数 a1,a 1+a2 ,a1+a 2+a 3,…,a1+a 2+…+a1987,从中总可以找到若干个数，使它们的和 能被 1987 整除。 网上购物 就到“淘宝网购物” http://www.66gw.com.cn 证明：构造如下 1987 个和：a1,a1+a2,a1+a2+a3,…,a1+a2+…+a1987 ，若其中有一个和能被 1987 整除，则结论成 立。否则上述 1987 个和除以 1987 的余数只能为 1,2,… ,1986，则其中必有两个和的余数相同，设为 a1+a 2+…+ai ,a1+a 2+…+aj(i512，故可得 513 对(a1’,a2’,…,a9’),(a1”,a2”,…,a9”)，且 有 ak ’ +ak ” =2bk(k=1,2, … ,9) ， 最 后 ， 在 上 述 的 513 个 (b1,b2, … ,b9) 中 ， 又 必 有 两 个 (b1’,b2’,…,b9’),(b1”,b2”,…,b9”)奇偶性相同，所以 bk’+bk”=2ck(k=1,2,…，9)，设 a1’+a1”=2b1’, =2b k”，k=1,2, …,9,则:ak’+ak”=2bk’,k=1,2, …,9,则:ak’+ak”=2bk’,k=1,2,…,9。此时所求四个数为：' kk aa + , , , 。 例 13、平面上有两个定点 A 和 B 及任意四点 p1,p2,p3,p4，求证：这四点中一定有两点 Pi,Pj,(i,j=1,2,3,4,i≠j)使得 |sinÐ APiB-sinÐ APjB|≤ 。 3 1 证 明 ： 显 然 ： 0≤∠APiB≤π, ∴ 0≤sin∠APiB≤1(i=1,2,3,4 ) ， 即 在 [0,1] 内 有 四 个 实 数 sin∠AP1B,sin∠AP2B,sin∠AP3B,sin∠AP4B ，把 0,1]分成三个子区间 [0, ],[ , ],[ ,1] ，由抽屉原理知： 3 1 3 1 3 2 3 2 sin∠AP1B,sin∠AP2B,sin∠AP3B,sin∠AP4B 中必有两个数在同一区间中，不妨设为 sin∠APiB,sin∠APjB(i≠j,i,j=1,2,3,4)， 则： |sin∠APiB-sin∠APjB|≤ ，命题得证。 3 1 例 14、任给 7 个实数，证明其中必有两个数，记为 x,y，满足 0≤ 3 3 1 ≤ + − xy yx 证明：设 7 个实数为 x1,x2,…,x7，令 xi=tanq i,q i∈(- , ),将区间(- , , )分为 6 个子区间，每个子区间的 2 π 2 π 2 π 2 π 长度为 ,即为： 6 π (- ,- ),[- ,- ],[- ,0],[ 0, ],[ , ],[ , ]，据抽屉原理知：必有两个角α,β落在同一区间中，即其差 2 π 3 π 3 π 6 π 6 π 6 π 6 π 3 π 3 π 2 π 在 0 与 之间，由于这两个角的正切对应着 7 个实数中， 2 个实数 x,y，则由 x=tanα,y=tanβ(0≤α-β≤ )，得 6 π 6 π 0≤ ，即：0≤ 。 3 3 tantan1 tantan ≤ ⋅+ − βα βα 3 3 1 ≤ + − xy yx