抽屉原理毕业论文.doc
《抽屉原理毕业论文.doc》由会员分享,可在线阅读,更多相关《抽屉原理毕业论文.doc(26页珍藏版)》请在三一文库上搜索。
1、材材 料料 清清 单单 一、毕业论文 二、毕业设计任务书 三、毕业设计开题申请表 四、毕业设计开题报告正文 声声 明明 本人 ,学号08109022,系襄樊学院数学与计算机科学 学院数学与应用数学专业0811班学生。所做论文内容主体均为 原创,无任何抄袭、剽窃他人劳动成果的行为。如有发现此类 行为,本人愿意为此承担一切道义及法律责任,特此声明。 学生签名: 年 月 日 1 抽屉原理及其应用抽屉原理及其应用 姓名: 专业:数学与应用数学 学号:08109038 指导老师:游学民 摘摘 要:要:抽屉原理是数学中的重要原理抽屉原理是数学中的重要原理, ,在解决数学问题时有非常重要的作用在解决数学问题
2、时有非常重要的作用. . 各种形式的抽屉原理在高等数学和初等数学中经常被采用各种形式的抽屉原理在高等数学和初等数学中经常被采用. .本文着重从抽屉的构本文着重从抽屉的构 造方法:造方法:等分区间、分割图形、利用等分区间、分割图形、利用“对称性对称性” 、 用整数性质、利用染色和用整数性质、利用染色和 根据问题的需要根据问题的需要阐述抽屉原理在高等数学和初等数学(竞赛题)中的应用阐述抽屉原理在高等数学和初等数学(竞赛题)中的应用, ,同时同时 指出了它在应用领域中的不足之处指出了它在应用领域中的不足之处: :抽屉的构造有一定的难度抽屉的构造有一定的难度, ,这就要求我们必这就要求我们必 须要求有
3、一定的数学功底须要求有一定的数学功底, ,甚至复杂的需要大量的演算甚至复杂的需要大量的演算, ,因此抽屉原理不能充分因此抽屉原理不能充分 的运用到我们日常生活中去的运用到我们日常生活中去. . 关键词关键词 :抽屉原理:抽屉原理; ;高等数学高等数学; ; 初等数学初等数学 2 The principle of drawer and its application Abstract:Drawer principle is the important principle of mathematics in solving mathematical problems, has a very imp
4、ortant role. All forms of drawer principle in Higher Mathematics and elementary mathematics is often used. This article emphatically from the drawer construction methods: equal interval, segmentation graph, using the“ symmetry“, with properties of the integers, using staining and according to proble
5、ms on the drawer principle in Higher Mathematics and Elementary Mathematics ( contest ) application, and points out that it is in the field of application of the deficiencies: drawer structure has certain difficulty, this asks we must have some math skills, even complex requires a large amount of ca
6、lculation, therefore the drawer principle can not full use of our daily life. Key Words:the principle of drawer; advanced mathematics; primary mathematics 3 目目 录录 1抽屉原理抽屉原理.1 1.1 抽屉原理的简单形式.1 1.2 抽屉原理的加强形式.2 2抽屉原理的应用抽屉原理的应用.4 2.1 抽屉的构造.4 2.2 抽屉原理在数学解题中的应用.10 3.抽屉原理在生活中的应用抽屉原理在生活中的应用 14 3.1 月黑穿袜子.14 3
7、.2 手指纹和头发.14 3.3 电脑算命15 4总结总结15 参考文献参考文献16 致致 谢谢 17 4 前言前言 抽屉原理又叫做鸽巢原理,指的是一件简单明了的事实:为数众多的鸽子 飞进为数不多的巢穴里,则至少有一个巢穴飞进了两只或者更多的鸽子。其实 有关于抽屉原理(鸽巢原理)的阐释,粗略的说就是如果有许多物体放进不足 够多的盒子内,那么至少有一个盒子被两个或多个盒子占据。抽屉原理在我们 日常生活中已经运用的比较广泛了,它往往和我们数学结合在一起为我们日常生 活带来了不小的便利。我将主要叙述一下抽屉原理的具体的形式、构造方法以 及他在我们生活中的一些具体的应用。希望大家能对抽屉原理有一个更加
8、清晰 的了解并能运用到我们的日常生活中去。 1.1.1.1.抽屉原理的简单形式抽屉原理的简单形式 抽屉原理的最简单的形式如下 定理 1鸽巢原理鸽巢原理(组合数学,)如果个物体放进个盒子,那么至少有1nn 一个盒子包含两个或更多的物体 证明:(用反证法)如果个盒子中每个盒子至多放一个物体,则放入个nn 盒子中的物体总数至多为个这与假设有个物体矛盾从而定理得证n1n 注意,无论是抽屉原理还是它的证明,对于找出含有两个或更多物体的盒 子都没有任何帮助我们只是简单断言,如果人们检查每一个盒子,那么他们 会发现有的盒子,里面放有多于一个的物体抽屉原理只是保证这样的盒子存 在因此,无论何时抽屉原理被用来证
9、明一个排列或某种现象的存在性,除了 考察所有的可能性外,它都不能对任何构造排列或寻找现象的例证给出任何指 示 还要注意,抽屉原理的结论不能被推广到只存在个(或更少)物体的情n 形这是因为我们可以把不同的物体放到个盒子的每一个中去当然,在这n 些盒子中可以这样分发物体:一个盒子放入两个物体,但对任意分发这是没有 保证的抽屉原理只是断言,在个盒子中去论如何分发个物体,总不能n1n 5 避免把两个物体放进同一个盒子中去 还存在一些与抽屉原理相关的其它原理,有必要正式叙述如下 (1) 如果将个物体放入个盒子并且没有一个盒子是空的,那么每个盒子nn 恰好包含一个物体 (2) 如果将个物体放入个盒子并且没
10、有盒子被放入多于一个的物体,那nn 么每个盒子里有一个物体 现在把所阐明的这三个原理更抽象的表述为: 令和是两个有限集,并令是一个从到得函数XY:fXYXY (1)如果的元素多于的元素,那么就不是一对一的XYf (2)如果和含有相同个数的元素,并且是映上的,那么就是一对XYff 一的 (3)如果和含有相同个数的元素,并且是一对一的,那么就是映上XYff 的 1.2.1.2.抽屉原理的加强形式抽屉原理的加强形式 下列定理包含定理 2.作为它的特殊情形 定理 2.鸽巢原理鸽巢原理(组合数学)设为正整数如果将 12 , n q qq 个物体放入个盒子内,那么,或者第一个盒子至少含有 12 1 n q
11、qqnn 个物体,或者第二个盒子至少含有个物体,或者第个盒子至少含有 1 q 2 qn 个物体 n q 证明:设将个物体分放到个盒子中如果对于每个 12 1 n qqqnn ,第 个盒子含有少于个物体,那么所有盒子中的物体总数不超12,in,i i q 过 1212 111 nn qqqqqqn()()() 该数比所分发的物体总数少 1,因此我们断言,对于某一个,第 个12,in,i 盒子至少包含个物体 i q 注意,能够将个物体用下面的方法分到个盒子中,对 12n qqqnn 所有的第 个盒子都不能含有个或更多的物体,我们可以通过将12,in,i i q 个物体放入第一个盒子,将个物体放入第
12、二个盒子等来实现,抽屉 1 1q 2 1q 6 原理的简单形式是由其强化形式的通过使得到的,由此有 12 .2 n qqq 12 1211 n qqqnnnn 在初等数学中抽屉原理的加强形式最常用于都等于同一个整数 12 , n q qq 的特殊情况在这种情况下,该定理叙述如下:r 推论 1 如果个物体放入个盒子中,那么至少有一个盒子含11n r n 有个或更多的物体等价的,r 推论 2如果个非负整数的平均数大于:n 12 ,., n m mm 1r 12 . 1 n mmm r n 那么至少有一个整数大于或等于r 这两种表述之间的联系可以通过取个物体并放入个盒子中得11n r n 到对于,令
13、是第 个盒子中的物体个数于是这个数12,in, i mim 的平均数为 12 ,., n m mm 12 .(1) 11 (1) n mmmn r r nnn 由于这个平均数大于,故而有一个整数至少是换句话说,这些盒子1r i mr 中有一个盒子至少含有个物体r 推论 3. 如果个非负整数的平均数小于:n 12 ,., n m mm1r 12 . 1 n mmm r n 那么至少有一个整数小于1r 推论 4 如果个非负整数的平均数至少等于,那么这个n 12 ,., n m mmrn 整数至少有一个满足 12 ,., n m mm i mr 推论 5 个物体放入个盒子中,则至少有一个盒子中有不少
14、于mn 个物体 1 1 m n 注:符号表示不超过实数的最大整数 xx 证明:(反证法)若不然,则每一个集合中最多有个物体,这时, 1m n 7 个盒子中就最多有个物体n 1m n n 因为,所以,这与已知 11mm nn 11 1 mm nnmm nn 条件个物体放入个盒子中矛盾,故上述推论成立mn 抽屉原理的形式比较多变,在具体的应用中也会有不同的变化,但本质上 都是一样的 上述定理及推论的证明均采用反证法,这种证明方法对于证明元素个数多 于抽屉个数的问题时有其普遍意义, 平均重叠原则:把一个量任意分成份,则其中至少有一份不大于Sn ,也至少有一份不少于 S n S n 不等式重叠原则:若
15、,且,则,至, , ,a b c dRacbdabcd 少有一个成立 面积重叠原则:在平面上有个面积分别是,的图形,把n 1 A 2 A n A 这个图形按任何方式一一搬到某一个面积为的固定图形上去,nA (1)如果,则至少有两个有公共点; 12 . n AAAA (2)如果,则固定图形中至少有一个点未被盖住 12 . n AAAA 2 2抽屉原理的应用抽屉原理的应用 应用抽屉原理的基本思想是根据不同问题自身特点,洞察问题本质,先弄 清对哪些元素进行分类,再找出分类的规律,即所谓的构造抽屉,构造抽屉是 应用抽屉原理的关键在介绍抽屉原理的应用之前,本文先用几个具体的例子 来介绍几种常用的构造抽屉
16、的方法 2.1 抽屉的构造抽屉的构造 2. .1.1 等分区间制造抽屉等分区间制造抽屉 当问题的结论与区间有关时,可等分某个区间,设计出若干个抽屉 例 1 求证:对于任给的正无理数及任意大的自然数,存在一个有n 理数,使得 k m 1k mmn 8 证明:把区间(0,1)进行等分,得个小区间nn 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 pp
17、in 和,它们的差的绝对值小于,即 11 pp 22 pp 1 n 1212 1 ()()pppp n 设,则 1212 ,ppmppk ,即 1 mk n 1k mmn 上述例子涉及区间问题,把区间(0,1)进行等分,得个小区间,自然nn 就得到了个抽屉,而个数可以作为个物体,此处可以利用抽屉原理n1n1n 解决问题 2.1.22.1.2 分割图形构造抽屉分割图形构造抽屉 在一个几何图形内有若干已知点,我们可以根据问题的要求把图形进行适 当的分割,用这些分割成的图形作为抽屉,再对已知点进行分类,集中对某一 个或几个抽屉进行进行讨论,使问题得到解决 例 2 在边长为 2 米的正方形内,任意放入
18、 13 个点求证:必有 4 个 点,以它们为顶点的四边形的面积不超过 1 平方米 9 (1) (2) 证明:把边长为 2 米的正方形分割成面积为 1 平方米的 4 个小正方形,如 图 1因为 13=34+1,所以由抽屉原理知,至少有 4 个点落在同一个面积为 1 平方米的小正方形内(或边上),以这 4 个点为顶点的四边形的面积总小于或 等于小正方形的面积,即以这 4 个点为顶点的四边形的面积不超过 1 平方米 注:此例是通过分割图形构造抽屉 将正方形等分成 4 个矩形来制造抽屉 也可以解决本题,如图 2 2.1.32.1.3 利用利用“对称性对称性”构造抽屉构造抽屉 “对称性”是数学中常用的处
19、理问题的一种方法同样,在构造抽屉的过 程中也可以利用“对称性”来解决问题,这种方法不易观察,需要不断的训 练 例 3 九条直线中的每一条直线都把正方形分成面积比为 2:3 的两个 四边形证明:这九条直线中至少有三条经过同一点 证明:如图,设是一条这样的这样的直CD 线我们再画出这两个梯形的中位线,因这两AB 个梯形有相等的高,所以他们的面积比应等于对 应的中位线长的比,即等于(或者)因:AP PB:BP PA 为点有确定的位置,它在正方形一对对边中点P 的连线上,并且,由几何上的对称性,:2 3AP PB : 这种点共有 4 个,即图中的已知的九, ,P Q R S 条适合条件的分割直线中的每
20、一条必须过 这 4 点中的一点把当成 4 个抽屉,9 条直线当成 9 个物体,, ,P Q R S, ,P Q R S 10 即可看出必有 3 条分割直线经过同一个点 正方形是个比较规则的图形,在正方形中有很多对称关系,对解题减小了 一点难度。 2.1.42.1.4 用整数性质制造抽屉用整数性质制造抽屉 当问题与整数性质有关时,我们可以用整数的性质,把题目中的数设计成 一些抽屉,然后用抽屉原理去解 (1)划分数组制造抽屉 仔细观察题目中的数,如果题中数据具有一定的规律,可以划分数组构造 抽屉 例 4 从 1,2,3, 98 中任取 50 个不同的数,试证:其中必有两个 数,它们之差等于 7 证
21、明:先把所给的 98 个数设计成 49 个抽屉:(1,8),(2,9) (3,10),(4,11),(21,28),(91,98),可以发现每个抽 屉里的两个数之差为 7 从 1,2,3,98 中任取 50 个,就是从这 49 个抽屉中任取 50 个数,由 抽屉原理知,必有一个抽屉中要取出两个数,即这 50 个数中必有两个数,它们 之差为 7 本题的关键就是对这 98 个数进行合理分类,构造抽屉分类的原则是每个 抽屉中的两个数只差是 7,且抽屉的个数少于任取的数的个数 (2)按同余类制造抽屉 把所有整数按照除以某个自然数的余数分为类,叫做的剩余类或同mmm 余类,用0,1,2,m-1表示每一个
22、类含有无穷多个数在研究 与整除有关的问题时,常按同余类制造抽屉 例 5任意 10 个自然数中,总有两个数的差是 9 的倍数 证明:要使两个自然数的差被 9 整除,必须使两个自然数被 9 除的余数相 同于是我们考虑把自然数按除以 9 所得的余数 0、1、2、3、8 进行 分类,也就是 9 个抽屉根据抽屉原理,任意 10 个自然数中,必有两个数除以 9 所得的余数相同因此这两个数的差一定是 9 的倍数 11 本题的特点比较明显,很容易想到利用同余类制造抽屉 2.1.52.1.5 利用染色制造抽屉利用染色制造抽屉 我们可以把将物体放入盒子改为用中颜色中的每一种颜色对每一个物体n 染色此时抽屉原理断言
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 抽屉 原理 毕业论文
链接地址:https://www.31doc.com/p-3930417.html