容斥原理与抽屉原理

《容斥原理与抽屉原理》由会员分享，可在线阅读，更多相关《容斥原理与抽屉原理（18页珍藏版）》请在金锄头文库上搜索。

1、抽抽屉屉原原理理常常见见形形式式第第一一抽抽屉屉原原理理原理 1： 把多于 n+1 个的物体放到 n 个抽屉里，则至少有一个抽屉里的东西不少于两件。 抽屉原理 证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是 n，而不是题设的 n+k(k1)，故不可能。 原理 2 ：把多于 mn(m 乘以 n)个的物体放到 n 个抽屉里，则至少有一 个抽屉里有不少于 m+1 的物体。 证明（反证法）：若每个抽屉至多放进m 个物体,那么 n 个抽屉至多放 进 mn 个物体,与题设不符，故不可能。 原理 3 ：把无穷多件物体放入 n 个抽屉，则至少有一个抽屉里 有无 穷个物体。 原理 1 、

2、2 、3 都是第一抽屉原理的表述。 第第二二抽抽屉屉原原理理把（mn1）个物体放入 n 个抽屉中，其中必有一个抽屉中至多有 （m1）个物体。 证明（反证法）：若每个抽屉都有不少于m 个物体，则总共至少有 mn 个物体，与题设矛盾，故不可能。 基基本本介介绍绍应应用用抽抽屉屉原原理理解解题题 抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。 许多有关存在性的证明都可用它来解决。 例 1：同年出生的 400 人中至少有 2 个人的生日相同。 解：将一年中的 365 天视为 365 个抽屉，400 个人看作 400 个物体， 由抽屉原理 1 可以得知：至少有 2 人的生日相同 . 40

3、0/365=135,1+1=2 又如：我们从街上随便找来 13 人，就可断定他们中至少有两个人属相相同。“从任意 5 双手套中任取 6 只，其中至少有 2 只恰为一双手套。 ” “从数 1，2，.，10 中任取 6 个数，其中至少有 2 个数为奇偶性不 同。” 例 2： 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友 任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的 玩具都相同，试说明道理 . 解 ：从三种玩具中挑选两件，搭配方式只能是下面六种：（兔、兔）， （兔、熊猫），（兔、长颈鹿），（熊猫、熊猫），（熊猫、长颈鹿）， （长颈鹿、长颈鹿）。把每种搭配方式看作一个抽

4、屉，把7 个小朋友看作 物体，那么根据原理 1，至少有两个物体要放进同一个抽屉里，也就是说， 至少两人挑选玩具采用同一搭配方式，选的玩具相同. 上面数例论证的似乎都是 “存在”、“总有”、“至少有”的问题， 不错，这正是抽屉原则的主要作用 .（需要说明的是，运用抽屉原则只是肯 定了“存在”、“总有”、“至少有”，却不能确切地指出哪个抽屉里存在 多少. 抽屉原理虽然简单，但应用却很广泛，它可以解答很多有趣的问题，其 中有些问题还具有相当的难度。下面我们来研究有关的一些问题。 制制造造抽抽屉屉是是运运用用原原则则的的一一大大关关键键 例 1 从 2、4、6、30 这 15 个偶数中，任取 9 个数

5、，证明其中一定 有两个数之和是 34。 分析与解答 我们用题目中的 15 个偶数制造 8 个抽屉： 此抽屉特点：凡是抽屉中有两个数的，都具有一个共同的特点：这两个 数的和是 34。现从题目中的 15 个偶数中任取 9 个数，由抽屉原理（因为抽 屉只有 8 个），必有两个数可以在同一个抽屉中（符合上述特点）.由制造 的抽屉的特点，这两个数的和是 34。 例 2：从 1、2、3、4、19、20 这 20 个自然数中，至少任选几个数， 就可以保证其中一定包括两个数，它们的差是12。 分析与解答在这 20 个自然数中，差是 12 的有以下 8 对：20，8， 19，7，18，6，17，5，16，4，1

6、5，3，14，2，13，1。 另外还有 4 个不能配对的数 9，10，11，12，共制成 12 个抽 屉（每个括号看成一个抽屉） .只要有两个数取自同一个抽屉，那么它们的 差就等于 12，根据抽屉原理至少任选 13 个数，即可办到（取 12 个数：从 12 个抽屉中各取一个数（例如取 1，2，3，12），那么这 12 个数中任 意两个数的差必不等于 12）。 例 3： 从 1 到 20 这 20 个数中，任取 11 个数，必有两个数，其中一个 数是另一个数的倍数。 分析与解答 根据题目所要求证的问题，应考虑按照同一抽屉中，任意 两数都具有倍数关系的原则制造抽屉 .把这 20 个数按奇数及其倍数

7、分成以 下十组，看成 10 个抽屉（显然，它们具有上述性质）： 1，2，4，8，16，3，6，12，5，10，20，7，14，9，18， 11，13，15，17，19。 从这 10 个数组的 20 个数中任取 11 个数，根据抽屉原理，至少有两个 数取自同一个抽屉 .由于凡在同一抽屉中的两个数都具有倍数关系，所以这 两个数中，其中一个数一定是另一个数的倍数。 例 4：某校校庆，来了 n 位校友，彼此认识的握手问候 .请你证明无论 什么情况，在这 n 个校友中至少有两人握手的次数一样多。 分析与解答 共有 n 位校友，每个人握手的次数最少是0 次，即这个人 与其他校友都没有握过手；最多有n-1

8、次，即这个人与每位到会校友都握 了手.然而，如果有一个校友握手的次数是0 次，那么握手次数最多的不能 多于 n-2 次；如果有一个校友握手的次数是n-1 次，那么握手次数最少的 不能少于 1 次.不管是前一种状态 0、1、2、n-2，还是后一种状态 1、2、3、n-1，握手次数都只有 n-1 种情况.把这 n-1 种情况看成 n-1 个抽屉，到会的 n 个校友每人按照其握手的次数归入相应的 “抽屉”，根 据抽屉原理，至少有两个人属于同一抽屉，则这两个人握手的次数一样多。 在有些问题中， “抽屉”和“物体”不是很明显的，需要精心制造 “抽屉”和“物体”.如何制造“抽屉”和“物体”可能是很困难的，

9、一方 面需要认真地分析题目中的条件和问题，另一方面需要多做一些题积累经验。例 5：15 个网球分成数量不同的 4 堆，数量最多的一堆至少有多少个 球？ 分分析析与与解解答答 此题实际是求出 15 可分拆多少种 4 个互不相同的整数之 和，而 15=1+2+3+9=1+2+4+8=1+2+5+7=1+3+4+7=1+3+5+6=2+3+4+6，所以最 多一堆的球数可能是 9、8、7、6，其中至少有 6 个。1 整整除除问问题题把所有整数按照除以某个 自然数 m 的余数分为 m 类，叫做 m 的剩余类 或同余类，用 0，1，2，m-1表示.每一个类含有无穷多个数， 例如1中含有 1，m+1，2m+

10、1，3m+1，.在研究与整除有关的问题时，常 用剩余类作为抽屉 .根据抽屉原理，可以证明：任意 n+1 个自然数中，总有 两个自然数的差是 n 的倍数。(证明：n+1 个自然数被 n 整除余数至少有两 个相等（抽屉原理），不妨记为 m=a1*n+b n=a2*n+b，则 m-n 整除 n)。 例 1 证明：任取 8 个自然数，必有两个数的差是 7 的倍数。 分析与解答 在与整除有关的问题中有这样的性质，如果两个整数 a、b，它们除以自然数 m 的余数相同，那么它们的差 a-b 是 m 的倍数.根据 这个性质，本题只需证明这 8 个自然数中有 2 个自然数，它们除以 7 的余 数相同.我们可以把

11、所有自然数按被 7 除所得的 7 种不同的余数 0、1、2、3、4、5、6 分成七类.也就是 7 个抽屉.任取 8 个自然数，根据 抽屉原理，必有两个数在同一个抽屉中，也就是它们除以7 的余数相同， 因此这两个数的差一定是 7 的倍数。 例 2：对于任意的五个自然数，证明其中必有3 个数的和能被 3 整除. 证明任何数除以 3 所得余数只能是 0，1，2，不妨分别构造为 3 个 抽屉： 0，1，2 若这五个自然数除以 3 后所得余数分别分布在这 3 个抽屉中(即抽屉 中分别为含有余数为 0,1,2 的数)，我们从这三个抽屉中各取 1 个(如 15 中取 3,4,5)，其和(3+4+5=12)必

12、能被 3 整除. 若这 5 个余数分布在其中的两个抽屉中，则其中必有一个抽屉至少包 含有 3 个余数（抽屉原理），即一个抽屉包含1 个余数，另一个包含 4 个， 或者一个包含 2 个余数另一个抽屉包含 3 个。从余数多的那个抽屉里选出 三个余数，其代数和或为 0，或为 3，或为 6，均为 3 的倍数，故所对应的 3 个自然数之和是 3 的倍数. 若这 5 个余数分布在其中的一个抽屉中，很显然，从此抽屉中任意取 出三个余数，同情况 ，余数之和可被 3 整除，故其对应的 3 个自然数之 和能被 3 整除. 例 2：对于任意的 11 个整数，证明其中一定有 6 个数，它们的和能 被 6 整除. 证明

13、：设这 11 个整数为：a1，a2，a3a11 又 6=23 先考虑被 3 整除的情形 由例 2 知，在 11 个任意整数中，必存在： 3|a1+a2+a3，不妨设 a1+a2+a3=b1； 同理，剩下的 8 个任意整数中，由例 2，必存在： 3 | a4+a5+a6.设 a4+a5+a6=b2； 同理，其余的 5 个任意整数中，有： 3|a7+a8+a9，设：a7+a8+a9=b3 再考虑 b1、b2、b3 被 2 整除. 依据抽屉原理， b1、b2、b3 这三个整数中，至少有两个是同奇或同偶， 这两个同奇（或同偶）的整数之和必为偶数 .不妨设 2|b1+b2 则：6|b1+b2，即：6|a

14、1+a2+a3+a4+a5+a6 任意 11 个整数，其中必有 6 个数的和是 6 的倍数. 例 3： 任意给定 7 个不同的自然数，求证其中必有两个整数，其和或 差是 10 的倍数. 分析：注意到这些数除以 10 的余数即个位数字，以 0，1，9 为标 准制造 10 个抽屉，标以 0，1，9.若有两数落入同一抽屉，其差 是 10 的倍数，只是仅有 7 个自然数，似不便运用抽屉原则，再作调整： 6，7，8，9四个抽屉分别与 4，3，2，1合并，则可保证 至少有一个抽屉里有两个数，它们的和或差是10 的倍数. 抽抽屉屉原原理理 - - 表表述述 抽屉原理的一种更一般的表述为： “把多于 kn+1

15、 个东西任意分放进 n 个空抽屉（k 是正整数），那么一 定有一个抽屉中放进了至少 k+1 个东西。” 利用上述原理容易证明： “任意 7 个整数中，至少有 3 个数的两两之 差是 3 的倍数。”因为任一整数除以 3 时余数只有 0、1、2 三种可能，所 以 7 个整数中至少有 3 个数除以 3 所得余数相同，即它们两两之差是3 的 倍数。 如果问题所讨论的对象有无限多个，抽屉原理还有另一种表述： “把无限多个东西任意分放进 n 个空抽屉（ n 是自然数），那么一定有 一个抽屉中放进了无限多个东西。 ” 抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。 许多有关存在性的证明都可用

16、它来解决。 面面积积问问题题例：九条直线中的每一条直线都将正方形分成面积比为2:3 的梯形， 证明：这九条直线中至少有三条经过同一点 . 证明：如图，设直线 EF 将正方形分成两个梯形，作中位线MN。由于 这两个梯形的高相等， 故它们的面积之比等于中位线长的比，即 |MH|:|NH| 。于是点 H 有确定的位置（它在正方形一对对边中点的连线上， 且|MH|:|NH|=2:3）. 由几何上的对称性，这种点共有四个（即图中的 H、J、I、K）.已知的九条适合条件的分割直线中的每一条必须经过 H、J、I、K 这四点中的一点 .把 H、J、I、K 看成四个抽屉，九条直线当成 9 个物体，即可得出必定有 3 条分割线经过同一点 .应该是 (物体数-1) 抽屉数+1 染染色色问问题题例 1 正方体各面上涂上红色