浅谈抽屉原理中抽屉的几种构造方法.doc

浅谈抽屉原理中抽屉的几种构造方法.doc浅谈抽屉原理中抽屉的几种构造方法摘要:抽屉原理(鸽巢原理)是组合数学屮一个重要的初等原理,在解决一某类存在性问题中具有广泛应用。考虑到应用抽屉原理证明时构造抽屉的重要性,该文在简单地介绍抽屉原理(鸽巢原理)的基础上,分别从等分区间,通过几何图形,利用余数,分组构造等几个方面对如何构造抽屉,进行了总结与概括,进而应用抽屉原理来解决某类存在性问题。关键词:组合数学抽屉原理存在性问题构造中图分类号:029文献标识码:A文章编号:1674-098X(2012)12(a)-000-021抽屉原理抽屉原理又称鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。是一个及其初等而有应用广泛的数学原理。定理1・1抽屉原理(基本形式):将n+1个物体放入到n个抽屉中,则至少有一个抽屉中的物品数不少于两个。以上定理不难推广为:(推广形式人把个物体放入标号为的个抽屉中,则至少有一个标号为i的抽屉中物品数不少于,。根据以上定理结果,可得到以下结论。,则至少有一个集合中含有两个或两个以上的元索。,则至少有一个集合屮元素个数不少于r个。,则至少有一个集合中元素个数不少于个。其中为取整函数,下同。,则至少有一个集合中元素个数不多于个。以上结果均为冇限形式的抽屉原理的冇关结论,对于无限形式,有以下定理:定理1・3抽屉原理(无限形式人无穷多个物体放到有限多只抽屉中,至少有一只抽屉放进了无穷多个球。以上诸定理及英推论在大部分组合数学教材中均有论及,限于篇幅有限,证明从略。2抽屉的构造抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它來解决。而在利用抽屉原理证明数学问题或者解决实际问题时,最关键是要确定哪些是“球”,哪些是“抽屉”。很多时候需要我们选取、制造“合适、恰当”的抽屉。“合适”一要求每个抽屉的“规格”是一样的,因为是按任意方式放进元素的,每个抽屉放人元素的可能性是一样的;“恰当”一抽屉的数目要少于元素的数目,且满足所求的结论。以下通过实例,对如何构造抽屉进行简要分析说明。:如果在长度为1的区间内有多于n个的点,可考虑把区间n等分成n个子区间,这样由抽屉原理可知,一定有两点落在同一子区间,它们之间的距离不大于。这种构造法常用于处理一些不等式的证明。对于给定了一定的长度或区间并要证明不等式的问题,可以采用等分区间的构造方法来构造抽屉。例1设xl,x2,…,xn全为实数,满足,求证:对于任意的整数,存在不全为零的整数,使得,并且:分析:由条件以及柯西不等式显然有:从而可以进一步把区间等分成个小区间,构造抽屉。证明:由柯西不等式有:所以:因此,当时,冇把区间分成个小区间,每个区间长度为。而因为每个能取k个整数,所以一共有个整数。根据抽屉原理,必存在某个小区间,其中至少有两个整数,设它们分别为和,则有:其屮使得为整数,且。证毕。从上面例题不难发现,在等分区间的基础上便很方便的构造了抽屉,从而寻找到了证明不等式的一