抽屉原理的应用与推广-毕业论文.doc

1、目 录1 引言 .12 抽屉原理的形式 .13 抽屉原理在高等数学中的应用 .33.1 数论问题中的应用 .33.2 高等代数中的应用 .63.3 集合论中的应用 .83.4 不等式中的应用 .94 抽屉原理的推广 .104.1 抽屉原理在无限集上的推广 .114.2 抽屉原理的推广定理- 定理 .12Ramsey5 抽屉原理在实际生活中的应用 .15参考文献 .17致谢 .18i抽屉原理的应用与推广Xxxxxx 系本 xxxxx 班 xxxxxx指导教师： xxxxxxx摘 要 ： 本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重简述其在数论和高等数学及无限集中的应用，及在生活中的应

2、用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey 定理。关键词： 抽屉原理，有限集，无限集，Ramsey 定理。The Drawer of the principle of promotionLi xxxxxxxxxxxClass xxxx, Mathematics DepartmentTutor: xxxxxxxxxxAbstract: This paper introduces the widespread use of simple forms and all kinds of extended forms of the drawer princ

3、iple, focusing on the application of The drawer principle in the number theory, higher mathematics and infinite seta, 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 Rams

4、ey theorem.Key words: the drawer principle, finite set, infinite sets, Ramey theorem.01 引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理。它是由德国著名数学家狄利克雷首先发现的，因此也叫狄利克雷原理。抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学中的应用进行了梳理，将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好的理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的 定理及

5、其推广。Ramsey2 抽屉原理的形式什么是抽屉原理？举个简单的例子说明，就是将 3 个球放入 2 个篮子里，无论怎么放，必有一个篮子中至少要放入 2 个球，这就是抽屉原理。或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼有粮食或两只以上的鸽子，这也是鸽巢原理这一名称的得来。抽屉原理简单直观，很容易理解。而这个看似简单的原理在高等数学中有着很大的用处，对于数论、高等数学、集合论以及无限集中的复杂问题，可以利用抽屉原理巧妙的解答出来。下面首先从抽屉原理的形式入手，然后研究它在高等数学中的应用。我们最常用的抽屉原理只是抽屉原理的简单形式，就是将 个元素或者1n更多的元素放入

6、 个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素。n除了这种普遍的形式外，抽屉原理还有其他形式的推广、原理及形式。推广 1 若将 个物品放入 个盒子中，则至少有一个盒子中有1)(rnn个物品。r推广 2 设 是 个整数，而且 ,则12,nm 121nmr中至少有一个数不小于 .1,nm r推广 3 若将 个物品放入 个盒子中，则至少有一个盒子中有不少于 个nm物品。其中， 是不少于 的最小整数。nn1原理 1 把多于 ( 乘以 )个的物体放到 个抽屉里，则至少有一个抽mnn屉里有 个或多于 个的物体。1原理 2 把无穷多个元素放入有限个集合里，则一定有一个集合里含有无穷多个元素。原理 3

7、 把 个物体放入 个抽屉中，其中必有一个抽屉中至多有)1(mnn个物体。)1(m原理 4 设 是两个有限集合，对于任意从 到 的函数 ，D 必有NM, MNf个元素 ,使得 .i,21ia /)()(21idffdf原理 5 设 为无限集， 为有限集，对于任意有 到 的函数 ，用f表示 的值域，则 的各个元素的原象的集合中，必有一个是无限集。MNfMN原理 6 设 是不可数集， 是有限集或可数集，对于任意从 到 的MN函数 ，用 表示 的值域，则 的各个元素的原象的集合中，必有一个是ff不可数集。原理 7 设 同是不可数(或可数)集, ,对于任意从 到NM、 K的函数 , 中必有两个元素 ,

8、,使 .Nf 1m2)()21mff原理 8 设 都是正整数，如果把 个物品放n,21 1n入 个盒子，那么或者第 1 个盒子至少包含 个物品，或者第 2 个盒子至少包n 1含 个物品，或者第 个盒子至少包含 个物品。2mnm形式 1 个元素分为 个集合中，那么至少有一个集合中存在/mn个元素。形式 2 个元素分为 个集合中，几种必有一个集合中元素个数大于或等k于 ./kn形式 3 元素分为 个集合，那么必有一个 ,在121nm ni)1(n第 个集合中元素的个数 .i iib2形式 4 设有无穷多个元素按任一确定的方式分成有限个集合，那么至少有一个集合含有无穷多个元素。3 抽屉原理在高等数学

9、中的应用以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中的数论、集合论、高等数学、不等式这四个方面的应用。3.1 数论问题中的应用狄利克雷定理 为无理数，则对任意的正整数 ，存在整数 ，n)(nqp、满足 .（狄利克雷是经典的数论问题） 。而抽屉原理的应用是：如果npq1有 个正整数 被 除，则必有两个 设为 对模 同余，即121,na (ija、 )，因此， .)(modaji)(ji例 1 证明 任意五个整数中，必有三个整数的和是 3 的倍数。分析与证明 任一

10、整数被 3 除余数只可能是 0,1,2.若给定的五个整数被 3除所得的余数中 0,1,2 都出现，那么余数分别为 0,1,2 的三个数的的和一定能被3 整除，如果余数中至多出现，0,1,2,中的两个，那么由抽屉原理，其中必有一个余数至少出现三次，而这余数相同的三个数的和一定能被 3 整除。因此在任意五个整数中，必有三个整数的和是 3 的倍数。例 2 中国剩余定理 令 和 为两个互素的正整数，并令 和 为整数，()mnab且 以及 ,则存在一个正整数 ，使得 除以 的余数是 ,并10ma10bxma且 除以 的余数为 .即 可以写成 的同时又可以写成 的xnxapxqnx形式，这里 和 是整数。

11、pq分析与证明 为了证明这个结论考虑 个整数n ,)1(,2, aa这些整数中的每一个除以 都余 ，设其中的两个除以 有相同的余数 ，令这manr两个数为 和 ,其中 ,aij 10ji因此,存在两整数 和 ,使得 及 ，这两个方iqj rqirqajmi3程相减可得 .nqmijij)()(于是 是 的一个因子，由于 和 没有除 1 之外的公因子，因此nm是 的因子，然而， 意味着 ，也就是说 不可ij10ji0nij n能是 的因子，该矛盾产生于我们的假设： 个整数中有两个除以 会有相同的余数。因此这 个数中amnama)1(,2, n的每一个数除以 都有不同的余数，根据抽屉原理， 个数

12、中的每一1,0n个作为余数都要出现，特别地，数 也是如此。令 为整数，满足 ，bpp且使数 除以 余数为 ，则对于某个适当的 ，有apmxnq.bx因此， 且 ，从而 具有所要求的性质。qxx例 3 求证 在有 40 个不同的正整数所组成的等差数列中,至少有一项不能表示成 的形式。)(2Nlkl、证明 假设存在一个各项不同且均能表示成 的形式的 40 项)(32Nlkl、等差数列。设这个等差数列为 ，其中， .da39, da、设 , ,其中, 表示不qpda329 )39(log),(log2nmx超过实数 的最大整数。则 .x,接下来研究这个数列中最大的 14 项 .dada,27,6首先

13、证明 中至多有一个不能表示成 或da39,27,6 lm32的形式。)(32Nlkn、若 中的某一个 ( )不能表示da, hda9,726成 或 的形式,由假设知一定存在非负整数 ,使得lm)(lkn、 cb、.cbh2由 的定义可知 又因为 不能表示成 或n、 .,ncmbcbhda2lm324的形式,所以nk32.1,ncmb若 ,则 b 123nmbhda4)39(log)39(log21dada1)39(127da6与 矛盾。dadah39,27,若 ,则 2nc 132nmcbda9)39(log)3(log2 dada11)39(8da1426与 矛盾。dadah39,7,因此,

14、只有 .1,ncmb故 中至多有一个不能表示成)39276(hda或 的形式。lm)(32Nlkn、所以, 中至少有 13 个能表示成),(或 的形式。lm)(lkn、由抽屉原理知，至少有七个能表示成 或 中的同一种lm32)(Nlkn、5形式。（1） 有七个能表示成 的形式。lm32设 ，其中， .71,32lllm 721ll则 是某个公差为 的 14 项等差数列中的七项,721ll d所以, .显然, .17lld5217ll故 矛盾。dlllll 3)(3)3(13 12175 (2) 有七个能表示成 的形式。nk2设 ,其中, .knk,271 721kk则 是某个公差为 的 14

15、项等差数列中的七项。71 d而 ,矛盾。dd kkk 3)(3)2(3 1221715 综上,假设不成立.故原题得证。3.2 高等代数中的应用例 4 已知齐次线性方程组121221220nnnaxaxxx 其中 ,证明存在不全为零的整数,0,1,ijaij 适合nx21,2)2,(2njni 证明令 ， ，nijaA2)(122nxXxnO06则该齐次线性方程组可写成 0AX设集合 S= njnxXjn2,1,:21D= :X SnjjnjjjjxaxaAX21211映射 是一个满射.显然 = ,因为 -1，0，1，所以对:SDXAfSn2)1(ja1每个 X S，它的 2n 个分量适合212

16、21nijiiinaxaxx122n （i=1,2, ,n）n因此 又D)4(2nnn )14()4(1222 根据抽屉原理 映射形式设 和 是两个有限集，如果 那么对从 到ABABA的任何满映射 ，至少存在 , ,使 .Bf1a2)(21affS 中至少存在两个不同的元njjjniii xxXxx221221,使 ,即 .)(jifxf0)(,jijiA7令 ，则 即是我们所要求的， 是njijinxx221221n221 n2,1不全为零的整数，且满足 .),2(knxajkijkik 例 5 设 为 阶方阵，证明存在 1 ，使秩 =秩 =秩AiA(1i)(2iA证明 因为 阶方阵的秩只能

17、是 这 +1 个数之一。nn,2,0 令 ,E120,nAA的个数多于秩的个数，由抽屉原理可知，存在 , 满足E kl1 使 kl秩 = 秩 ,(A)(l)但秩 秩 秩 ,k1k(lA)所以秩 =秩 ,()()利用此式与秩的性质得 秩 秩 +秩 -秩 ,这里的BC()(BC)()是任意三个可乘矩阵，用数学归纳法可证 CBA,秩 =秩 .其中 为非负整数，(mkA)(1mk)故命题的结论成立. 秩 =秩 =秩 =.i(1iA)(2i)3.3 集合论中的应用从集合论的原理来讨论抽屉原理,主要应用集合论的映射来阐述抽屉原理,有在倍数问题、几何问题、涂色问题、经济问题等方面的应用，本文主要介绍倍数问题和经济问题。例 6（倍数问题的应用） 自 1 至 100 这一百个自然数中，如果任取 51 个数，那么其中至少有两个数，使一个数是另一个数的倍数。证明 我们知道形如 （ 为自然数， ）的数之间有倍数关系，np2,21n