抽屉原理(中).doc

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

(1)第一抽屉原理
设有个元素分属于个集合(其两两的交集可以非空),且(均为正整数),则必有一个集合中至少有个元素。
(2)第二抽屉原理
设有个元素分属于个两两不相交的集合,且(均为正整数),则必有一个集合中至多有个元素。
(3)无限的抽屉原理
设有无穷多个元素分属于个集合,则必有一个集合中含有无穷多个元素。

设,且
,
则中必有一个不大于,亦必有一个不小于;中必有一个不大于,亦有一个不小于。

个平面图形的面积分别为,将它们以任意方式放入一个面积为的平面图形内。
(1)若,则存在,使图形与有公共内点;
(2)若, 则存在一点,不属于图形中的任意一个。
以上命题用反证法很容易证明,大家可以自行完成。
一般来说,适合应用抽屉原理解决的数学问题具有如下特征:,可以随意地一个抽屉放几个,也可以让抽屉空着. 问题的结论是存在性命题,题目中常含有“至少有……”、“一定有……”、“不少于……”、“存在……”、“必然有……”等词语,其结论只要存在,不必确定,即不需要知道第几个抽屉放多少个苹果.
对一个具体的可以应用抽屉原理解决的数学问题还应搞清三个问题:
(1)什么是“苹果”?
(2)什么是“抽屉”?
(3)苹果、抽屉各多少?
用抽屉原理解题的本质是把所要讨论的问题利用抽屉原理缩小范围,使之在一个特定的小范围内考虑问题,从而使问题变得简单明确.
用抽屉原理解题的基本思想是根据问题的自身特点和本质,弄清对哪些元素进行分类,,抽屉之间可以有公共部分,亦可以没有公共部分。一般说来,数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等,都可作为构造抽屉的依据。这一简单的思维方式在解题过程中却可以演变出很多奇妙的变化和颇具匠心的运用。抽屉原理常常结合几何、整除、数列和染色等问题出现,从小学奥数、中学奥数、IMO到Putnam都可以见到它的身影。实际应用中,抽屉原理常常与反证法结合在一起。
二、极端原理
让我们先看一个有趣的放硬币游戏.
两人相继轮流往一张圆桌上平放一枚同样大小的硬币,条件是后放的硬币不能压在先放的硬币上,直到桌子上再也放不下一枚硬币为止。谁放入了最后一枚硬币谁获胜。问:先放的人有没有必定取胜的策略?
,引出了如下一段意味深长的对话:
数学家:这有什么难?如果圆桌小到只能容纳一枚硬币,那么先放的人当然能够取胜。
提问者:这还用你讲?简直废话!
数学家:不!这是一个很重要的特殊情况,它的解决将导致一般问题的解决.
提问者:怎么解决?
数学家:我先将第一枚硬币放在桌子的中心,利用圆桌的对称性,