抽屉原理(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张牌，才能保证四种花色都有。

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

第二章 几个重要的原理

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的倍数。

抽屉原理

一、教学准备

（一）教学对象。小学生。

（二）教学方法。鉴于小学生无初中生的抽象思维、推理演绎能力，采用归纳总结方法教学，再加上小学生注意力不能长时保持集中，应该综合运用游戏闯关、趣闻轶事、生活常识等手段，使之在乐趣中学习，在学习中成长，使之对数学产生浓厚兴趣，使之学会资料查询、网络搜索等能力。

（三）教学时间。40分钟。

二、教学实施（40分钟）

分三个阶段实施，第一阶段引出抽屉原理概念，第二阶段对抽屉原理进行应用，第三阶段发散思维，引出抽屉原理趣闻轶事。

（一）定义概念（10分钟）

1.小猴子有3个苹果，它想把他们放在2个无差别的抽屉中，但它不能将苹果切开，那么我们发现至少有一个抽屉有2个苹果。

（0,3）、（1,2）两种。

4个苹果放在3个抽屉中呢？同样发现至少有一个抽屉有2个苹果。

（0,4）、（1,3）、（2,2）三种。

5个苹果放在4个抽屉中，仍然是至少有一个抽屉有2个苹果。

（0,5）、（1,4）、（2,3）三种。

以此类推：“n+1个苹果放在n个抽屉中，至少有一个抽屉里有2个苹果。”这种现象称为“抽屉原理”，也叫“鸽巢原理”。抽屉原理是组合数学的一个重要原理。

抽屉原理的一般含义：“如果每个抽屉代表一个集合①，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有2个元素。”它是由德国数学家狄利克雷在1834年提出的。

2.n+1个苹果放在n个抽屉中，至少有一个抽屉里有2个苹果，那如果把多于n+1个苹果放在n个抽屉中，能保证至少有一个抽屉里有2个苹果吗？（显然能！）

抽屉原理的另一层含义：把多于n+1个的元素放到n个集合中，则至少有一个集合含有不少于2个元素。即n+k(k≥1)个元素放到n个集合中，则至少有一个集合含有不少于2个元素。

3.大家再算算：把5个苹果放在2个抽屉里，至少能保证有一个抽屉里有几个苹果呢？（5÷2＝2···1，即把5个苹果试着平均分配，每个抽屉里分到2个，结果还余出来一个，