抽屉原理2

1 最不利原则和抽屉原理

第四讲：最不利原则

一、最不利原

在日常生活和生产中，我们常常会遇到求最大值或最小值的问题，解答这类问题，常常需要从最不利的情况出发分析问题，这就是最不利原则。

例1口袋里有同样大小和同样质地的红、黄、蓝三种颜色的小球各20个。问：一次最少摸出几个球，才能保证至少有4个小球颜色相同？

分析与解：如果碰巧一次取出的4个小球的颜色都相同，就回答是“4”，那么显然不对，因为摸出的4个小球的颜色也可能不相同。回答是“4”是从最“有利”的情况考虑的，但为了“保证至少有4个小球颜色相同”，就要从最“不利”的情况考虑。如果最不利的情况都满足题目要求，那么其它情况必然也能满足题目要求。

“最不利”的情况是什么呢？那就是我们摸出（ ）个红球、（ ）个黄球和（ ）个蓝球，此时三种颜色的球都是（ ）个，却无4个球同色。这样摸出的9个球是“最不利”的情形。这时再摸出一个球，无论是红、黄或蓝色，都能保证有4个小球颜色相同。所以回答应是最少摸出（ ）个球。

通过上面分析，列式为：

例2一把钥匙只能开一把锁，现有10把钥匙和10把锁，最少要试验多少次就一定能使全部的钥匙和锁相匹配？

分析与解：从最不利的情形考虑。用10把钥匙依次去试第一把锁，最不利的情况是试验了9次，前8次都没打开，第9次无论打开或没打开，都能确定与这把锁相匹配的钥匙（若没打开，则第10把钥匙与这把锁相匹配）。同理，第二把锁试验8次„„第九把锁只需试验1次，第十把锁不用再试（为什么？）。通过上面分析，列式为：

例3在一副扑克牌中，最少要取出多少张，才能保证取出的牌中四种花色都有？

分析与解：一副扑克牌有大、小王牌各1张，“红桃”、“黑桃”、“方块”、“梅花”四种花色各13张，共计有54张牌。最不利的情形是：取出四种花色中的三种花色的牌各13张，再加上2张王牌。这41张牌中没有四种花色。剩下的正好是另一种花色的13张牌，再抽1张，四种花色都有了。因此最少要拿出42张牌，才能保证四种花色都有。

让我们为全力打造甘肃名校—甘肃省华亭县皇甫学校而共同努力吧!

走进奥数,成就辉煌—皇甫学校培优竞赛教程(李敬之个人竞赛空间)137 第24讲 抽屉原理 只在此山中，云深不知处。 ——贾岛知识方法扫描 美国一家杂志上曾刊登这样一幅漫画：三只鸽子同时往两只鸽笼子里飞. 这是一幅含义深刻的漫画，它有趣地说明了抽屉原理：三只鸽子要飞进两只鸽笼，则一定有一只笼子里至少飞进两只鸽子. 抽屉原理一般可表述为： 原理1 若将n＋1件物品任意放入n个抽屉里，则必有一个抽屉里，至少有两件物品． 原理2 若将mn＋k (k≥1)件物品任意放入n个抽屉里，则必有一个抽屉里，至少有m＋1件物品． 原理1是原理2在m=k=1时的特殊情形．它的正确性是显然的，可用反证法很容易证明．请同学们自证． 抽屉原理尽管简单，但却有许多出人意料的应用，它是组合数学中一条重要的论证存在性的原理．应用抽屉原理解决问题的关键在于制造合适的抽屉．如何制造抽屉呢?基本的想法是有的放矢，围绕题设要求，在充分考虑问题自身特点的基础上制造抽屉，这往往要求我们认真观察，善于联想，努力想象，大胆尝试，并灵活运用数学、代数、几何等方面知识，本讲通过典型例题介绍几种常见的制造抽屉的方法．经典例题解析1．分割图形制造抽屉在讨论有关点在几何图形中的分布和性质时，我们常常将几何图形分割成若干部分，将每一部分看成一个“抽屉”．一般来说，采取均等分割图形制造抽屉，如等分正方形、等分矩形、等分线段、等分圆周等．例1 在边长为1的正三角形内，有5个点．证明：其中至少有两个点，它们的距离不大于.21 分析与解 只须证明至少有两个点在边长为的正三角形内即21可，如图连接正三角形各边的中点，将边长为1的正三角形分为四个全等的边长为的小正三角形。由原理1，以这四个小正三角形21作为四个抽屉，5个点放入后必有一个小正三角形中至少有两个点，则这两个点的距离不大于正三角形的边长.21 评注 这里是用等分三角形的方法来制造“抽屉”，用类似的作法，将5个点扩充为10个点，此题可推广为：在边长为

山东省济宁一中奥林匹克数学竞赛辅导讲义 贾广素 编写

第二章 几个重要的原理

2.1 抽屉原理

将10个苹果放在9个抽屉中，无论怎么放，一定会有一个抽屉里放了2个或更多的苹果，这个简单的事实就是抽屉原理. 它是由德国数学家狄利克雷(Dirichlet)提出来的,因此也称为狄利克雷原理.如果将苹果换成信，鸽子或鞋，而把抽屉换成信筒，鸽笼或鞋盒，那么这个原理应然适用. 它是许多存在性问题得以证明的理论依据,也是离散数学中的一个重要原理，把它推广到一般情形，就可以得到：

抽屉原理

如果将m个物品放入n个抽屉内，那么至少有一个抽屉的物品不少于l个，其中[]1mnlmn （这里[]x表示不超过x的最大整数）

【证明】当|nm时，若结论不真，则每个抽屉中至多有1mn个物品，那么n个抽屉中物品的总数(1)mnmnmn个，矛盾！

时，若结论不真，则n个抽屉中物品总数[]mmnnmnn个，也矛盾！ 当有的参考书上给出了此定理的另外一种写法：如果将m个物品放入n个抽屉内，那么必有一个抽屉内至少有1[]1mn个物品。这是抽屉原理的不同的两种表现形式，其本质是一样的。另外，抽屉原理还有其它的几种形式的推广：

推广1：如果将m个物体放入n个抽屉内，那么必有一个抽屉内的物品至多有[]mn个。

这是推广也叫做第二抽屉原理，证明如下：

【证明】用反证法，如果每个抽屉内至少有[]mn＋1个物品，那么n个抽屉内的物品的总数至少为([]1)mmnnmnn，这与n个抽屉内共有m个物品矛盾！

推广2：无穷多个物品放入有限个抽屉中，则至少有一个抽屉中有无穷多个物品。

推广3：把121nmmmn个元素分成n类，则存在一个k，使得第k类至少有||nmnm|nm山东省济宁一中奥林匹克数学竞赛辅导讲义 贾广素 编写

数论中的抽屉原理（组合）

一、数论中的抽屉原理 & 最不利原则 —— “和差倍”

1. 题型 （1）两数之和 或 两数之差 是m

（2）两数之和 或 两数之差 是m的倍数

2. 解题思路 题型（1）根据 题意 构造抽屉

题型（2）根据 余数的特征 进行分组，构造抽屉 二、注意事项

1. 相邻两数必互质。

题型一：根据题意构造抽屉

1. 从2、4、6、…、30这15个偶数中，至少选出多少个数，才能保证其中一定有两个数之和

是34 .

2. 从1 ~ 11这11个自然数中，至少选出多少个数，才能保证其中一定有两个数之和是12 . 3. 从1 ~ 99这99个自然数中，最多选出多少个数，使得其中每两个数之和都不等于100？

4. 从1，2，3，4，5，6，7，8，9，10，11，12中最多能选出几个数，使得在选出的数中，

每一个数都不是另一个数的2倍。

5. 从1 ~ 21这21个自然数中，至少取出多少个数，才能保证其中必有两数的差等于4？

6. 从1 ~ 99这99个自然数中，最多可以取出多少个数，使得其中每两个数之差都不等于5？

7. 如果在1，2，… …，n中任取19个数，都可以保证其中必有两个数的差是6，那么n最大

是多少？

8. 从1 ~ 50这50个自然数中，至少选出多少个数，才能保证其中必有两个数互质？ 题型二：根据余数构造抽屉

1. 在任意的四个自然数中，是否其中必有两个数，它们的差能被3整除。

2. 至少取几个数，才能保证一定有两个数的差是7的倍数？

3. 1 ~ 17中，至少拿出多少个数才能保证：

（1）里面一定有5的倍数？ （2）一定有两个数的和是5的倍数？

4. 1 ~ 35中，至少拿出多少个数才能保证一定有两个数的和是8的倍数？

5. 从1至17这17个自然数中取出若干个数，使其中任意两个数的和都不能被5整除．请问：

最多能取出多少个数？

6. 任选7个不同的数，请说明：其中必有2个数的和或者差是10的倍数。