《抽屉原理及其应用论文草案.doc》由会员分享，可在线阅读，更多相关《抽屉原理及其应用论文草案.doc（19页珍藏版）》请在金锄头文库上搜索。
1、目录 1抽屉原理 1 11 抽屉原理的简单形式 1 12 抽屉原理的加强形式 2 2抽屉原理的应用 4 21 抽屉的构造4 211 等分区间制造抽屉 4 212 分割图形构造抽屉 5 213 利用“对称性”构造抽屉 6 214 用整数性质制造抽屉7 215 利用染色制造抽屉 8 216 根据问题的需要制造抽屉 9 22 抽屉原理在数学解题中的应用10 221 解决代数问题10 222 解决数论问题11 223 解决几何问题12 224 多次顺向运用抽屉原理12 225 逆向运用抽屉原理 13 23 抽屉原理在生活中的应用13 231 月黑穿袜子 13 232 手指纹和头发14 233 电脑算命
2、14 3总结15 参考文献 16 致 谢17 1 1抽屉原理抽屉原理 抽屉原理又叫做鸽巢原理，指的是一件简单明了的事实：为数众多的鸽子 飞进为数不多的巢穴里，则至少有一个巢穴飞进了两只或者更多的鸽子，其实 有关于抽屉原理（鸽巢原理）的阐释，粗略的说就是如果有许多物体放进不足 够多的盒子内，那么至少有一个盒子被两个或多个盒子占据。我将在下面的论 文当中给出更加精确的叙述。 1 11 1 抽屉原理的简单形式抽屉原理的简单形式 抽屉原理的最简单的形式如下 定理 111 如果个物体放进个盒子，那么至少有一个盒子包含1nn 两个或更多的物体 证明：（用反证法）如果个盒子中每个盒子至多放一个物体，则放入n
3、 个盒子中的物体总数至多为个这与假设有个物体矛盾从而定理得nn1n 证 注意，无论是抽屉原理还是它的证明，对于找出含有两个或更多物体的盒 子都没有任何帮助我们只是简单断言，如果人们检查每一个盒子，那么他们 会发现有的盒子，里面放有多于一个的物体抽屉原理只是保证这样的盒子存 在因此，无论何时抽屉原理被用来证明一个排列或某种现象的存在性，除了 考察所有的可能性外，它都不能对任何构造排列或寻找现象的例证给出任何指 示 还要注意，抽屉原理的结论不能被推广到只存在个（或更少）物体的情n 形这是应为我们可以把不同的物体放到个盒子的每一个中去当然，在这n 些盒子中可以这样分发物体：一个盒子放入两个物体，但对
4、任意分发这是没有 保证的抽屉原理只是断言，在个盒子中去论如何分发个物体，总不能n1n 避免把两个物体放进同一个盒子中去 还存在一些与抽屉原理相关的其它原理，有必要正式叙述如下 (1) 如果将个物体放入个盒子并且没有一个盒子是空的，那么每个盒子nn 恰好包含一个物体 (2) 如果将个物体放入个盒子并且没有盒子被放入多于一个的物体，那nn 么每个盒子里有一个物体 现在把所阐明的这三个原理更抽象的表述为： 令和是两个有限集，并令是一个从到得函数XY:fXYXY （1）如果的元素多于的元素，那么就不是一对一的XYf （2）如果和含有相同个数的元素，并且是映上的，那么就是一对XYff 一的 （3）如果和
5、含有相同个数的元素，并且是一对一的，那么就是映XYff 上的 1 12 2 抽屉原理的加强形式抽屉原理的加强形式 下列定理包含定理 111 作为它的特殊情形 定理 121 设为正整数如果将 12 , n q qq 个物体放入个盒子内，那么，或者第一个盒子至少含 12 1 n qqqnn 有个物体，或者第二个盒子至少含有个物体，或者第个盒子至少含 1 q 2 qn 有个物体 n q 证明：设将个物体分放到个盒子中如果对于每 12 1 n qqqnn 个，第 个盒子含有少于个物体，那么所有盒子中的物体总数不12,in，i i q 超过 1212 111 nn qqqqqqn（）（）（） 该数比所分
6、发的物体总数少 1，因此我们断言，对于某一个，第 个12,in，i 盒子至少包含个物体 i q 注意，能够将个物体用下面的方法分到个盒子中，对 12n qqqnn 所有的第 个盒子都不能含有个或更多的物体，我们可以通过将12,in，i i q 个物体放入第一个盒子，将个物体放入第二个盒子等来实现，抽屉 1 1q 2 1q 原理的简单形式是由其强化形式的通过使得到的，由此有 12 .2 n qqq 12 1211 n qqqnnnn 在初等数学中抽屉原理的加强形式最常用于都等于同一个整数 12 , n q qq 的特殊情况在这种情况下，该定理叙述如下：r 推论 121 如果个物体放入个盒子中，那
7、么至少有一11n r n 个盒子含有个或更多的物体等价的，r 推论 122如果个非负整数的平均数大于：n 12 ,., n m mm 1r 12 . 1 n mmm r n 那么至少有一个整数大于或等于r 这两种表述之间的联系可以通过取个物体并放入个盒子中得11n r n 到对于，令是第 个盒子中的物体个数于是这个数12,in， i mim 的平均数为 12 ,., n m mm 12 .(1) 11 (1) n mmmn r r nnn 由于这个平均数大于，故而有一个整数至少是换句话说，这些盒子1r i mr 中有一个盒子至少含有个物体r 推论 123 如果个非负整数的平均数小于：n 12
8、,., n m mm1r 12 . 1 n mmm r n 那么至少有一个整数小于1r 推论 124 如果个非负整数的平均数至少等于，n 12 ,., n m mmr 那么这个整数至少有一个满足n 12 ,., n m mm i mr 推论 125 个物体放入个盒子中，则至少有一个盒子中有不少mn 于个物体 1 1 m n 注：符号表示不超过实数的最大整数 xx 证明：（反证法）若不然，则每一个集合中最多有个物体，这时， 1m n 个盒子中就最多有个物体n 1m n n 因为，所以，这与已知 11mm nn 11 1 mm nnmm nn 条件个物体放入个盒子中矛盾，故上述推论成立mn 抽屉原
9、理的形式比较多变，在具体的应用中也会有不同的变化，但本质上 都是一样的 上述定理及推论的证明均采用反证法，这种证明方法对于证明元素个数多 于抽屉个数的问题时有其普遍意义， 平均重叠原则：把一个量任意分成份，则其中至少有一份不大于Sn ，也至少有一份不少于 S n S n 不等式重叠原则：若，且，则，至, , ,a b c dRacbdabcd 少有一个成立 面积重叠原则：在平面上有个面积分别是，的图形，把n 1 A 2 A n A 这个图形按任何方式一一搬到某一个面积为的固定图形上去，nA （1）如果，则至少有两个有公共点； 12 . n AAAA （2）如果，则固定图形中至少有一个点未被盖住
10、 12 . n AAAA 2 2抽屉原理的应用抽屉原理的应用 应用抽屉原理的基本思想是根据不同问题自身特点，洞察问题本质，先弄 清对哪些元素进行分类，再找出分类的规律，即所谓的构造抽屉，构造抽屉是 应用抽屉原理的关键在介绍抽屉原理的应用之前，本文先用几个具体的例子 来介绍几种常用的构造抽屉的方法 2 21 1 抽屉的构造抽屉的构造 2 21 11 1 等分区间制造抽屉等分区间制造抽屉 当问题的结论与区间有关时，可等分某个区间，设计出若干个抽屉 例 1 求证：对于任给的正无理数及任意大的自然数，存在一个有n 理数，使得 k m 1k mmn 证明：把区间（0，1）进行等分，得个小区间nn 11
11、22 31 0,.,1 n nn nn nn 由抽屉原理知，这些区间内的个数中，必有两个数落在某一个区间，1n 从而这两个数的差的绝对值小于 1 n 设，则由是正无理数得(1,2,.,1) i pN in 01 ii pp 所以这个数中，必有 2 个数，不妨设为1n(1,2,.,1) ii ppin 和，它们的差的绝对值小于，即 11 pp 22 pp 1 n 1212 1 ()()pppp n 设，则 1212 ,ppmppk ，即 1 mk n 1k mmn 上述例子涉及区间问题，把区间（0，1）进行等分，得个小区间，自nn 然就得到了个抽屉，而个数可以作为个物体，此处可以利用抽屉原n1n
12、1n 理解决问题 2 21 12 2 分割图形构造抽屉分割图形构造抽屉 在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适 当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一 个或几个抽屉进行进行讨论，使问题得到解决 例 2 在边长为 2 米的正方形内，任意放入 13 个点求证：必有 4 个 点，以它们为顶点的四边形的面积不超过 1 平方米 (1) (2) 证明：把边长为 2 米的正方形分割成面积为 1 平方米的 4 个小正方形，如 图 1因为 13=34+1，所以由抽屉原理知，至少有 4 个点落在同一个面积为 1 平方米的小正方形内（或边上），以这 4 个点为
13、顶点的四边形的面积总小于或 等于小正方形的面积，即以这 4 个点为顶点的四边形的面积不超过 1 平方米 注：此例是通过分割图形构造抽屉 将正方形等分成 4 个矩形来制造抽屉 也可以解决本题，如图 2 2 21 13 3 利用利用“对称性对称性”构造抽屉构造抽屉 “对称性”是数学中常用的处理问题的一种方法同样，在构造抽屉的过 程中也可以利用“对称性”来解决问题，这种方法不易观察，需要不断的训 练 例 3 九条直线中的每一条直线都把正方形分成面积比为 2：3 的两个 四边形证明:这九条直线中至少有三条经过同一点 证明：如图，设是一条这样的这样的直CD 线我们再画出这两个梯形的中位线，因这两AB 个
14、梯形有相等的高，所以他们的面积比应等于对 应的中位线长的比，即等于(或者)因:AP PB:BP PA 为点有确定的位置，它在正方形一对对边中点P 的连线上，并且，由几何上的对称性，:2 3AP PB ： 这种点共有 4 个，即图中的已知的九, ,P Q R S 条适合条件的分割直线中的每一条必须过这 4 点中的一点把, ,P Q R S 当成 4 个抽屉，9 条直线当成 9 个物体，即可看出必有 3 条分割直线, ,P Q R S 经过同一个点 正方形是个比较规则的图形，在正方形中有很多对称关系，对解题减小了 一点难度。 2 21 14 4 用整数性质制造抽屉用整数性质制造抽屉 当问题与整数性质有关时，我们可以用整数的性质，把题目中的数设计成 一些抽屉，然后用抽屉原理去解 （1）划分数组制造抽屉 仔细观察题目中的数，如果题中数据具有一定的规律，可以划分数组构造 抽屉 例 4 从 1，2，3，98 中任取 50 个不同的数，试证：其中必有两 个数，它们之差等于 7 证明:先把所给的 98 个数设计成 49 个抽屉：（1，8），（2，9） （3，10），（4，11），（21，28），（91，98），可以发现每个抽 屉里的两个数之差为 7 从 1，2，3，98 中任取 50 个，就是从这 49 个抽屉中任取
