资源描述：
《E14一类离散最值问题的探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、E14•—类离散最值问题的探究参赛队员：蔡煜晟、赵海洲所在省份：浙江省所在国家：中华人民共和国指导老师：张传鹏、杨晓鸣论文标题：-•类离散最值问题的探究1H录摘要关键词1.背景与结果(3)2.预备知识(5)3.引理的证明(6)4.定理的证明(11)5.思考与展望(18)附录：参考文献(19)2一类离散最值问题的探究摘要木文探究了在给^mXni网格中任意画圆，圆周经过的格点数f(m)的最大值问题。对于方格数小于15X15,借助已有的知识和工具问题得到彻底解决；对于方格数大于16X16,我们引进了类似Farey数列，建立一•套计数方法，得到函数f(m)的下界。
2、在此基础上，给出相应圆的半径的上界和下界，并根据函数f(m)的下界和圆的半径范甬求出所有可能的圆，再分别计算这些圆所经过的格点数。从而得出在给定mXm网格中任意圆周经过的格点数的最人值。关键词格点、欧拉函数、Farey数列、互质。AbstractThispapermainlydiscusseshowtogetf(m),themaximumnumberofgridpointsacirclecanpassinagridnetofmXm.FormW15,wesolvetheproblemusingknowntoolsandknowledge.Form^l6,wo
3、makeuseofthesimilarcalculationmethodasFarcySequence,andgetthelowerboundoftherangeoff(m).Basedonthislowerbound,wecalculatetherangeoftheradiusofthecircle;next,weobtainal1thecircleequationforallthepossiblecircleaccordlngtothelowerboundoff(m)andrangeofradius.Final1y,themaximumnumbetof
4、gridpointacirclecanpassinthegirdnetofmXmisobtained.KeywordGridpoint&Gridnot,EulerFunction,FareySoqucnee,RelativelyPrimeIntegers1•背景与结果2010年浙江省湖州市中考有一道很有意思的题目，即第16题：请你在如图一所示的12X12的网格图形中任意画一个圆，则所画的圆最多能经过169个格点中的个格点.[1]3图一这道题当时给出的标准答案是12,它实际上是错误的，正确答案应该是16。我们注意到这一错误，并月•进行探究之后，对于沪12以外
5、的情况产生了兴趣。我们知道,哈代等数学家在他的论著[2](p257~258)中，得到了以原点为圆心的圆周经过的格点数，即得到下面的命题。命题方程x2y2n(n2prqs,p、q分别为形如4M1以及1(l)s4M1不同的素数)有整数解组数为4(n)((n)=(r1)(。))2事实上，华罗庚先生在他的《数论导引》[3](P131-140)中对以原点为圆心的圆周经过的格点数、中心在原点的椭圆内的格点数、以及三维球内和高维球内的格点数都作了论述。我们利用这些结果得到下而的推论：推论若圆(axbl)(ayb2)n(a.n为正整数，bl、b2为整数，圆的半径22为R=
6、n2mRWm)在mXm的网格上经过s个格点。若当R>m时，则sW(n)；若当a22m时，sW4(n)o2时，则sW2(n)；若当RW我们知道，要使在给定方格中得I员1周经过的格点数最多，利用閲的性质，其関心一定为有理点。所以，我们总假设圆的圆心是有理点。利用推论，以及圆的半径的平方数的质因数分解，解决了网格数小T15X15的网格中任意圆周经过的最大格点数。但当网格数大于16X16，该方法失效，失效的原因是此时解决该问题时使用的抽屉原理不能使用，因为抽屉个数多于格点个数。所以当网格数大于16X16就要另辟其径。解决问题的关键Z—是整数的计数方法，受Farey
7、数列的启发，我们引进边长和的概念(以两个格点为对角线所做矩形的两邻边Z和)，这个和记为EF,对角线的斜率的绝对值记为
8、k
9、=al(al、bl为互索的正整数)，这样建立了整数EF与整数al+bl的关系。这bl样，利用欧拉函数建立了-•套计数方法。借助这些知识和概念，我们分布解决问题(得到一4系列引理):定义在网格mXm屮，一•个圆能够经过的格点数的函数f(山)。先给出一个f(m)下界的估计s：f(m)2s利用反证法证明f(m)Ws(1)假设f(m)>s(即f(m)2s+l)(2)求出能够满足f(m)Ms+l的圆的半径R的范围并通过求得的范围给出所冇可能的圆以
10、逐一验证，从而说明格点数不小于s+1的圆无论怎样移动网格所覆盖的格
