抽屉原理(中)

7

抽屉原理与极端原理

一、抽屉原理

美国一家杂志上曾刊登这样一副漫画：三只鸽子同时往两个鸽笼里飞。这是一副含义深刻的漫画，它有趣的揭示了抽屉原理：三只鸽子同时飞进两个鸽笼里，则一定有一只鸽笼里至少飞进两只鸽子。抽屉原理俗称鸽笼原理，最先是由19世纪的德国数学家狄利克雷(P.G.Dirichlet 1805--1859)运用于解决数学问题的，所以抽屉原理又叫狄利克雷原理。

1．抽屉原理

（1）第一抽屉原理

设有m个元素分属于n个集合（其两两的交集可以非空），且m?kn（m，n，k均为正整数），则必有一个集合中至少有k?1个元素。 （2）第二抽屉原理

设有m个元素分属于n个两两不相交的集合，且m?kn（m，n，k均为正整数），则必有一个集合中至多有k?1个元素。 （3）无限的抽屉原理

设有无穷多个元素分属于n个集合，则必有一个集合中含有无穷多个元素。

2．平均值原理

?，an?R，且 设a1，a2，A?1?a1?a2???an?，G?n|a1a2?an|， na2，?，an中必有一个不大于A，亦必有一个不小于A；|a1|，|a2|，?，|an|中必有一个不大于则a1，G，亦有一个不小于G。

3．面积重叠原理

?，An的面积分别为S1，S2，?，Sn，将它们以任意方式放入一个面积为Sn个平面图形A1，A2，的平面图形A内。

1 ▎高一·第4讲·联赛预科班·教师版 ▎

（1）若S1?S2???Sn?S，则存在1≤i?j≤n，使图形Ai与Aj有公共内点；

（2）若S1?S2???Sn?S， 则A存在一点，不属于图形A1，A2，?，An中的任意一个。 以上命题用反证法很容易证明，大家可以自行完成。

一般来说，适合应用抽屉原理解决的数学问题具有如下特征：新给的元素具有任意性.如n?1个苹果放入n个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有……”、“一定有……”、“不少于……”、“存在……”、“必然有……”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果. 对一个具体的可以应用抽屉原理解决的数学问题还应搞清三个问题： （1）什么是“苹果”？ （2）什么是“抽屉”？ （3）苹果、抽屉各多少？ 用抽屉原理解题的本质是把所要讨论的问题利用抽屉原理缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确. 用抽屉原理解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.关键是构造适合的抽屉，抽屉之间可以有公共部分，亦可以没有公共部分。一般说来，数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等，都可作为构造抽屉的依据。这一简单的思维方式在解题过程中却可以演变出很多奇妙的变化和颇具匠心的运用。抽屉原理常常结合几何、整除、数列和染色等问题出现，从小学奥数、中学奥数、IMO到Putnam都可以见到它的身影。实际应用中，抽屉原理常常与反证法结合在一起。

二、极端原理

让我们先看一个有趣的放硬币游戏．

两人相继轮流往一张圆桌上平放一枚同样大小的硬币，条件是后放的硬币不能压在先放的硬币上，直到桌子上再也放不下一枚硬币为止。谁放入了最后一枚硬币谁获胜。问：先放的人有没有必定取胜的策略？

这是一个古老而值得深思的难题．当有人向一位确有才能的数学家提出这个难题时，引出了如下一段意味深长的对话：

数学家：这有什么难？如果圆桌小到只能容纳一枚硬币，那么先放的人当然能够取胜。 提问者：这还用你讲？简直废话！

数学家：不！这是一个很重要的特殊情况，它的解决将导致一般问题的解决． 提问者：怎么解决？

数学家：我先将第一枚硬币放在桌子的中心，利用圆桌的对称性，我就可以获胜．不管是圆桌还是方桌，也不管是桌子有多大，只要有一个对称中心就行．

数学家独具慧眼，能从一般性问题中一下子找到一个极易求解的极端情形，并能将极端情形下的解法推向一般，轻而易举地解决了上述难题，而且还作了推广．

这位数学家大概是这样思考的：

一般性的问题比较复杂，先将其极端化，注意到所放硬币总数n?1，取其极端情形n?1即假设桌子小到只能放下一枚硬币，得出特殊问题的解，即先占中心者为胜．然后根据圆桌的对称性，先放者把硬币放在中心位置O，若后放者把硬币放在C处，则先放者把硬币放在中心位置O的对称点C'处，这样只要后放者能放下硬币，先放者总能根据对称性，放下硬币，最后获胜．

这种思考问题的方法称为极端原理.

2 ▎高一·第4讲·联赛预科班·教师版 ▎

有时，我们只要抓住研究对象中某些具有极端性质的事物或它们所具有的特殊性质即可达到解决问题的目的。这样一种思想方法常称为极端原理.在数学竞赛中应用较多.

从问题的极端情况考虑，对于数值问题来说，就是指取它的最大或最小值；对于一个动点来说，指的是线段的端点，三角形的顶点等等。极端化的假设实际上也为题目增加了一个条件，求解也就会变得容易得多。

所谓极端原理指的是直接抓住全体对象中的极端情形或它们所具有的某种极端性质加以研究、解决问题的思想方法.

99【例 1】 在一个礼堂中有名学生，如果他们中的每个人都与其中的66人相识，那么可能出现这种情

况：他们中的任何4人中都一定有2人不相识（假定相识是互相的）。

【解析】 注意到题中的说法“可能出现……”，说明题的结论并非是条件的必然结果，而仅仅是一种可

能性，因此只需要设法构造出一种情况使之出现题目中所说的结论即可。 将礼堂中的99人记为a1，a2，…，a99，将99人分为3组：

?，a33?，?，a66?，?，a99?，将3组学生作为3个抽屉，分别?a1，a2，?a34，a35，?a67，a68，记为A，B，C，并约定A中的学生所认识的66人只在B，C中，同时，B，C中的学生所认

识的66人也只在A，C和A，B中。如果出现这种局面，那么题目中所说情况就可能出现。 因为礼堂中任意4人可看做4个苹果，放入A，B，C三个抽屉中，必有2人在同一抽屉， 即必有2人来自同一组，那么他们认识的人只在另2组中，因此他们两人不相识。

点评：这种类型的构造通常都是用分组的语言来描述的，此题的99和66是很大的提示

a1，?，an，满足a0?a1?a2???an?2n.证明：一定可以从中选出3个不同【例 2】 已知正整数a0，的数，使得其中两数之和等于第三数。

【解析】 由于1?a0?a1?a2???an?2n ①

1≤an?an?1?an?an?2?an?a0?2n ②

从而2n?1个数

a0，a1，a2，?，an，an?an?1，an?an?2，?，an?a0，

分属于2n?1个集合

{1}， {2}，…， {2n-1}，

根据抽屉原理，存在0≤i，j≤n?1，使得an?ai?aj. （1）若i?j，则an?ai?aj，原命题成立；

3 ▎高一·第4讲·联赛预科班·教师版 ▎

（2）若i?j，即an?2ai，则对于k?i，0≤k≤n，有an?2ak， 从而2n个数

a0，a1，a2，?，ai?1，ai?1，?，an，an?an?1，an?an?2，?，an?a0

分属于2n-1个集合

{1}， {2}，…， {2n-1}，

据抽屉原理，存在0≤i??j?≤n?1，使得an?ai??aj?，即an?ai??aj?，于是原命题成立 综上所述，命题成立。

【点评】 欲在a0，a1，?，an中找到不同的三个数，使得其中两数之和等于第三数，首先构造抽屉及足

够数量的数，在注意到特殊情况。根据需要两次应用抽屉原理是解答要点。其中（2）是在加

强条件以后再次应用抽屉原理，值得我们研究。

【例 3】 在圆周上放着100个筹码，其中有41个红的和59个蓝的。那么总可以找到两个红筹码，在

它们之间刚好放有19个筹码，为什么？

【解析】 此题需要研究“红筹码”的放臵情况，因而涉及到“苹果”的具体放臵方法，由此我们可以在构

造抽屉时，使每个抽屉中的相邻“苹果”之间有19个筹码。 依顺时针方向将筹码依次编上号码：1，2，…，100。 然后依照以下规律将100个筹码分为20组：

（1，21，41，61，81）；（2，22，42，62，82）；……（20，40，60，80，100）。 将41个红筹码看做苹果，放入以上20个抽屉中，因为41?2?20?1，

A所以至少有一个抽屉中有2?1?3（个）苹果，也就是说必有一组5个筹码中有3个红色筹码，而每组的5个筹码在圆周上可看做两两等距，且每2个相邻筹码之间都有19个筹码，那么3个红色筹码中必有2个相邻（这将在下一段利用第二抽屉原理证明），即有2个红色筹码之间BC有19个筹码。 上述疑问，现改述如下：在圆周上放有5个筹码，其中有3个是同色的，那么这3个同色的筹码必有2个相邻。 将这个问题加以转化：

如图，将同色的3个筹码A，B，C臵于圆周上，看是否能用另外2个筹码将其隔开。

将同色的3个筹码放臵在圆周上，将每2个筹码之间的间隔看做抽屉，将其余2个筹码看做苹果，将2个苹果放入3个抽屉中，则必有1个抽屉中没有苹果，即有2个同色筹码之间没有其它筹码，那么这2个筹码必相邻。

【例 4】 在一个面积为20?25的长方形内任意放进120个面积为1?1的正方形，证明：在这个长方形

内一定还可以放下一个直径为1的圆，它和这120个正方形的任何一个都不相重叠.

1【解析】 要使直径为1的圆完全放在一个矩形里，它的圆心应与矩形任何一条边的距离不小于，这

21的长条，则余下的长方形A'B'C'D'的面2积为19?24?456（如图a）.这样，任意放进长方形ABCD内的直径为1的圆心都在长方形可从20×25的长方形ABCD的每一边剪去一个宽为

4 ▎高一·第4讲·联赛预科班·教师版 ▎

A'B'C'D'中，此外，圆心应与任何一个正方形的边界的距离也大于

1，即在任何一个小正方2形以外加上

1的框[如图b）所得图形的面积是 21ππ1?4???3?.

244

用这样的120个图形互不相交地去覆盖长方形A'B'C'D'，它们的总面积等于120?(3?π但是 120?(?3?)120?4?4).

12?3.2?30?15.2?456. 4这说明用这样的120图形不能覆盖一个面积为456的长方形，从而可以在长方形ABCD内放臵一个直径为1的圆，它不与所有的小正方形中的任何一个重叠.

【点评】 常规题型 最常见的做法，把圆心不能存在的地方全部描述出来。

【例 5】 证明:任何四面体中，一定有一个顶点，由它出发的三条棱可以

构成一个三角形. A【解析】 如图，组成四面体的六条棱中总存在最长棱，不妨设为AB，

则AD?BD?AB，AC?BC?AB，有 (AC?AD)?(BC?BD)?2AB.

D从而AC?AD?AB与BC?BD?BA二式中必有一式成立， 即顶点A与顶点B中至少有一点为所求.

BC

【例 6】 晚会上n(n?2)对男女青年双双起舞，设任何一个男青年都未与全部女青年跳过舞，而每个女

b2及两g1，g2，使得b1与g1，b2与g2跳过舞青年至少与一个男青年跳过.求证:必有两男b1，而b1与g2，b2与g1均未跳过.

【解析】 证法1

记与之跳过舞的女青年数最多的男青年之一为b1，因b1未与全部女青年跳过，故可找到女青

年g2未与b1跳过.因g2至少与一个男青年跳过舞，故存在b2 (?b1)与g2跳过.如果凡事与b1跳过舞的女青年都与b2跳过，则与b2跳过舞的女青年数至少比b1大1，这不可能.故在与b1跳过舞的女青年中至少有一个未与b2跳过，记其中之一为g1，则这样选取的b1、b2、g1、g2满足要求. 证法2

记与之跳过舞的男青年数最少的女青年之一为g1，因g1至少与一个男青年跳过舞故可取b1与g1跳过.因b1未与全部女青年跳过舞，故又可选取g2未与b1跳过.如果凡与g2跳过舞的男青年

5 ▎高一·第4讲·联赛预科班·教师版 ▎

本文来源：https://www.bwwdw.com/article/uu67.html