《抽屉原理及其应用数学与应用数学专业毕业设计毕业论文》由会员分享，可在线阅读，更多相关《抽屉原理及其应用数学与应用数学专业毕业设计毕业论文（30页珍藏版）》请在金锄头文库上搜索。
1、 本科毕业论文 论文题目： 抽屉原理及其应用 学生姓名： 学号： 专业： 数学与应用数学 指导教师： 学 院： 数学科学学院 1 2012 年 5 月 20 日 毕业论文内容介绍 论文题目抽屉原理及其应用 选题时间2011.10.25完成时间2012.5.18 论文（设计） 字数 12750 关 键 词 抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey 定 理；应用 论文题目的来源、理论和实践意义： 题目来源：学生自拟 研究意义： 研究抽屉原理在高等数学中数论、离散数学、高等代数、抽象代数等多个学科中的运 用，对其在高等数学各方面的运用进行较为全面的梳理总结，加深对抽屉原理的理解，使
2、 复杂的数学问题能够在抽屉原理的作用下得到灵活巧妙的解决. 论文（设计）的主要内容及创新点： 主要内容： 本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散 数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题， 并根据抽屉原理的不足之处引入抽屉原理的推广定理 Ramsey 定理. 创新点： 以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文的主要创新 点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结. 生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取 与生活贴近的如赛程安排、资
3、源分配等问题进行阐述，更好地突出抽屉原理在实际生活中 的用处. 附：论文本人签名： 2012 年 5 月 20 日 目录 中文摘要1 英文摘要1 1.引言2 2.抽屉原理的形式2 3.抽屉原理在高等数学中的应用3 3.1 数论中的应用 3 3.2 离散数学中的应用 5 3.3 高等代数中的应用 8 3.4 抽象代数中的应用 9 4.抽屉原理在生活中的应用 10 5.抽屉原理的推广定理Ramsey 定理 12 6.参考文献 16 0 抽屉原理及其应用 XXX 摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其 在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以
4、巧 妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理 Ramsey 定理. 关键词：抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey 定理； 应用 Dirichlet drawer principle and the application of it XXX Abstract:This paper introduces the widespread use of simple forms and all kinds of extended forms of Dirichlet drawer principle,focusing on the applicatio
5、n of Dirichlet drawer principle in the number theory ,discrete mathematics, hight algebra and abstract algebra ,and also the real life. It can solve ably some complicated problems,and according to the principle of drawer the shortcomings of the principle of introducing the drawer theorem Ramsey theo
6、rem. Keywords:Dirichlet drawer principle; Number theory; Discrete mathematics; Higher algebra; Abstract algebra; Ramsey theorem; Application. 1 1.1.引言引言 抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重 要的原理.它是由德国著名数学家狄利克雷(P.G.T.Dirichlet 1805-1855)首先发 现的，因此也叫作狄利克雷原理. 抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数 论、组合论以及集合论等领域中有
7、着广泛应用，在高等数学的其它几门学科领 域中也是解决问题的有效方法. 本文总结了如何运用抽屉原理解决数论、离散数学、高等代数及抽象代数 中的问题，对抽屉原理在高等数学中的应用进行了梳理，将抽屉原理的解题思 路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽 屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的 Ramsey 定理. 2.2.抽屉原理的形式抽屉原理的形式 什么是抽屉原理？先举个简单的例子说明，就是将 3 个球放入 2 个篮子里， 无论怎么放，必有一个篮子中至少要放入 2 个球，这就是抽屉原理.或者假定一 群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一
8、个鸽笼里有两 只或两只以上的鸽子，这也是鸽巢原理这一名称的得来. 抽屉原理简单直观，很容易理解.而这个看似简单的原理在高等数学中有着 很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题， 可以利用抽屉原理巧妙的解答出来. 下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用. 我们最常用的抽屉原理只是抽屉原理的简单形式，就是将 n+1 个元素或者 更多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素. 除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式. 陈景林、阎满富在他们编著的组合数学与图论一书中将抽屉原理抽象 概括成以下三种形式1:
9、原理 1. 把多于个的元素按任一确定的方式分成个集合，则一定有一个nn 集合中含有两个或两个以上的元素. 原理 2. 把个元素任意放到个集合里，则至少有一个集合里至mn)(nm 少有个元素，其中k 2 原理 3. 把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合 中仍含无穷个元素. 卢开澄在组合数学 （第三版）中将抽屉原理（书中称为鸽巢原理）又进 行了推广2. 鸽巢原理：设 k 和 n 都是任意正整数，若至少有 kn+1 只鸽子分配在 n 个鸽 巢中，则至少存在一个鸽巢中有至少 k+1 只鸽子. 推论 1.有 m 只鸽子和 n 个鸽巢，则至少有一个鸽巢中有不少于+1 只 n m 1
10、 鸽子. 推论 2.若将 n(m-1)+1 个球放入 n 个盒子里，则至少有一个盒子有 m 个球. 推论 3.若是 n 个正整数，而且，则 12 , n m mm 12n mmm n 中至少有一个数不小于 r. 12 , n m mm 另外，抽屉原理还可以用映射的形式来表示，即:设和是两个有限集，AB 如果，那么对从到的任何满射，至少存在,使ABABf 1 a 2 a . 12 f af a 3.3.抽屉原理在高等数学中的应用抽屉原理在高等数学中的应用 以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来， 在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们 通过一
11、些比较典型的实例来说明抽屉原理在高等数学中数论、离散数学、高等 代数以及抽象代数这五个方面的应用. 3.13.1 数论问题中的应用数论问题中的应用 例例 1 1.任意 5 个整数中，有其中 3 个整数的和为 3 的倍数. 证明证明 1 m nm n k m nm n , 当能整除时, , 当不能整除时. 3 将整数分为形如 3k、3k+1 及 3k+2 这 3 类形式， 则我们可以将这 3 类整数看作是 3 个抽屉，将这 5 个整数看作元素放入这 3 个抽屉中. 由抽屉原理可知，至少存在 2=+1 个整数在同一抽屉中，即它们都是 3 15 形如（3k+m）的整数，m=0,1 或 2. 如果有
12、3 个以上的数在同一个抽屉中，则取其中的任意三个数，它们的和 是形如 3（3k+m）的整数，即三者的和为 3 的倍数. 如果有 2 个整数在同一个抽屉中，则由抽屉原理知，在余下的 3 个数中有 2 个数在同一个抽屉中，余下的 1 个数在另一个抽屉中.在 3 个抽屉中各取一个 数，这 3 个数的形式分别为 3k ,3k +1,3k +2,则三者的和为 3（k +k +k ） 123123 +3，即为 3 的倍数. 例例 2 2.设有两组整数，而且每一组的数都是小于 n（nZ ）的互不相同的数，这 两组数的数目个数n，则存在一对分别取自两组的数使这两个数的和为 n. 证明证明 设这两组数为a ,a
13、 ,a、b ,b ,b. 12 p 12 q 已知每一组的数都是小于 n（nZ ）的互不相同的数. 不妨设 a 那么对从 A 到 B 的任何满映AB 射 f，至少存在,使 f()=f().） 1 a 2 a 1 a 2 a S 中至少存在两个不同的元 nj j j j ni i i i x x x X x x x X 2 2 1 2 2 1 , 使,即,. ji xfxf ji AXAX 0 ji XXA 令，则即是我们所要求的，是 njni ji ji n xx xx xx 22 22 11 2 2 1 n2 2 1 n2, 21, 不全为零的整数，且满足 . nknxxxx jkikjki
14、kk 2 , 2 , 12 例例 7.7. 设为阶方阵，证明存在 1，使秩()=秩()=秩Anni i A 1i A )( 2i A 证明证明 因为阶方阵的秩只能是这+1 个数之一.nn, 2, 1, 0 n ,的个数多于秩的个数，由抽屉原理可知，存在,E 120 , nn AAAAAEk 满足 12,则存在最小正整数 R(p,q),使得当 nR(p,q)时，用红蓝两色涂的边，则或存在一个蓝色的,或存在一个红色 n K p K 的. p K Ramsey 定理（狭义）的内容任意六个人中要么至少三个人认识，要么至少 三个不认识. Ramsey 定理可以视为抽屉原理的推广，1947 年，匈牙利数学家把这一原理 引进到中学生数学竞赛中，当年匈牙利全国数学竞赛有一道这样的试题：“证 明：任何六个人中，一定可以找到三个互相认识的人，或者三个互不认识的人. ” 在1958 年 6-7 月号美国数学月刊同样也登载着这样一个有趣的问题 “任何六个人的聚会，总会有 3 人互相认识或 3 人互相不认识.”这就是著名的 Ramsey 问题. 这个问题乍看
