数论的方法和技巧 02整点问题.doc

整点问题整点是指平面直角坐标系中纵、横坐标都是整数的点，又称为格点整点问题是数论与解析几何相结合的产物，不仅有趣，而且富有技巧性对于培养学生分析问题、解决问题的能力和训练思维的灵活性等很有好处，是考核数学竞赛参赛者的良好题材. 1整点多边形问题 如果一个多边形的所有顶点都是整点，则称这个多边形为整点多边形平面直角坐标系中是否存在整点正n边形？对于n=4，我们知道存在整点正方形，对于n=3，n5呢？ 例1证明：不存在整点正三角形 证 反证法，设平面上3个整点A，B，C组成一个正三角形由于向上、下或左、右平移整数个单位，整点仍然变为整点，因此不妨设A为原点，|AB| = r , B，C的坐标分别为（a，b），（x，y），其中a，b，x， yR如图8-5于是因为a，b均为整数，且至少有一个不为零，所以x，y不可能均为整数，矛盾.因此不存在整点正三角形 例2证明：不存在整点正五边形证 设存在一个整点正五边形ABCDE，边长为a，如图8-6，易知边长a与对角线d的比满足由两点间的距离公式知，任意两个整点的距离的平方是整数，所以a2和d2均为整数，从而是有理数，但是上式右端是一个无理数，矛盾。因此，整点正五边形是不存在的下面我们给出本题的另一证法设存在整点正五边形，在所有的整点正五边形中选出边长最短的一个，记作ABCDE，连接所有的对角线-得五边形如图87易知五边形是正五边形又因为为平行四边形，A，B，E是整点，令A，B，A1，E的坐标为则所以同理所以A1也是整点，同理，均为整点这样就得到了一个比ABCDE边长更短的整点正五边形矛盾我们用完全类似的方法可以证明整点正n边形不存在。整点多边形的内部及边界生的整点数目与面积之间有如下的关系。毕克(Pick定理) 一个整点多边形的内部有n个整点，边界上有m个整点，则此整点多边形的面积下面我们仅对一个两条边分别平行于坐标轴的直角三角形来验证毕克定理. 如图8-8所示，将整点直角三角形ABC扩充成矩形ABCD.设AB和BC边上分别含有a个和b个整点（不包括端点），则AB=a+l，BC=b+l,于是 设边AC上有c个整点（不包括端点）由于矩形ABCD内的整点数目为ab，所以ABC内的整点数ABC边界上的整点数因此 由毕克定理马上可以知道，任何一个整点三角形的面积不小于1/2 例3 整点三角形ABC的边上除顶点外没有其它的整点，而且它的内部只有一令整点P证明：P是ABC的重心证 由毕克定理知，由此可知P是3条中线的交点，即重心如图8-9，事实上，由可推知于是所以D是BC边上的中点，即AD是BC边上的中线，同理P点在中线BE和CF上 例4证明：整点凸五边形的面积不小于.证 整点可按它坐标的两个分量的奇偶性分成（偶，偶），（奇，奇），（偶，奇），（奇；偶）四类，于是5个整点中一定有两个点属于同一类型（抽屉原则），它们的中点M也是整点，由于是凸五边形，因此M在此五边形的内部或边界上(1) 若M在凸五边形的内部，根据毕克定理(2) 若M在边界上，不妨设M在边P1P2上，连接P3S,如图8-10，则整点凸五边形MP2P3P4P5的内部或边界上至少有一个整点（不包括顶点）于是根据毕克定理，2平面区域内的整点数例5求位于直线和横坐标轴形成的三角形内部和边界上的整点数解如图8-11，函数当x取1，2,，10时（注意，当时，)，得到y依次为于是，位于已知三角形（包括边界）中整点个数等于纵坐标的整数部分之和加上位于横坐标轴上的10个点的个数，即所以，三角形的内部与边界上共有37个整点，例6 m是正整数时，在曲线和直线所围区域内（包括边界）所含有的整点有多少个？解 抛物线和直线交点的横坐标为方程的实根，即如图8-12所示，对于满足的整数与直线的交点Ai是整点与抛物线的交点是整点于是上的整点个数为所以区域内（包括边界）的整点总数为下面介绍一个圆内整点问题例7设a为正实数，在圆内的整点数记为证明：证: 以圆内每个格点为左下方的顶点作边与坐标轴平行的单位正方形，因单位正方形的对角线长为所以这些正方形内任一点到原点(0，0)的距离不大于即所作的正方形均在圆内，从而这些单位正方形的面积和（等于圆内的整点数）不超过圆的面积从而右边不等式得证 对于圆内的任一点P，必有一个整点以，以A为左下方顶点、边与坐标轴平行的单位正方形含P点此正方形内的任一点与原点(0，0)的距离因此正方形在圆内从而以圆内的整点为左下方顶点所作的在圆内的单位正方形全体覆盖了圆及其内部，因此左边不等式得证3其它例8 在坐标平面上作一个凸集，使得它含有无限多个整点，但它与任何一条直线的交要么只含有限多个整点，要么不含整点（注：平面上的一个点集称为凸集，若对此点集中的任意两点，连接这两点的线段仍在该点集中例如；半平面、圆的内部、三角形区域、带形区域等均为凸集） 解：在直角坐标平面上作一个带形区域则此带形区域A为凸集，下面验证它满足题设条件，因为当x为整数时，整点因此凸集A含有无限多个整点对于形如的直线，它与A的交至多只含有一个整点这是因为此直线上至多只有一个整点的缘故，否则，若整点均在上，则所以这与均为整数，且矛盾，对于不是形如的直线，它与A的交是一线段，故至多只有有限多个整点 说明本例是一个“存在性”问题在处理这类问题时，往往需要构造，如何构造，是一个难点，多做练习t，积累经验，构造方面的能力就会有所提高下面的例子，也需要“构造性证明” 例9证明：在直角坐标平面上存在同心圆的集合，使得 (1)每个整点都在此集合的某一个圆周上； (2)此集合的每个圆周上，有且只有一个整点证: 取点设整点和到点P的距离相等，则即由于是无理数，所以上式仅当两边同时为零时成立，故式代入式并化简得由于因此b=d从而点(a,b)与(c,d)重合，故任意两个整点到的距离都不相等，现将所有整点到P点的距离从小到大排成一列，显然，以P为圆心，为半径作的同心圆的集合即为所求 例10有101个长方形，边长都是不超过100的整数证明：这些长方形中必有3个，第一个可以放在第二个中，第二个可以放在第三个中，证: 我们把这个问题转化为整点问题来解决将每个长方形用直角坐标系中的整点来表示，横、纵坐标x，y分别表示长方形的长和宽由题意知， 于是我们把问题转化为：有101个整点，它们的坐标均满足证明其中必有3个整点满足,我们考虑如图8-13所示的“”型,第一个的3个端点是(1，1)，(100，1)，(100，100)，第二个的3个端点是(2，2)，(99，2)，(99，99)，最后一个退化为一点(50，50)，共有50个“”型现有101个整点，根据抽屉原则，必有一个“”型中含有3个已知点，这3个点即为所求.例11. 平面上有限个点构成一个集合，其中每个点的坐标为整数，可不可以把此集合中某些点染成红色，其余点染成白色，使得与纵、横坐标轴平行的任一条直线l上所含的红、白点的个数至多相差一个？ 解答案是肯定的，对已知点n的个数进行归纳 当n=l时结论显然成立， 假设当所有点数小于n时结论都成立，考虑n个点如果每条横线与竖线上都只有一个已知点，任意染色即可否则设一条横线上有已知点A、B、如果过A的纵线、过B的纵线、，上面都只有一个已知点，那么将直线AB上的已知点交错地染上红色或白色，其余的点按归纳假设染好色即可 如果过A的纵线上还有一个已知点C，考虑以A，B，C为顶点的矩形ABDC.如果D是已知点，将A，D染成红色，B，C染成白色，其余的点按归纳假设染色即可，如果D不是已知点，将A，B，C除去，D点加入已知点中，由归纳假设将包括D在内的点染上颜色，不妨设D为红色，除去D，将B，C染成红色,A染成白色即可，例12. 在平面上任画一条所有顶点都是格点的闭折线，并且各节的长相等能使这闭折线的节数为奇数吗？证明你的结论解 令符合题设条件的闭折线为则所有顶点的坐标符合并且 为一固定的正整数），其中 则由已知，有不妨设,中至少有一个为奇数（因为设是指数最小的，为奇数，用除所有的数后，其商仍满足、式），于是它们的平方和C只能为或当时，由，知所有数对,都必须是奇数，因此，根据、式，知，n必为偶数，当时，由，知所有数对与都必一奇一偶，而由，知中为奇数的有偶数个(设为2u)，余下的n-2u个为偶数（与之对应的必为奇数），再由，知这种奇数的也应有偶数个（设为2v =n-2u)，故n=2（u+v）=偶数 综上所述，不能作出满足题设条件而有奇数个节的闭折线练习题 1填空题(1)设C是半径为r的圆，圆心在点是正实数，则圆C上整点个数最多有 个.(2)正整数x，y满足则这样的整点(x,y) 有_个(3)三角形3条边长均为整数，且最大边长为11的三角形共有 个.(4)平面上有若干个整点，要使它们之中总存在两点，使其连线的中点也是整点，则 这样的整点个数至少有_个(5)对任意自然数n，连接原点O与点用f(n)表示线段OAn上除端点外的整点个数，则f(l)+f(2)+f(1990)=_答：(1)1; (2)20; (3)36; (4)5; (5)1326.2三角形ABC是整点三角形，3条边长分别为a，b，c，外接圆半径为R求证：abc2R提示：利用3已知x，y都是两位的正整数，且xy，x+yAC，则AB - AC ，p是ABC的周长证明设ABC的顶点的坐标分别为：A(0，0)、B(x，y)、C(u，v)，三顶点A、B、C的对边长分别为a，b，c，则周长a+b+c于是，只需证明：因又因x,y,u,vZ, 故故。而故结论正确。8设p3是质数，是直角坐标平面上的一个点集，证明：从M中可以取出p个不同的点，使其中任3点不共线，任4点不构成平行四边形的顶点 9设ABC是整点三角形，且在ABC的内部只有一个整点（但在边上允许有整点）证明：10 如图，在坐标平面上给定凸五边形ABCDE，它的顶点都是整点证明：在五边形A1B1C1D1E1的内部或周界上至少有一个整点证明若周界上含有整点，结论显然成立，若周界上不含有整点，本题中只需证明结论对于和的内部及周界上不含A，B，C,D，E以外的整点时，结论成立这是因为若内部或周界含有另一整点K，则格点五边形KBCDE的“内五边形”包含于中，这样继续下去，总能找到一个符合上述要求的格点五边形其“内五边形”包含于中. 从ABC、BCD、CDE、DEA和EAB中选出面积最小的一个，不妨设为ABC,于是，点A与直线BC的距离不大于点O到该直线的距离；点C与直线AB的距离不大于点E到该直线的距离；为使四边形ABCO为平行四边形，点O显然为整点，则O在ABlC的内部，而AC1O1和CE1 A1内部或周界的都不含除A、C外的整点，所以点O在五边形A的内部或周界上11. 已知直线l经过两个格点，求证：直线l必经过无穷多个格点证设直线经过两格点则这说明：格点都在直线l上，故l上有无穷多个格点实战练习题1. （1999年全国高中数学联赛）平面直角坐标系中，纵、横坐标都是整数的点叫做整点，那么，满足不等式 (| x |-1) 2 +(| y |-1) 2 2的整点( x , y )的个数是( ) ( A )16( B )17( C )18( D )25 答：(A)解 因(x,y)是整点，所以x，yZ故及且又由于故有 从而，不难得到(z，y)共有：(1，1)、（1，-1）、（-1，1）、（-1，-1）、(1，2)、（1，-2）、（-1，2）、（-1，-2）、(2，1)、（2，-1）、（-2，1）、（-2，-1）、(1，0)、（-1，0）、(0，1)、（0，-1），16个整点故选A.2.（2000全国高中联赛）求平面上整点到直线的距离的最小值，解 将直线化成一般式显然这条直线上不存在整点由于25和5的最大公约数是5，所以，25x-15y(x，y都是整数)一定为5的整数倍，而且可以是5的任何整数倍，因此|25x-15y+12 | (x，y为整数)的最小值为2，因此，平面上的整点到直线的距离的最小值为3（1996全国高中联赛）在直角坐标平面上，以(199，0)为圆心，以199为半径的圆同上整点的个数为 解 设A(x，y)为圆O上的一整点，如右图，圆O的方程为显然，x=0，y=0；x=199,y=199; x=199，y= -199; x= 398，y=0为方程的4组解但当y0，199时，y与199互素（因199为素数），此时，199，y，|199-x|是一组勾股数，故199可表示成两个正整数的平方和，即因199=449+3，可设则这与199为4d+3型素数矛盾因而，圆O上只有4个整点(0,0)、(199, 199)、(398,0)、(199,-199)4. (1997年爱朋思杯-上海市高中数学竞赛决赛题)求平面直角坐标系中格点凸五边形（即每个顶点的纵、横坐标都是整数的凸五边形）的周长的最小值解格点多边形的边长的值最小为1，其次为图中五边形A BCDE周长为2+3.若格点五边形周长小于2+3，则其中至少有三边长为1，这三边中有两边相邻，设为图中AB、AE若有一边为BF=1，则ABFE成单位正方形，第五点在直线AE、BF外不可能与这四点成凸五边形所以与B相邻的另一边为图中BC同理与E相邻的另一边为图中ED这时凸五边形周长为2+3 ,因此所求最小值即2+35. （1992年日本数学奥林匹克预选赛题） A，B分别是坐标平面上的格点的集合：A=（x，y）|x，y为正整数，1x20，1y20B=（x，y）|x，y为正整数，2x19，2y19A中的点分别染成红色或蓝色染成红色的点有219个，其中有180个包含于B中，又四个角上的点（1，1），（1，20），（20，1），（20，20）都染成蓝色将水平或垂直方向上相邻两点按下列要求用红、蓝、黑色的线段连接起来：两点均为红色时，用红线连接；两点均为蓝色时，用蓝线连结；两点为一红一蓝时，用黑线连结问：（长度为1的）黑线有237段时，（长度为1的）蓝线有多少段？解 集合A中有400个点，其中红点有219个，蓝点有181个，在B内有蓝点144个A的四周有76个点，其中红点39个，蓝点37个（包括四个角上的点）每个角上的点引出2条线段；每个边界上（除四个角）的点引出3条线段；每个B内的点引出4条线段因此，对于蓝点共引出线段24+333+4144=683段;其中黑线有237段，所以蓝线有683-237=446段;这些蓝线在上述计数时，被重复计算了一次，故实际上有蓝线4462=223段6. (1994年日本数学奥林匹克预选赛题)某城市是长宽各为10km的正方形城内有间隔各为1km的棋盘街，东西走向和南北走向各11条东西走向道路所在的直线记为y=m（m=-5，-4，4，5），南北走向道路所在的直线记为x=n（n=-5，-4，4，5）某公司在该市开设5个分店Ak（k=1，2，5），它们分布在棋盘街道路沿线，其坐标（xk，yk）分别是（-5，1.3），（2，4.5），（4.4，3），（4，-1），（-2.7，-2）分店各派出1名店员，沿棋盘街道路行走，到街道沿线的某地会合要使得店员们行走的路程总和S（x，y）最小，求该地的坐标解 易知，所求的坐标（x，y）中至少有一个为整数，且若（x，y）不是格点（x，y均为整数的点），例如，设m、n为整数，而x=n，mym+1在（x，y）不是分店时，5个店员中有a人自北向南而至，b人自南向北而至当会合点向来人较多的方向移动时，S（x，y）将变小直到这个会合点移至格点或某个分店为止可能存在这样的分店Ak，其坐标xkn，mykm+1由它出发，到（x，y）点的路程不论由南向北来还是由北向南来，都是相等的此时（x，y）向南或向北移动，该店店员所走的路程都是减少的，因而只需考虑其他的人当y是整数而x不是整数时，考虑会合点东西向的移动，可得同样的结论综上所述，所求的点必为格点或某分店所在地由于题中的坐标xk（k=1，5）与yk（k=1，5）的中位数分别是x=2，y=1.3而最接近（2，1.3）的是格点（不是某分店）（2，1）即在格点（2，1）处会合，S（x，y）最小7. (1994年中国数学奥林匹克第