抽屉原理.doc
- 文档编号:2503636
- 上传时间:2023-05-03
- 格式:DOC
- 页数:25
- 大小:850.48KB
抽屉原理.doc
《抽屉原理.doc》由会员分享,可在线阅读,更多相关《抽屉原理.doc(25页珍藏版)》请在冰点文库上搜索。
四川理工学院毕业论文
抽屉原理在数学竞赛中的应用
学生:
学号:
专业:
数学与应用数学
班级:
指导教师:
四川理工学院理学院
二O一五年六月
四川理工学院
毕业论文任务书
论文题目:
抽屉原理在数学竞赛中的应用
二级学院:
理学院专业:
数学与应用数学班级:
学号:
学生:
指导教师:
接受任务时间:
2015年3月20日
系主任(签名)教学院长(签名)
1.毕业论文的主要内容及基本要求
主要内容:
本文主要介绍了初等数论中的一个重要原理——抽屉原理。
首先对抽屉原理产生背景、所属学科、定义表示等进行了简单介绍和证明。
接着是解决抽屉问题的关键点——抽屉的构造,列举实例分别介绍了分组、按奇偶性、模的剩余类、图形分割的方法来进行抽屉的构造。
然后研究了抽屉原理在高等数学中几何、代数、数论、离散等学科中的重要应用,说明了抽屉原理的应用是十分广泛的。
分析了在数学竞赛中考察抽屉原理解决实际问题的考察方式。
对于其在解决一些复杂的存在性问题时不足之处,由Ramsey定理进行了补充,使其能够更好的应用与问题解决当中。
基本要求:
在明确了主要内容基础上要做到
(1)查阅文献资料,确定课题研究思路,了解课题前沿
(2)理清论文思路;(3)撰写出思路清晰,逻辑合理的论文.
2.指定查阅的主要参考文献及说明
[1]张禾瑞.近世代数基础[M].北京:
高等教育出版社,2012.
[2]王萼芳,石生明.高等代数(第三版)[M].北京:
高等教育出版社,2011.
[3]闵嗣鹤,严士健.初等数论(第三版)[M].北京:
高等教育出版社,2011.
[4]王传玉.离散数学基础(第2版)[M].合肥:
中国科学技术大学出版社,2010.
3.进度安排
论文各阶段名称
起止日期
1
确定论文题目,接受任务
2015年3月20日-2013年3月25日
2
查阅文献资料,完成文献综述和开题报告
2015年3月25日-2013年3月31日
3
完成论文初稿(手写稿)
2015年4月1日-2013年4月30日
4
完成论文修改稿至定稿
2015年5月1日-2013年6月4日
5
论文答辩
2015年6月5日-2013年6月11日
摘要
摘要
本文研究了抽屉原理及其应用,通过例题的形式对抽屉的构造进行介绍,并且针对高等数学中抽屉原理的应用进行了分类研究。
通过研究得到了抽屉原理解决数学竞赛问题的基本思路和方法,对于其在解决某些复杂问题的不足之处也用其推广——Ramsey定理进行了补充。
首先对抽屉原理的发展史和基本定义进行了简单的介绍,通过简单的例子对其定义进行理解,说明其主要用途和研究意义。
然后关于如何解决具体的抽屉原理题目提出了方法,主要通过分组、按奇偶性、模的剩余类、图形分割的方法来进行抽屉的构造。
接着对高等数学中所遇到的抽屉原理的题目进行分类总结,研究了其在几何、代数、数论、离散等学科中的重要应用,可以看到抽屉原理的适用范围是非常广泛的。
紧接着通过对历史典故和实际问题的研究,说明了在数学竞赛中抽屉原理的主要考察方式。
最后对抽屉原理进行了进一步补充。
在解决比较复杂的存在性题目时,抽屉原理可能会显得不适用,因此需要对其进行推广,本文由Ramsey定理进行了补充,使其能够更好的应用与问题解决当中。
关键词:
抽屉原理;抽屉构造;组合数学;数学竞赛;Ramsey定理
ABSTRACT
ThispaperstudiestheDrawerprincipleanditsapplication,throughtheformofexamplestointroducethestructureoftheDrawer,andinviewofAdvancedMathematicsintheDrawerprinciplehascarriedontheclassificationoftheapplicationofresearch.TheDrawerprincipleisobtainedbyresearchthebasicideasandmethodstosolvetheproblemofmaths,foritsdeficiencyinsolvesomecomplexproblemsalsoaddedinitspromotionof——Ramsey'sTheorem.
Firsthistoryandbasicdefinitionsoftheprincipleofthedrawerhascarriedonthesimpleintroduction,throughasimpleexampletounderstanditsdefinition,itsmainpurposeandresearchsignificance.Thenquestionsonhowtosolvespecificdrawerprinciplemethod,mainlybygrouping,accordingtotheresidueclassofparity,mould,graphicssegmentationmethodsfortheconstructionofthedrawer.Thenencountersthedrawerprincipleinhighermathematicssubjectclassificationsummary,studieditsgeometry,algebra,numbertheory,andanimportantapplicationindiscretedisciplines,canseethedrawerprinciple,scopeofapplicationisveryextensive.Thenbasedontheresearchofthehistoricalallusionsandpracticalproblems,andillustratesthedrawerprinciple,themainapproachtoexamineatmathcontest.Finally,thedrawerprinciplehascarriedonthefurtheradded.Insolvingmorecomplex,theexistenceofthesubjectmayappearshallnotapplytotheprincipleofdrawer,soitisnecessarytopromotethe,addedbyRamsey'stheorem,thispaperenableittobetterapplicationandproblemsolving.
Keywords:
drawerprinciple;Drawerstructure;Combinatorialmathematics.Mathcompetition;Ramsey'stheorem
I
目录
目录
摘要 I
ABSTRACT II
前言 1
第一章抽屉原理 2
1.1引入 2
1.2原理产生 2
1.3原理概述 2
1.4抽屉原理常见形式 3
1.4.1第一抽屉原理 3
1.4.2第二抽屉原理 3
1.5研究意义 3
第二章抽屉构造的常用技巧 3
2.1分组构造抽屉 4
2.2按奇偶性分类构造抽屉 5
2.3从模的剩余类构造抽屉 6
2.3.1模的剩余类 6
2.3.2实例 6
2.3.3小结 8
2.4图形分割构造抽屉 8
2.5总结 9
第三章抽屉原理的应用 10
3.1在几何中的运用 10
3.2在近世代数中的应用 10
3.3在高等代数中的应用 11
3.4在初等数论中的应用 11
3.5离散数学中的应用 12
第四章抽屉原理在数学竞赛中的应用 12
4.1抽屉原理解决实际问题 12
4.1.1“二桃杀三士” 12
4.1.2“电脑算命” 13
4.2在数学竞赛中的应用 13
4.2.1完美赛程 13
4.2.2竞赛题目 13
第五章抽屉原理的推广定理-Ramsey定理 14
结论 16
参考文献 17
致谢 18
I
四川理工学院毕业论文
前言
数学竞赛一直以来都是很多学校、学生、家长关注的焦点,数学竞赛的开展对于开发学生的大脑,提高学生的思维能力有很大的意义。
数学竞赛的题目往往不是要求学生大量的计算,而是需要学生抽象思维与逻辑思维等思维能力合作完成。
而抽屉原理恰好对于这些能力有较高要求,所以在数学竞赛中抽屉原理的题目往往会被涉及。
随着计算机技术的不断发展组合理论也得到的进一步丰富,抽屉原理作为组合数学的重要内容,也成为了数学竞赛的热点。
抽屉原理简单易懂,主要用于证明某些存在性或必然性的问题,不仅在数论、组合论以及集合论等领域中有着广泛应用,在高等数学的其它几门学科领域中也是解决问题的有效方法。
生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例,选取与生活贴近的如赛程安排、资源分配等问题进行阐述,更好地突出抽屉原理在实际生活中的用处.
本文针对数学竞赛中的抽屉原理的题目进行分析,提供抽屉原理这一类题目的基本解题思路,对抽屉的构造方法进行了介绍。
总结了如何运用抽屉原理解决几何、数论、离散数学、高等代数及近世代数中的问题,对抽屉原理在高等数学中的应用进行了梳理,将抽屉原理的解题思路拓展到高等数学的其他领域,有助于更好地理解抽屉原理,并举例阐述了抽屉原理在现实生活中的应用,以及根据抽屉原理的不足引出的Ramsey定理。
以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面,本文的主要创新点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结。
抽屉原理是处理存在性问题的有力工具,它在数学中的应用十分广泛。
通过本文,将会发现,其解题的关键是在制造适合的“抽屉”,而制造抽屉有很多的方法,这些方法灵活多变。
我们不能生搬硬套某一个固定的模式,需要灵活应用针对具体的题目具体的进行转化。
第一章抽屉原理
1.1引入
在平时生活中经常会遇到下面的问题:
(i)13个人中,其中必有两个人的属相是相同的;
(ii)2015年出生的366人,这366人中至少有两人是同一天生日。
其实这一类问题解决时,我们都会用到一个组合数学中最基本但又十分重要的原理——抽屉原理。
1.2原理产生
抽屉原理又称鸽巢原理,是组合数学中的一个基本原理,最早由德国数学家狄利克雷(Dirichlet)明确提出来的。
1842年,Dirichlet开始研究具有Gauss系数的型,首次运用了“盒子原理”,因此,也称Dirichlet原理。
1.3原理概述
鸽巢原理其简单表述为:
若有个笼子和只鸽子,所有的鸽子都被关在笼子里,那么,至少有一个笼子有至少2只鸽子。
或表述为:
若有个笼子和只鸽子,所有的鸽子都被关在笼子里,那么,至少有一个笼子有至少只鸽子[1]。
具体的可以从一个简单的例子入手:
把3只鸽子分别放在2个笼子中,则共有4中不同的放法(见表1):
表1鸽子放入方式
放法
笼子1
笼子2
1
0
3
2
1
2
3
2
1
4
3
0
1
可以看出,无论哪一种放法,都能肯定“必有一个笼子中至少放了2只鸽子”。
1.4抽屉原理常见形式
1.4.1第一抽屉原理
把多余个的物体放到个抽屉里,则至少有一个抽屉里的东西不少于两件。
证明(反证法):
如果每个抽屉至多只能放一个物体,那么物体的总数至多是n,而不是题设中的,故得证。
1.4.2第二抽屉原理
把个的物体放到个抽屉里,则至少有一个抽屉里放入个或个以上的物体,其中,为自然数。
1.5研究意义
抽屉原理是组合数学中最简单的,它反映了整数最基本的本质,在数论和组合数学等中运用广泛。
这种简单的原理,对于学生的思维能力有显著提高,它解决的问题都是日常中有趣的问题,能提高题目的趣味性和技巧性。
而数学竞赛正是为了提高学生的思维能力,题目也不会是大篇幅的书写,往往有很高的技巧性,所以近年来,抽屉原理在数学竞赛中的题目也经常出现。
对抽屉原理进行研究,有助于理解竞赛中的题目,也能针对原理更多的命出更有意义的题目。
对抽屉原理解题的研究,能为学生提供一些解题的思路,有助于增加学生的知识储备。
第二章抽屉构造的常用技巧
利用抽屉原理解决的题目一般来说:
给定的元素具有任意性,如3个苹果放入2个抽屉,可以任意放几个抽屉,可以有的抽屉多放,有的一个也不放,而要证明的是存在性问题。
常常有“至少有···”,“一定有···”,“不少于···”,“存在···”,等词语,这些结论只要求存在不一定确定。
而在解题过程中首先要注意明确哪些是元素,哪些是抽屉,元素放入抽屉有什么要求。
如何构造抽屉是用抽屉原理解题的关键。
有的题目只需用一次抽屉原理就能解决,有的则需要反复多次,有的问题明显能用抽屉原理解决,但对于比较复杂的问题便需要经过转化才能利用抽屉原理解决。
下面介绍几种构造抽屉的常用方法:
2.1分组构造抽屉
利用这种构造法,确定分组的“对象”很关键。
确定了“对象”之后,其个数相对于“苹果”的个数而言,往往会显得太多。
只有把这些“对象”分成适当数量的组(抽屉)后,才能应用抽屉原理。
例1:
从1,2,3,···,10这10个自然数中,任取6个数,则必能找到两个数,其中一个数是另一个数的倍数。
分析:
任取6个数,需设计5个抽屉,把这10个数放在5个抽屉里,且满足每个抽屉中的数具有倍数关系,所以分类为:
,,,,
把这5组看做5个抽屉,任取6个数,则必有两个数出自同一抽屉里,这样大数是小数的倍数[2]。
拓展:
若题目变为从1,2,3,···,12这12个自然数中,任取7个数,则必能找到两个数,其中一个数是另一个数的倍数。
设计抽屉:
,,,,,
把这6组看做6个抽屉,任取7个数,则必能找到两个数,其中一个数是另一个数的倍数。
注释:
上述问题是如何划分此6个抽屉的呢?
注意到一个自然数,他表示为奇数与的乘积的形式。
若允许,则可用上述形式表达1,2,3,···,12这12个自然数。
并且把式中“奇数”部分相同的的作为一组,构成一个抽屉:
显然有:
所以这6组数集便是上述6个抽屉的由来。
例2:
在前25个自然数中任取7个数,求证其中存在两个数,他们相互的比值在内。
证明:
题中取的是7个数,所以需要把这25个自然数划分成6个集合,本题涉及到两位数比值的上下界,因此,在一个抽屉内的集合中的元素的数值之间的差不能过大。
于是便可用递推办法来构造抽屉。
题设要求在之间,则“1”这个数,只能单独占一个抽屉;能与“2”合在一个抽屉内的数有“3”;与“4”合在一个抽屉内的数有“5”,“6”,···;如此,得到6个抽屉:
显然,若有两个数落在上述6个抽屉中的某一个之内,则这两个数的比值在内,而由抽屉原理得;对于这25个自然数中任取7个数,一定存在两个数,同在这6个抽屉的某一个抽屉内,于是命题得证[3]。
2.2按奇偶性分类构造抽屉
例3:
任意给定平面中五个格点(即坐标皆为整数的点),求证:
其中至少有两个点的连线的中点仍是一格点。
设这5个给定的格点为,,
取个点的横坐标,,···,,由抽屉原理知,其中必有3个具有相同的奇偶性,不妨设他们为,,,
再取其相应的纵坐标,,,
同理,其中至少有2个点具有相同的奇偶性,不妨设为,,
于是对于两点,来说与,与有相同的奇偶性。
即:
,
为整数。
所以为格点,此格点为线段的中点[4]。
例4空间中至少应该给出几个格点,才能使他们之中必有两点,使连接这两点的直线段内部含有格点。
分析:
设两个格点的坐标为,,
则连线的中点坐标为,
显然,为了保证中点为格点,这三个坐标均为整数,
当且仅当与,与,与奇偶性相同,
因此,可按奇偶性将所有格点的坐标分类,有:
(奇,奇,奇)(奇,奇,偶)(奇,偶,奇)(奇,偶,偶)
(偶,奇,奇)(偶,奇,偶)(偶,偶,奇)(偶,偶,偶)
这8种情况,把这8种情况看做抽屉,
由抽屉原则,至少应给出9个格点,才能使题设结论成立[4]。
小结:
抽屉原理解题的过程中,既可以从“苹果”入手,构造“抽屉”,也有可能从“抽屉”入手,得到“苹果”的个数,在数学竞赛中对于抽屉原理正逆运用十分广泛,特别是从“抽屉”“苹果”更是命题人的爱好。
2.3从模的剩余类构造抽屉
2.3.1模的剩余类
若是一个给定的正整数,则全部整数可分为个集合,记作......,,其中(r=0,1,...,)是由一切形如qm+r(q=0,,,......)的整数所组成的。
这些集合具有下列性质:
(i)每一个整数必包含在而且仅在上述的一个集合里面;
(ii)两个整数同在一个集合的充分与必要条件是这两个整数对模n同余。
上述中的叫做模n的剩余类。
2.3.2实例
例5任取4个自然数,其中必有两个数的差是3的倍数。
分析:
任意一个自然数被3除的余数只能是0,1,2三种,根据所得余数,可以把所有自然数分为三类:
{余数为0的自然数},{余数为1的自然数},{余数为2的自然数}
把他们看做3个抽屉,余数相同的自然数在同一个抽屉里,任取四个数必有两个数它们在同一个抽屉中,这两个数除以3所得到的余数是相同的,用大数减去小数,它们的差是3的倍数。
小结:
对于任给个自然数,其中必有两个数的差是的倍数。
对于这类题的基本方法是:
(i)任意自然数被除,余数有种:
0,1,......,;
(ii)根据余数,构造出个抽屉;
(iii)任取个数则必有两个数出自同一个抽屉;
(iv)用大数减去小数,它们之差就是的倍数[5]。
拓展:
任意给定7个不同的自然数,证明其中必有两个数的和或差是10的倍数。
证明:
将自然数按除以10所得余数分类,共10类:
0,......,9。
任意给定的7个数,若有两数在同一抽屉中,则大数减去小数是10的倍数,结论成立。
若给定的7个数,每两个数不在同一抽屉中,此时需要重新构造抽屉,将自然数按被10除的余数0,1,2,......,9分成6类。
{0},{1,9},{2,8},{3,7},{4,6},{5}
每一类做为一个抽屉,这样构造了6个抽屉,而在这7个自然数中,必有两个在同一个抽屉之中,则它们之和为10的倍数。
由此,可以得出更一般的结论:
任取+2个不同的自然数,则必有两个数的和或差是n的倍数。
证明:
设所给的自然数为(m=1,2,......,+2),有
则+2个自然数的余数,有+1种,可以看做+1个抽屉,这样,必定有在两个数,属于同一个抽屉,即:
。
(i)当时,-是n的倍数;
(ii)当时,+是n的倍数。
例6求证:
存在形如的一个整数,它是2014的倍数。
证明:
先考虑2015个数[7]。
2,22,...,
依次记为。
这2015个数被2014除,余数可能是0,1,2,...,2013折2014个数中的一个,
现在构造抽屉,按剩余类,便得到下列2014个抽屉:
第1个余数为0的;
第2个余数为1的;
第3个余数为2的;
第2014个余数为2013的。
现由抽屉原理可以知道,必有一个抽屉放入了两个数,记作,。
则这两个数被2014除得的余数相同,即是2014的倍数。
于是,是2014的倍数,
即是1007的倍数,显然1007与互质,
因此,是1007的倍数,即是2014的倍数,其中。
2.3.3小结
在利用模的剩余类来构造抽屉时,通常在数学竞赛中是用于解决整除问题。
根据除数来对若干数进行分类,注意合理的应用剩余类的性质,注意是两数之和还是两数之差。
2.4图形分割构造抽屉
在数学竞赛中,往往涉及到一个几何图形内有若干个点的情况。
常常是把图形分割成适当的部分,用分割所得的小图形作抽屉。
例7在正方形内任取5个点,可以找到2个点,使得它们之间的距离不大于正方形对角线长的一半[8]。
题目要得到的是不大于正方形对角线长的一半,由此可以根据对角线的对正方形进行分割(如图1)
图2-1分割的正方形
设四边形ABCD为正方形,取各边中点,连接,相交于店,则将正方形分成同样大小的四个小正方形,可以看做四个抽屉。
由抽屉原理,至少有一个小正方形至少包含其中的两个点,而这两个点的距离显然小于这个小正方形的对角线,即正方形对角线的一半,题目得证。
例8在边长为1的等边三角形内,任取5个点,证明:
至少有两个点,它们的距离小于。
题目中要求小于,注意到正三角形的边长为1,可以取各边中点,这样可以得到题设所需的,现在根据正三角形中的这6个点来分割图形(图2)。
(1)
(2)
(3)(4)
图2-2正三角形4种分割方法
对于这4种分割方式,根据抽屉原则,都可以确定至少有两个点落在同一部分内,两点间的距离不一定小于,前3种分割方式均不能保证。
而第4种分割方式中,得到的4个全等的小正三角形。
这4个小正三角形的边长为。
作为4个抽屉由抽屉原理可知,在正三角形中任取5个点,则一定有一个小正三角形里含有两个或两个以上的点,它们之间的距离不会超过,故命题得证。
由此题可以看出,将任意5个点放入边
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 抽屉 原理