抽屉原理(中)

1、、抽屉原理美国一家杂志上曾刊登这样一副漫画：三只鸽子同时往两个鸽笼里飞。这是一副含义深刻的漫画，它有趣的揭示了抽屉原理：三只鸽子同时飞进两个鸽笼里，则一定有一只鸽笼里至少飞进两只鸽子。抽屉原理俗称鸽笼原理，最先是由19世纪的德国数学家狄利克雷 (P.G.Dirichlet 1805-1859)运用于解决数学问题的，所以抽屉原理又叫狄利克雷原理。1 .抽屉原理(1) 第一抽屉原理设有m个元素分属于n个集合(其两两的交集可以非空)，且m kn ( m, n , k均为正整数)，则 必有一个集合中至少有 k 1个元素。(2) 第二抽屉原理设有m个元素分属于n个两两不相交的集合，且 m kn ( m

2、, n , k均为正整数)，则必有一个集合 中至多有k 1个元素。(3 )无限的抽屉原理设有无穷多个元素分属于 n个集合，则必有一个集合中含有无穷多个元素。2 平均值原理设印,a2, L , an R，且A 丄 a2 L an , G 打|3a2L an| , n则a1 , a2, L , an中必有一个不大于 A，亦必有一个不小于 A ；旧|a? L , |an |中必有一个不大于G，亦有一个不小于 G。3 面积重叠原理n个平面图形A1 ,A , L ,An的面积分别为S ,S2, L ,Sn ,将它们以任意方式放入一个面积为S的平面图形A内。(1 )若0 S2 L Sn S，则存在 K i

3、 j w n，使图形A与Aj有公共内点;以上命题用反证法很容易证明，大家可以自行完成。一般来说，适合应用抽屉原理解决的数学问题具有如下特征：新给的元素具有任意性如n 1个苹果放入 n 个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着 . 问题的结论是存在性命题，题目 中常含有“至少有”、“一定有”、“不少于”、“存在”、“必然有”等词 语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果.对一个具体的可以应用抽屉原理解决的数学问题还应搞清三个问题：（ 1）什么是“苹果” ？（ 2）什么是“抽屉”？（ 3）苹果、抽屉各多少？用抽屉原理解题的本质是把所要讨论的问题利用抽屉原理缩小范围

4、，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确 .用抽屉原理解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律 . 关键是构造适合的抽屉，抽屉之间可以有公共部分，亦可以没有公共部分。一般说来，数的奇 偶性、剩余类、数的分组、染色、线段与平面图形的划分等，都可作为构造抽屉的依据。这一简单的 思维方式在解题过程中却可以演变出很多奇妙的变化和颇具匠心的运用。抽屉原理常常结合几何、整 除、数列和染色等问题出现，从小学奥数、中学奥数、IMO到Putnam都可以见到它的身影。实际应用中，抽屉原理常常与反证法结合在一起。二、极端原理让我们先看一个有趣的放硬币游戏两人

5、相继轮流往一张圆桌上平放一枚同样大小的硬币， 条件是后放的硬币不能压在先放的硬币上， 直到桌子上再也放不下一枚硬币为止。谁放入了最后一枚硬币谁获胜。问：先放的人有没有必定取胜 的策略？这是一个古老而值得深思的难题当有人向一位确有才能的数学家提出这个难题时，引出了如下 一段意味深长的对话：数学家：这有什么难？如果圆桌小到只能容纳一枚硬币，那么先放的人当然能够取胜。 提问者：这还用你讲？简直废话！数学家：不！这是一个很重要的特殊情况，它的解决将导致一般问题的解决提问者：怎么解决？ 数学家：我先将第一枚硬币放在桌子的中心，利用圆桌的对称性，我就可以获胜不管是圆桌还 是方桌，也不管是桌子有多大，只要有

6、一个对称中心就行数学家独具慧眼，能从一般性问题中一下子找到一个极易求解的极端情形，并能将极端情形下的 解法推向一般，轻而易举地解决了上述难题，而且还作了推广这位数学家大概是这样思考的：一般性的问题比较复杂，先将其极端化，注意到所放硬币总数 n 1，取其极端情形 n 1即假设 桌子小到只能放下一枚硬币，得出特殊问题的解，即先占中心者为胜然后根据圆桌的对称性，先放 者把硬币放在中心位置 0 ,若后放者把硬币放在 C处，则先放者把硬币放在中心位置 0的对称点C处, 这样只要后放者能放下硬币，先放者总能根据对称性，放下硬币，最后获胜这种思考问题的方法称为极端原理 . 有时，我们只要抓住研究对象中某些具

7、有极端性质的事物或它们所具有的特殊性质即可达到解决 问题的目的。这样一种思想方法常称为极端原理. 在数学竞赛中应用较多 .从问题的极端情况考虑，对于数值问题来说，就是指取它的最大或最小值；对于一个动点来说， 指的是线段的端点，三角形的顶点等等。极端化的假设实际上也为题目增加了一个条件，求解也就会 变得容易得多。所谓极端原理指的是直接抓住全体对象中的极端情形或它们所具有的某种极端性质加以研究、解 决问题的思想方法【例2】已知正整数ao, a1 , L , an ,满足a。 的数，使得其中两数之和等于第三数。aia2 L an 2n.证明：一定可以从中选出 3个不同【解析】由于1a0 a1 a2

8、L an 2n【例1】在一个礼堂中有99名学生，如果他们中的每个人都与其中的66人相识，那么可能出现这种情况：他们中的任何 4人中都一定有2人不相识（假定相识是互相的）。【解析】注意到题中的说法“可能出现”，说明题的结论并非是条件的必然结果，而仅仅是一种 可能性，因此只需要设法构造出一种情况使之出现题目中所说的结论即可。将礼堂中的99人记为ai, a2，a99 ,将99人分为3组:ai , a2 , L , aaa , 834 235 , L , a66 ,尙，玄68 , L , 899 ,将3组学生作为3个抽屉，分别记为A B, C,并约定A中的学生所认识的66人只在B, C中，同时，B,

9、C中的学生所认识的66人也只在A, C和A, B中。如果出现这种局面，那么题目中所说情况就可能出现。因为礼堂中任意 4人可看做4个苹果，放入 A, B, C三个抽屉中，必有 2人在同一抽屉，即必有2人来自同一组，那么他们认识的人只在另2组中，因此他们两人不相识。99和66是很大的提示点评：这种类型的构造通常都是用分组的语言来描述的，此题的an 1 an an 2 an a0 2n从而2n1个数a0 , a1 ,a2 , L ,an , anan 1 ,anan 2 , L ,ana0 ,分属于2n 1个集合1 , 2,2n-1根据抽屉原理，存在i , j w n 1 ,使得 anaia；.(1

10、 )若 i j，则 aaiaj ,原命题成立;(2)若 i j ,即 an细,贝V对于 k i , 0 w k w n ,有 an 2a从而2n个数分属于2n-1个集合1 , 2,2n-1,据抽屉原理，存在0 i j 4，求n的最小值f m ,使得对具有性质 p m的任何赛况，都有所有 n名棋手的得分各不相同。【解析】本题粗看起来比较乱，又是性质又是最小值。我们先需要理清思路。首先要看p m说的是什么，其实 p m在感觉上就是说，可以存在平局 A平B，或者循环胜利（即A胜B , B胜C , C胜A ），但是这样的A , B或者A, B , C必然要处于“中等水平”， 以便任意取包含他们的一个

11、m棋手的集合，都有人胜了他们，也有人败给了他们。而如果不出现平局，也没有循环胜利，显然可以给所有棋手排一个“序”，使得排序靠前的棋手在对排序靠后的棋手的比赛中，都是获胜的，那么所有棋手的得分当然不相同。把这个思路反过来想，就是构造反例的思路。我们将证明f m 2m 3。先构造一个 2m 4 名棋手的反例。设这 2m 4名棋手为 A1，A2， Am 3，B1，B2， ，Bm 3，C1，C2 ，下面如此构造他们的比赛结果。(1) A中的任意一人胜了 B和C中的所有人。( 2) B 中的任意一人败给了 C 中的两个人。(3) 对于 A 和 Aj i j , A 胜了 Aj。(4) 对于 Bj和B(i

12、 j) , Bi胜了 Bj。(5) 和C2战成平局。那么我们可以看的出，Ci和 C2的得分是完全相同的。任意取m位棋手，设他们组成的集合为 S。由于A和C 一共m 1人，B和C也一共m 1人, 所以在S中，必然有A中的棋手，也有 B中的棋手。设i是最小的角标，使得 A S，j是最大的角标，使得 Bj S，那么显而易见的有 A胜了S中所有其他人，Bj败给了 S中所有其他人，即这 2m 4名棋手满足性质 P m，但并不是所有棋手的得分都不同。当棋手总人数小于2m-4时，我们可以依次去掉棋手Am3，Bm3，Am2，Bm 2A2,B2，这样同上面的证明知性质 P m 依然存在， 但是还是有两名棋手的得

13、分相同。 直到剩下不足 4名棋手,那么 P m 等于没有限制,结论显然不成立。下面我们将证明,对于任意 n 2m 3名棋手的具有性质 P m 的任何赛况,都有所有 n 名棋 手的得分各不相同。我们假设不然,即存在两名棋手的得分相同,我们下面将先证明,或者存在两名棋手打成平 局，或者存在三名棋手循环胜负(即A胜B，B胜C，C胜A )。不妨设没有任何平局出现，且两名得分相同的棋手为A和B，其中A胜了 B。由于A和B积分相同，即他们获胜的场次数相同。而 A已经在与B的比赛中胜了一场，故在与其他 n 2名 棋手的对弈中， A胜的场数比B胜的场数少1。这就意味着，必然存在一个人 C，他胜了 A， 但是败

14、给了 B，这样我们就找到了三个人 A、B、C，A胜B，B胜C，C胜A。回到原题，我们将证明这 n 个人不满足性质 P m 。分两种情况讨论：(1)存在两人打成平局。不妨设是 A和B打成平局。将剩下n 2个人分成三个集合 R，S， T。所有赢了 A和B的人分入集合R，所有输给了 A和B的人分入集合S，剩下的人分入集 合T。因为R，S，T 一共只有2m 5个人，由抽屉原理，R或者S中至少有一个集合有不超过 m 3 个人。如果R不超过m 3个人，那么取 A和B，以及S和T中的一些人，凑够 m人，但是这 m个人必然不满足性质 P m，因为没有人赢了 A和B，且A和B打成了平局。如果S不超过m 3个人，

15、那么取 A和B，以及R和T中的一些人，凑够 m人，但是这m个人必然不满足性质 P m，因为没有人输给了 A和B，且A和B打成了平局。（2）存在三个人循环胜负，不妨设是 A胜B， B胜C，C胜A。将剩下n 3个人分成三 个集合R，S，T。所有赢了 A、B和C的人分入集合 R，所有输给了 A、B和C的人分入集 合S,剩下的人分入集合 T。因为R，S，T 一共只有2m 6个人，由抽屉原理， R或者S中 至少有一个集合有不超过 m 3个人。如果R不超过m 3个人，那么取A、B和C,以及S和T中的一些人，凑够m人，但是这m 个人必然不满足性质 P m，因为没有人赢了 A、B和C，且A、B和C循环胜负。如

16、果S不超过m 3个人，那么取A、B和C，以及R和T中的一些人，凑够m人，但是这m 个人必然不满足性质 P m，因为没有人输给了 A、B和C，且A、B和C循环胜负。综上，假设并不成立，即 n的最小值就是2m 3。【点评】解答此题需要我们抓住最本质的胜负关系进行讨论，方有结果。习题2. 一个车间有一条生产流水线，由5台机器组成，只有每台机器都开动时，这条流水线才能工作。总共有8个工人在这条流水线上工作。在每一个工作日内，这些工人中只有5名到场。为了保证生产，要对这 8名工人进行培训，每人学一种机器的操作方法称为一轮。问：最少 要进行多少轮培训，才能使任意5个工人上班而流水线总能工作？【解析】20轮。如果培训的总轮数少于20，那么在每一台机器上可进行工作的工人平均数就小于2020 4，这说明，至少有一台机器至多有3个会操作的工人。如果这 3个工人某一天都没有5到车间来，那么这台机器就不能开动，整个流水线就不能工作。故培训的总轮数不能少于20。另一方面，只要进行 20轮培训就够了。对 3名工人进行全能性培训，训练他们会开动一台机 器；而对其余 5名工人，每人只培训一轮，让他们每人能开动一台机器。这个方案实施后， 不论哪5名工人上班，流水线总能工作。习题3.证明每个凸五边形必有三条对