抽屉原理及其应用论文草案

《抽屉原理及其应用论文草案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录1．抽屉原理11．1抽屉原理的简单形式11．2抽屉原理的加强形式22．抽屉原理的应用42．1抽屉的构造42．1．1等分区间制造抽屉42．1．2分割图形构造抽屉52．1．3利用“对称性”构造抽屉62．1．4用整数性质制造抽屉72．1．5利用染色制造抽屉82．1．6根据问题的需要制造抽屉92．2抽屉原理在数学解题中的应用102．2．1解决代数问题102．2．2解决数论问题112．2．3解决几何问题122．2．4多次顺向运用抽屉原理122．2．5逆向运用抽屉原理132．3抽屉原理在生活中的应用132．3．1月黑穿袜子

2、132．3．2手指纹和头发142．3．3电脑算命143．总结15参考文献16致谢171．抽屉原理抽屉原理又叫做鸽巢原理，指的是一件简单明了的事实：为数众多的鸽子飞进为数不多的巢穴里，则至少有一个巢穴飞进了两只或者更多的鸽子，其实有关于抽屉原理（鸽巢原理）的阐释，粗略的说就是如果有许多物体放进不足够多的盒子内，那么至少有一个盒子被两个或多个盒子占据。我将在下面的论文当中给出更加精确的叙述。1．1抽屉原理的简单形式抽屉原理的最简单的形式如下．定理1．1．1[１]如果个物体放进个盒子，那么至少有一个盒子包含两个或更多的物

3、体．证明：（用反证法）如果个盒子中每个盒子至多放一个物体，则放入个盒子中的物体总数至多为个．这与假设有个物体矛盾．从而定理得证．注意，无论是抽屉原理还是它的证明，对于找出含有两个或更多物体的盒子都没有任何帮助．我们只是简单断言，如果人们检查每一个盒子，那么他们会发现有的盒子，里面放有多于一个的物体．抽屉原理只是保证这样的盒子存在．因此，无论何时抽屉原理被用来证明一个排列或某种现象的存在性，除了考察所有的可能性外，它都不能对任何构造排列或寻找现象的例证给出任何指示．还要注意，抽屉原理的结论不能被推广到只存在个（或更少

4、）物体的情形．这是应为我们可以把不同的物体放到个盒子的每一个中去．当然，在这些盒子中可以这样分发物体：一个盒子放入两个物体，但对任意分发这是没有保证的．抽屉原理只是断言，在个盒子中去论如何分发个物体，总不能避免把两个物体放进同一个盒子中去．还存在一些与抽屉原理相关的其它原理，有必要正式叙述如下．(1)如果将个物体放入个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体．(2)如果将个物体放入个盒子并且没有盒子被放入多于一个的物体，那么每个盒子里有一个物体．现在把所阐明的这三个原理更抽象的表述为：令和是两个有限

5、集，并令是一个从到得函数．（1）如果的元素多于的元素，那么就不是一对一的．（2）如果和含有相同个数的元素，并且是映上的，那么就是一对一的．（3）如果和含有相同个数的元素，并且是一对一的，那么就是映上的．1．2抽屉原理的加强形式下列定理包含定理1．1．1作为它的特殊情形．定理1．2．1［１］设为正整数．如果将个物体放入个盒子内，那么，或者第一个盒子至少含有个物体，或者第二个盒子至少含有个物体，…，或者第个盒子至少含有个物体．证明：设将个物体分放到个盒子中．如果对于每个，第个盒子含有少于个物体，那么所有盒子中的物体总数

6、不超过该数比所分发的物体总数少1，因此我们断言，对于某一个，第个盒子至少包含个物体．注意，能够将个物体用下面的方法分到个盒子中，对所有的第个盒子都不能含有个或更多的物体，我们可以通过将个物体放入第一个盒子，将个物体放入第二个盒子等来实现，抽屉原理的简单形式是由其强化形式的通过使得到的，由此有．在初等数学中抽屉原理的加强形式最常用于都等于同一个整数的特殊情况．在这种情况下，该定理叙述如下：推论1．2．1［１］如果个物体放入个盒子中，那么至少有一个盒子含有个或更多的物体．等价的，推论1．2．2［１］如果个非负整数的平均

7、数大于：那么至少有一个整数大于或等于．这两种表述之间的联系可以通过取个物体并放入个盒子中得到．对于，令是第个盒子中的物体个数．于是这个数的平均数为由于这个平均数大于，故而有一个整数至少是．换句话说，这些盒子中有一个盒子至少含有个物体．推论1．2．3［１］如果个非负整数的平均数小于：那么至少有一个整数小于．推论1．2．4［１］如果个非负整数的平均数至少等于，那么这个整数至少有一个满足．推论1．2．5［２］个物体放入个盒子中，则至少有一个盒子中有不少于个物体．注：符号表示不超过实数的最大整数．证明：（反证法）若不然，则

8、每一个集合中最多有个物体，这时，个盒子中就最多有个物体．因为，所以，这与已知条件个物体放入个盒子中矛盾，故上述推论成立．抽屉原理的形式比较多变，在具体的应用中也会有不同的变化，但本质上都是一样的．上述定理及推论的证明均采用反证法，这种证明方法对于证明元素个数多于抽屉个数的问题时有其普遍意义，平均重叠原则［３］：把一个量任意分成份，则其中至少有一份不大于，也至