剁树枝问题 数学与应用数学毕业论文(剁树枝问题,组合数学、初等数论方向) 17页

剁树枝问题摘要有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。剁树枝问题是许多实际问题的一个模型，有着广泛的应用。本课题的任务是提供一般的方法使剁的次数最少。采用例举、分析、归纳、证明的流程，给出了剁树枝问题最少次数的递推关系和具体表达式，并对其进行了证明。关键词初等数论；组合数学；递归；数学归纳法AbstractSupposethereisapositiveintegerunitslongbranches,tochopthemintoacertainlengthofshortbranches.Duringthecuttingprocessoverlapisallowed,thenhowmanytimesisneededatleast?Thisproblemisknownascuttingthetreeproblem.Thecuttingbranches-problemisamodelformanypracticalproblems,withawiderangeofapplications.Basedontheideaofdynamicprogramming,therecursionformulaoftheleastnumberofmovementsnecessaryforthisproblemispresented.Thedirectformulaoftheleastnumberofmovementsnecessaryforthisproblemisgivenandprovedbytriplemathematicalinductionandpurecombinatorics.Keywordsnumbertheory；combinatorialmathematics；recursive;mathematical-17-\n目录摘要……………………………………………………………………………2第一章．绪论……………………………………………………………41.1剁树枝问题的简介…………………………………………………41.2剁树枝问题的研究意义及主要方法……………………………4第二章．主要理论：递归关系……………………………………………5第三章．推导过程…………………………………………………………63.1剁成1分米长的短树枝的情况…………………………………63.2剁成2或3分米长的短树枝的情况…………………………9第四章．结论………………………………………………………………13致谢…………………………………………………………………………14参考文献……………………………………………………………………15附录：外文参考文献………………………………………………………16参考文献翻译………………………………………………………………18-17-\n第一章.绪论1.1剁树枝问题的简介有一根正整数单位长树枝，要剁成一定长的短树枝，在剁的过程中可以重叠，问如何剁次数最少？这样的问题被称为剁树枝问题。例如：长为4分米的树枝要剁成1分米长的短树枝，先剁成两个2分米长度的树枝，再重叠剁成四个1分米的长度的短树枝，这样剁的次数最少，为两次。又如，长为9分米的树枝要剁成2分米或3分米长的短树枝最少次数是两次。剁树枝问题是许多实际问题的一个模型，有着广泛的应用。本课题的任务是提供一般的方法使剁的次数最少。1.2剁树枝问题的研究意义及主要方法本课题是主要研究剁树枝这样一个数学模型的一般性解决方法，涉及数论和组合数学知识，为日常生产生活、以及数学中类似问题的解决提供模型和参考。本课题的研究主要将涉及初等数论、组合数学等方面的知识，尤其是组合数学中的递推关系，将在本课题的研究中起到重要的作用。力图通过研究任意正整数长度的树枝分别剁成1分米，2或3分米两种情况的最少次数的情况，由其归纳出普遍适用的函数关系式，并通过验证、证明，归纳出最终的结论。第二章主要理论：递归关系　在组合数学中，递归关系是求解计数问题的重要方法。一般地说，当时，若数列满足-17-\n(h(n))=F(h(n-1),h(n-2),…,h(n-k))（*）（这里F是k元函数）则称式（*）为这数列的递推关系（或递归关系）。而满足递推关系（*）的数列称为这递推关系的解。当这数列的初始值h(0),h(1),…,h()给定时，从式（*）可依次计算出,….从而就确定了这数列，也就是可以计算出这数列的每一项。有时还能得到这数列的通项公式。第三章.推导过程3.1剁成1分米长的短树枝的情况（为书写方便，所有单位dm均忽略不写）：设n为树枝长度（nZ*），f(n)为最少剁的次数。例举n[1,50]的情形。如：当n=1时，f(1)=0.当n=2时，剁一次，f(2)=1.n=3,f(3)=2.……n=16时，先在中间剁一次为2个8（记为8·2），重叠在中间成4个4（4·2·2），如此往复，依次可得：16=8·2=4·2·2=2·2·2·2=1·2·2·2·2，共剁4次,f(16)=4n=17,先剁成8+9，重叠后剁成(4+4)+(4+5)，重叠后剁成2·7+3，再次重叠剁成1·15+2，最后将2剁成两个1，共计5次。……n=50,50=25·2=(12+13)·2=(6·3+7)·2=(3·7+4)·2=(2·9+1·7)·2=1·50,由等号的个数可以看出f(50)=6.结果如下表所列：-17-\nn12345f(n)01223n678910f(n)33344n1112131415f(n)44444n1617181920f(n)45555n2122232425f(n)55555n2627282930f(n)55555n3132333435f(n)55666n3637383940f(n)66666n4142434445f(n)66666n4647484950-17-\nf(n)66666通过以上表格和在分析得到此表格的过程，我们可以得到如下发现：1.f(n)随着n的增大而增大或不变，即f(m)f(n),mn.2.f(n)在以下位置之后值发生改变：f(1)=0,f(2)=1,f(4)=2,f(8)=3,f(16)=4,f(32)=5.……不难发现这样的规律：f()=n，f(+t)=n+1(1t<).为了证明这个公式，下面，我将给出以下几个引理：引理1.1f(n)f(n+1)证明：由剁树枝的过程，此定理显然成立。引理1.2f(2n)=f(n)+1证明：由剁树枝的过程可发现，对于偶数长度的树枝，先将其对半剁，使2n长度为2个n长。接着将2个n重叠，以下剁法同长为n的树枝。故长2n的树枝比长n的树枝多剁一次，即f(2n)=f(n)+1.引理1.3f(2n-1)=f(2n)n2证明：对于大于1的奇数长度的树枝，如2n-1，第一步将其剁为长度相差最小的两段，即(n-1)+n，然后将这两段树枝重叠再剁。由f(n-1)f(n),故重叠后至少要剁f(n)次。故f(2n-1)=f(n)+1=f(2n).下面我们开始定理的证明：定理1.对于长度为m（mZ*）分米的树枝，将其剁为长度为1分米的短树枝，最少所需次数为f(m)。则f(m)满足下列公式：任意mZ*,存在n,tZ,使得m=+t,其中t[0,),tZ.nt=0;则f(m)=f(+t)=-17-\nn+11t<.证明：【一】先考虑t=0的情形：n=0时，f(1)=f()=0.结论成立。n>0时，由引理1.2，有f()=f(2·)=f()+1=f()+2=……=f()+n=n.得证。【二】再考虑t0，即1t<的情形：n1时，<+t<，故由引理1.1，有f()f(+t)f()（1）而由引理1.3:f(2n-1)=f(2n)n2，故f(+1)=f(+2)=f[2*(+1)]=f(+1)+1=f(+2)+1=f(+1)+2=……=f(+1)+n=f(2)+n=n+1.又f()=n,f(+1)=n+1,f()=n+1,由（1）式及引理1.1，有n+1=f(+1)f(+t)f()=n+1,故f(+t)=n+1,1t<.得证。3.1剁成2或3分米长的短树枝的情况设n为树枝长度（nZ*），g(n)为最少剁的次数。例举n[2,50]的情形。如：当n=2或3时，g(n)=0;当n=4时，剁一次，g(n)=1……-17-\nn=16时，先在中间剁一次为2个8（记为8·2），重叠在中间成4个4（4·2·2），再重叠剁一次即可，依次可得：16=8·2=4·2·2=2·2·2·2，共剁3次,g(16)=3n=17,先剁成8+9，重叠后剁成(4+4)+(4+5)，重叠后剁成2·7+3，共计3次，故g(17)=3。……n=50,50=25·2=(12+13)·2=(6·3+7)·2=(3·7+4)·2=3·14+2·4,由等号的个数可以看出g(50)=5.结果如下表所列：n23456g(n)00111n7891011g(n)22222n1213141516g(n)23333n1718192021g(n)33333n2223242526g(n)33344n2728293031-17-\ng(n)44444n3233343536g(n)44444n3738394041g(n)44444n4243444546g(n)44444n47484950g(n)4455和剁成1分米的情况类似，我们也不难得到如下发现：1.g(n)随着n的增大而增大或不变，即g(m)g(n),mn.2.g(n)在以下位置之后值发生改变：g(3)=0,g(6)=1，g(12)=2,g(24)=3,g(48)=4.……不难发现这样的规律：g(3·)=n，g(3·+t)=n+1(1t<3·).为了证明这个公式，同样也将给出以下几个引理：引理2.1g(n)g(n+1)证明：由剁树枝的过程，此定理显然成立。引理2.2g(2n)=g(n)+1证明：由剁树枝的过程可发现，对于偶数长度的树枝，先将其对半剁为最简方案，使2n长度为2个n长。接着将2个n重叠，以下剁法同长为n的树枝。故长2n的树枝比长n的树枝多剁一次，即g(2n)=g(n)+1.-17-\n引理2.3g(2n-1)=g(2n)n3证明：对于大于3的奇数长度的树枝，如2n-1，第一步将其剁为长度相差最小的两段，即(n-1)+n，然后将这两段树枝重叠再剁。由g(n-1)g(n),故重叠后至少要剁g(n)次。故g(2n-1)=g(n)+1=g(2n).下面我们开始定理的证明：定理2.对于长度为m（mZ*）分米的树枝，将其剁为长度为2或3分米的短树枝，最少所需次数为g(m)。则g(m)满足下列公式：任意m3,mZ,存在n,tZ,使得m=3·+t,其中t[0,3·),tZ.nt=0;则g(m)=g(3·+t)=且g(2)=0.n+11t<3·.证明：n=2时，g(2)=0，显然成立。下证n>2的情形。【一】先考虑t=0的情形：n=3时，g(3)=g(3·)=0.结论成立。n>3时，由引理2.2，有g(3·)=g(3·2·)=g(3·)+1=g(3·)+2=……=g(3·)+n=n.结论成立。【二】再考虑t0，即1t<3·的情形：n1时，3·<3·+t<3·，故由引理1.1，有g(3·)g(3·+t)g(3·)（2）而由引理2.3:g(2n-1)=g(2n)n3，故g(3·+1)=g(3·+2)=g[2·(3·+1)]=g(3·+1)+1=g(3·-17-\n+2)+1=g(3·+1)+2=……=g(3·+1)+n=g(4)+n=n+1.又g(3·)=n,g(3·+1)=n+1,g(3·)=n+1,由（2）式及引理2.1，有n+1=g(3·+1)g(3·+t)g(3·)=n+1得g(3·+t)=n+1,1t<3·.得证。第四章结论通过本次课题的研究，得到了对于剁树枝问题的一些基本结论和定理，也为以后此类问题的研究提供依据。在研究的过程中发现，这类问题是数论、组合数学在现实生活中较为具体的实例，且趣味性较强。但是虽然不是难题，此类问题的研究还是具有非常重要的意义的，特别是对于数学与应用数学师范类的本科生，未来的职业生涯将主要从事初等数学的教学和研究，这类与初等数学联系较为密切的问题，对于以后在中小学生的奥数及趣味数学、数学建模中的应用，有着尤为重要的作用和帮助。-17-\n致谢致谢:本论文是在XXX老师的悉心指导下完成的。X老师渊博的学识给与了我极大的帮助，使我在论文的编写过程中受益匪浅，不但提高了科研水平，而且还提高了科技论文的写作水平。通过论文的写作，使我对以前学的课本知识能够有效地运用到实践当中，使理论与实践得到很好的结合，对于此类实际问题的解决，也有了更强的兴趣和信心。在此论文完成之际，谨向X老师表示由衷的感谢。与此同时，向在我的本科生学习当中给与了极大帮助和支持的我的家人及XXXX大学XXXX学院的老师和领导表示感谢，谢谢你们的辛劳！最后祝所有关心过我的同学、朋友、导师、领导、家人身体健康、工作顺利、好人一生平安。XXX-17-\n参考文献1．越民义《组合优化导论》浙江科学技术出版社20012．孙淑玲、许胤龙《组合数学引论》中国科学技术大学出版社第二版20103．李文林《王元论哥德巴赫猜想》山东教育出版社19994．[加]R.K.盖伊《数论中未解决的问题》科学出版社第三版20075．李凡长编著《组合理论及其应用》清华大学出版社20056．[美]FredS.Roberts,BarryTesman《应用组合数学》机械工业出版社20077．Soederstroem.T.，《递推辨识的理论与实践》科学出版社19898．李乔《组合学讲义》高等教育出版社20089．蔡锁章主编《数学建模：原理与方法》海洋出版社200010．魏有德《递推法》四川教育出版社198911．陈永明《递推式》上海科学技术出版社198912．华罗庚《华罗庚文集数论卷》科学出版社201013．[美]JosephH.Silverman《数论概论》机械工业出版社200814．[英]Burn.R.P《数论入门》高等教育出版社199015．丁石孙主编《归纳·递推·无字证明·坐标·复数》北京大学出版社1995-17-\n附录：外文参考文献ProofbyinductionSincenumbertheoryislargelyconcernedwiththepositiveintegers,someofitstheoremsareofform,“such-and-suchistrueforallpositiveintegersn.”Propositionslikesthiscanoftenbeprovedbymathematicalinduction(orinductionforshort—wewillnotbeconcernedwithanyotherkind).Thismethodofproofisbasedonthefollowingpropertyofpositiveintegers:(1)Ifasetofintegerscontains1,andifitcontainsr+1wheneveritcontainsr,thenthesetcontainsallthepositiveintegers.Thispropertyissofundamentalthatitisusuallytakenasanonprovablepostulateaboutthepositiveintegers.ItisappliedwhenwewanttoshowthatapropositionP(n)aboutthepositiveintegernistrueforalln,n=1,2,….Examplesofsuchpropositionsare:“n(n+1)(n+2)isdivisibleby6.”-17-\nLetSdenotethesetofpositiveintegersforwhichP(n)istrue.Ifwecanshowthat1isinSandthatifrisinS,thenr+1isinS,then(1)saysthatallpositiveintegersareinS.Rephrasingthis,wegettheinductionprinciple:IfP(1)istrue,andifthetruthofP(r)impliesthetruthofP(r+1),thenP(n)istrueforalln,n=1,2,….Thereisnonecessityforaninductiontostartwith1;wecouldstartwith2,3,17,or-12.Forexample,ifP(3)istrueanifthetruthofP(r)impliesthetruthofP(r+1),thenP(n)istrueforn=3,4,….Anotherformoftheinductionprincipleissometimesused:IfP(1)istrue,andifthetruthofP(k)for1krimpliesthetruthofP(r+1),thenP(n)istrueforalln,n=1,2,….Thisisvalidbecauseofthecorrespondingpropertyofintegers:ifasetofintegerscontains1,andcontainsr+1wheneveritcontains1,2,…,r,thenitcontainsallpositiveintegers.-17-\n参考文献翻译数学归纳法数论的理论主要和正整数有关，其定理通常以以下形式出现：“所有正整数都满足这样的条件”。命题得到证明通常可以用数学归纳法（简称感应证明）。这种证明方法通常如下：（1）如果一个整数集包含1，且只要它包含r，就一定包含r+1，则这个集合包含所有的正整数。这是一个基本属性，它通常被当做对正整数集合的一个假设。当我们需要证明命题P（n）对于任意正整数n（n=1,2,…）都成立时，就可以运用这个定理。例如：:“n(n+1)(n+2)能被6整除.”设S表示使P（n）成立的正整数集。如果我们能够证明，1在S中，且如果r在S中，则r+1一定也在S中，那么根据定理（1），所有的正整数都在S中。这个定理可以如下陈述，即为数学归纳法：-17-\n如果P（1）是真的，且P（r）为真，就必有P（r+1）为真，那么P（n）为真，n=1,2，...。数学归纳法不一定要从1开始证明，我们可以也用2，3，17或-12开始。例如，如果P（3）是真的，且P（r）为真，就必有P（r+1）为真，那么P（n）为真，n=3,4，...。数学归纳法的另一种方式为：如果P（1）是真的，且如果P（k）为真，其中1kr，就必有P（r+1）为真，那么P（n）为真，n=1,2，...。这个定理为真，可以由这样的整数性质得到：如果一个整数集包含1，且如果它包含1,2，…,r，就必包含r+1，那么它包含所有的正整数。-17-