【提优教程】江苏省2012高中数学竞赛-第40讲-格点教案.doc

第40讲 格点本节主要内容有格点的概念，及格点在解题中的应用格点，又叫整点，指的是在直角坐标系中，每个坐标都是整数的点或者直接在平面上取两组互相垂直的平行线(在空间中就取三组互相垂直的平行平面)，相邻的两条平行线的距离相等，这两组平行线的交点就是格点当一个多边形的所有顶点都是两组互相垂直的平行线，相邻的两条平 行线的距离相等，这两组平行线的交点就是格点关于格点多边形，有下列定理：定理1 (皮克定理)设格点多边形内部有N个格点，边界上有L个格点，则其面积S=N+L1(证明略)定理2 边与两轴平行的正方形(顶点不一定是格点)，如果其面积大于1，则其内部至少有一个格点 证明 如图，设点A、B的横坐标分别为a，b，则rba1若a为整数，则a1b，而a1为整数，此时，直线xa1穿过正方形ABCD内部；若a不是整数，a是不超过a的最大整数，aaa，有0a1，此时aaaa1aa1a1abab即直线xa1穿过正方形内部总之，正方形内部有一条竖直格线穿过同理，正方形内部有一条水平格线穿过即其正方形内部有一个格点A类例题例1 内部不含格点的圆，其面积 内部恰有一个格点的圆，其半径不大于1分析 本题是定理2的一个直接应用证明 如果圆的面积，则其半径其内接正方形边长1由定理2可知其内部必有格点故证 证明 设O有内部恰有一个格点，且其的半径1圆心O必在某个格点正方形ABCD内或在其边上从而A、B、C、D至少有三点在O外或O上于是相对的两个顶点A、C或B、D同在O外或O上，例如B、D在O外(或O上)于是BO1，DO1即O应在以B、D为圆心，1为半径的圆外(或边界上)，又在正方形ABCD内部，这是不可能的例2 找出内部恰有0个、1个、2个、3个、4个格点的面积最大的圆 能否找到内部恰有5个格点的面积最大圆？解 (如图)内部恰有0个格点的面积最大圆的半径；内部恰有1个格点的面积最大圆的半径1；内部恰有2个格点的面积最大圆的半径；内部恰有3个格点的面积最大圆的半径；内部恰有4个格点的面积最大圆的半径解 如左图画的是内部有5个格点且过4个格点的圆，其半径但这圆不是内部有5个格点的面积最大圆 如右圆，取内部恰有四个格点的面积最大圆(虚线画的圆)，其圆心为O，点P1、P2、P3、P8等8个格点在此圆上，其半径可以作一个圆使原来四个在圆内的格点仍在此圆内，且使P1在圆内而原来在圆上的其他格点都在圆外为此取P1P8、P2P3的垂直平分线l1、l2，则在这两条直线围出的右上平面内的点，到P1的距离比到P8的距离小，到P2的距离比到P3的距离小，再作P2P8的垂直平分线l3，则l3上的点到P2、P8距离相等，现在l3上靠近点O取一点Q，以Q为圆心，QP2为半径画一圆，显然，此圆内恰有5个格点只要点Q充分接近O，则Q的半径充分接近，但圆内恒有5个格点即没有圆内恰有5个格点而面积最大的圆情景再现1内部不含格点的正方形，其面积22找出内部恰有1个，2个格点的面积最大的正方形B类例题例3 求证：对任何n(nN)，可以作一个圆，恰盖住n个格点(格点在圆内部)分析 只要能证明，平面上存在一点，到所有格点的距离两两不等为此，可以利用“无理数不等于有理数”来解证明 取一点，其两个坐标都是无理数，例如取点W(，)，先证明，以W为圆心，任意长为半径作的圆，至多通过一个格点设某个以W为圆心的圆通过两个格点(m，n)，(p，q)(m，n，p，qZ)，则(m)2+(n)2(p)2+(q)2展开整理得，m2+n2p2q22(pm)+2(qn)左边是有理数，右边当且仅当pm，qn时为有理数故证于是可知以W为圆心的圆至多通过一个格点现考虑，平面上所有的点与W的距离，这些距离没有两个相等把所有的格点与点W的距离按从小到大排队0r0r1r2r3rn取线段r，满足rnrrn+1，以W为圆心，r为半径作圆，则此圆内恰有n个格点说明 本题即是辛泽尔定理，利用本题的结果可以解1987年的全国高中联赛题二试第2题例4 若a与b是互质的正整数，证明(a1)(b1)分析 研究数ka(k，aN*)的几何意义：取函数ykx，这是一条直线，在直线上取一点(a，ka)，在连结点(a，0)与点(a，ka)的线段上(不含点(a，0)而含点(a，ka)时)，恰有ka个格点证明 取直线yx(右图中以a5，b9为例)对于k1，2，b1，由(a，b)1，知b ak所以直线yx与xk(k1，2，b1)的交点都不是格点而表示线段xk(y(0，ka)上的格点的个数，所以，表示以O(0，0)，A(b，0)，B(b，a)为顶点的三角形内部的格点数由于线段yx(x(0，b)上没有格点，由对称性知，OAB内部的格点数等于矩形OABC(其中点C坐标为(0，a)内部格点数的一半而矩形OABC内部的格点数(a1)(b1)(共a1行，b1列)从而(a1)(b1)说明 本题所证明的恒等式称为厄尔米特恒等式本题是把高斯函数中的内容与格点联系起来的一个定理 例5 若每边长均为整数，三边不等且最大边长为n的三角形共有600个，求n分析 先列出相关条件，把相关条件转化为平面上满足这些条件的格点数 解 设三边长为x，y，n，且xyn，则有x+yn本题可以理解为满足yn，yx，x+yn的区域中恰有600个整点故在坐标系内作直线yx，xyn，yn，若A(n，0)，B(n，n)，C(0，n)，AC、OB的交于点P由这三条直线围成的三角形PBC即为所求区域 正方形内共有(n1)2个格点，线段AC、OB内各有n1个格点，当n为奇数时，P不是格点，当n为偶数时，P是格点由对称性，PAB、PBC、PCO、POA内的格点数相等故有 (n1)22(n1)k6004(n为偶数时k1，n为奇数时，k0)即 n24n32400k当n为奇数时，(n2)22401492，所求正整数解为n51当n为偶数时，(n2)22400，无整数解所以 n51情景再现3 如图，在一个棋盘形的街区图中，纵线与横线都表示街道，有人沿此街道从(0，0)直到(n，m)，问使路程最短的走法有多少种? 如图，仍在此街道图中，如果在点(p，q)与 (p，q+1)(0pn，0qm1)间的街道(图中用粗线标出)戒严，禁止通行，则从(0，0)到(n，m)的最短走法有多少种？4试设计一种染色方法，把所有的平面整点染色，每一整点染成红色、白色或黑色中的一种颜色，使： 每一种颜色出现在无穷多条与横轴平行的格线上； 对任意白点A，红点B，黑点C，必可找到一个红点D，使ABCD为平行四边形(1986年全国高中联赛)5中国象棋的“马”可以从一个12矩形的一个顶点跳到相对的顶点上(不妨称之为12马)问一个中国象棋的马能否从其起点A出发，不重复不遗漏地跳遍半个棋盘？6在一个nn的方格纸上任意选定同一行的相邻两个方格A与B，在左面的A格中放了一枚棋子，它可以向上、右、和斜左下的格子走，试证明：对任何正整数n(n1)，这枚棋子不能走遍所有的格子并最后走到B，而且每个格子都只走过一次C类例题例6 起点为(0，0)，终点为(2n，0)(nN*)的折线由(p，q)(p+1，q1)类型的线段构成 集合A表示该折线除起点与终点外与y=0还有一个公共点，但位于y=0上方的折线集合；集合B表示该折线除起点与终点外与y=0没有公共点，且位于y=0上方的折线集合求证：card(A)=card(B)证明 对于每个A中的任意一条折线l，设它与x轴 (除起点与终点外)的交点为(2k，0)此点把l分成两部分：前段l1与后段l2，现把l2中从(2k，0)到(2k1，1)的一节截出放到从(0，0)到(1，1)，并把前段l1按(0，0)到(1，1)的向量平移，这样就得到了一条B中的折线反之，对于每条B中的折线l，它至少有两次与直线y1相交第一次交于(1，1)，设第二次交于点(2k1，1)，这两点把l分成三段一段是从(0，0)到(1，1)，一段是从(1，1)到(2k1，1)，一段是从(2k1，1)到(2n，0)，现把第一段移至(2k，0)到(2k1，1)，第二段按(1，1)至(0，0)的向量平移，则得到了一条A中的折线这说明A中的折线与B中的折线有一个一一对应关系 card(A)card(B)例7 在平面直角坐标系中，任取6个格点Pi(xi，yi)(i=1，2，3，4，5，6)满足： |xi|2，|yi|2(i=1，2，3，4，5，6)； 任何三点不在一条直线上试证明：在以Pi(i=1，2，3，4，5，6)为顶点的所有三角形中，必有一个三角形的面积不大于2(1992年全国高中数学联赛试题)分析 满足要求的格点共25个，设法把它们分组，使同组三个格点连成三角形面积不超过2，再研究可能取点的情况证明 如图，满足条件的格点只能是图中A、B、Y这25个格点中的6个把这25个格点分成三个矩形：矩形AEFJ、KOWU、MNYX若所取的6个点中有三个点在上述三个矩形中的某一个中，则此三点即满足要求若三个矩形中均无所取6点中的3点，则必是某个矩形中有所取的2个点 若E、F、D、G、O、R、W中有所取的点，则此点与矩形MNYX中的两点满足要求； 若上述7点均未取，则A、B、C、H、I、J中必有两点，此时若L、K中有所取的点，则亦有三点满足要求； 若L、K亦未取，则必在P、Q、V、U中取了2点，矩形ACHJ中取了2点：此时取P、Q两点，或Q、V两点，或V、U两点，或U、P两点，或Q、U两点，则无论ACHJ中取任一点，与之组成三角形面积均满足要求若取P、V两点，则矩形ACHJ中必有一点异于C，取此点与P、V满足要求综上可知，必有满足要求的3点存在例8 平面上有限点集的集合S其中每个点的坐标都是整数，是否可以把这个集合中的某些点染红色，其余点染白色，使得与纵横坐标轴平行的每一条直线L上所包含的红、白点的个数至多相差1个？分析 本题不外以下三种结果：1对于一切nN*，均无法染成，此时要给出证明；2对于一切nN*，均可以染成，此时要给出一个染色的方法；3对于某些nN*，可以找到染色方法；而对于另一些nN*，则无法染成；此时要给出分类的标准，并对无法染成的给出证明，对可以染成的给出染色方法为了证明本题，可以先看最简单的情况，n1，2，3等，于是可以考虑用数学归纳法证明本题证明 用数学归纳法证明：若n=1，则可以将此点任意染成红色或白色若n=2，则可把这两个点一个染红一个染白即n=1，2时命题成立设当nk(kN*)时都有满足上述要求的染法，当n=k+1时，若某一条纵线(或横线)上有奇数个点，则将此直线上的点去掉1个，此时，共余下k个点，可以有满足上述要求的染法由于去掉一个点后，这条直线上有偶数个点，故这条线上的其余点染成红白各半，而该点所在横线上的红白点或相等或相差1个，如果相等，则可把这点任意染色，如果红白相差1个，则染成较少个数的颜色，于是有满足要求的染法如果任一条横线与纵线上都有偶数个点，不妨在某条横线l1与纵线m1相交处的点被去掉，对于余下的这k个点，由归纳假设知必有合要求的染色方法，此时去掉点所在横线l1与纵线m1上都有奇数个点，必为某色多1，现只要说明，这两条线上是同色点多1即可设l1上红点多1，先不看l1，统计其余横线上的红白点数，由于其余横线上都是偶数个点，因此，都染成红白各半，所以这k个点染色时，红点总数应多1个再不看m1，统计其余纵线上的红白点数，由于其余纵线上也全为偶数个点，故也是红白各半，但由于红点总数多1个，故m1上点必染成红点多1个于是可以把去掉的点补回，并染白，就得到了满足要求的染色法根据数学归纳原理知，对于任何nN*，均有符合要求的染色法情景再现7设三角形的三边长为正整数l，m，n，且lmn当n=9时，有多少个这样的三角形？对于一般的n的值，有多少个这样的三角形？8给定一个正45边形，在它的每个顶点上标上0，1，2，9这十个数字中的一个另一方面，由这10个数字中的不同的数字组成了任意的数对，问能否找到这样的一种标数法，使得对于每一个数对都有一条边与之对应，且这条边两端标的数字就是这个数对习题401一个平行四边形的三个顶点是格点，则其第四个顶点也是格点2若有一个无限大的棋盘及一匹1n的“超级马”(即一步从某个1n格点长方形的一个顶点跳到与之相对的顶点，中国象棋的“马”是12马)，问n应该满足什么条件，才能使它从某个格点跳到任一格点3在平面直角坐标系中，横、纵坐标都是有理数的点称为有理点，若为无理数，则过(，0)的所有直线中，有且只有1条直线至少通过两个有理点4各边的长都为整数的三角形，其三边的和为50，这样的三角形有多少种？5对任意正整数n，连结原点O与点An(n，n+3)，用f(n)表示线段OAn上的整点个数(不计端点)，试求f(1)+f(2)+f(1990)(1990年全国高中数学联赛，原题是填空题)6给定一个nn的格点阵，以此阵中的格点为顶点的格点正方形有多少个？7若每边长均为整数，三边不等且最大边长为n的三角形共有600个，求n8设n0，给定平面区域P(x，y)|x0，y0，且xyn求证：P内格点的个数S=229设有一条平面闭折线A1A2AnA1，它的所有顶点都是格点(即纵、横坐标都是整数的点)，且|A1A2|=|A2A3|=|An-1An|=|AnA1|证明：n为偶数(1986年第1届国家集训队训练题)10某次共有18名学生参加选举，每人投1票，投给2名侯选人中的1人，投票完毕后，由1名学生逐张开票，1名学生记录开票的结果若最后侯选人甲得到11张票问在开票过程中，甲得票数始终不少于乙的开票方法有多少种？11把边长为1的正三角形ABC的各边分为n等分，过各分点作平行于其他两边的平行线，将这个三角形分成小正三角形，各小三角形的顶点称为结点，在每个结点上放置一个实数，已知：A、B、C上放置的数分别为a、b、c(a、b、c不全相等)，在每个有公共边界的两个最小三角形组成的菱形中，两组相对顶点上放置的数的和相等试求：放置最大数与放置最小数的点之间的最短距离r； 所有结点上放置的数的总和S(第二届国家冬令营)12试求格点凸32边形周长的最小值本节“情景再现”解答：1证明 若正方形的面积2，则其边长，其内切圆的直径而此内切圆的边与坐标轴平行的内接正方形边长1，于是，由定理2，此正方形内部至少有一个格点矛盾2解 内部恰有一个格点的正方形边长2， 3解：图中用粗线标出了一种走法显然，长一种满足要求的走法都包含了n段短横线与m段短竖线故可以考虑给出n+m个位置，在这些位置中选择n个位置给“横”，其余m个位置给“竖”于是所求的走法数为C 从(0，0)到(p，q)有C种走法，从(p，q+1)到(n，m)有C种方法； 共有CCC种方法4解 把每个点的横坐标与纵坐标的和记在此格点旁，凡记数被4除余0、余2的点染红，被4除余1的点染白，被4除余3的点染黑此时每条格线上都有三种颜色的点设取了白点A(4kr，4k1r)，5解 把棋盘的格点染成红蓝两色：相邻的点染色都不同，如图中画圈的点染红，未画圈的点染蓝则马只能从某色点跳到不同色的点图中共有23个红点，22个蓝点故若马从蓝点出发，跳遍棋盘，若最后跳到蓝点，则跳过的蓝点应比红点数多1个，若最后跳到红点，则红点与蓝点个数相等，但图中红点多1个，故不存在这种跳法6证明 设向上走x步，向右走y步，向斜左下走z步，共经过m(mn2)个格点(包括A、B)，则若能走，可得xz，yz+1，x+y+zm1，即3zm2，故 n23z+22(mod 3)，但平方数被3除的余数不可能为2故证7解 取x=l，y=m，则有xy9，x+y9这可用直角坐标系内的区域表示：即直线x+y=9，y=x，y=9这三条直线围成的三角形的内部及部分边界上的整点数即为解数现考虑由x=0，x=9，y=0，y=9这四条直线围成的正方形，其内部及边界上共有1010=100个格点直线y=x上在正方形内部的格点有一半满足要求，直线x+y=9上的点不满足要求，这两条直线的交点不是格点直线y=9上有点(1，9)，(2，9)，(9，9)满足要求故这100个格点中恰有满足要求共有25个满足条件的三角形解：对于一般的n值，当n为奇数时，三角形数=(n+1)2当n为偶数时三角形数由于y=x与x+y=n的交点是格点，故三角形数=(n+1)21)总之，对于一切n，三角形数=(n+1)28解 先考虑数0，它可以组成9个数对(0，1)，(0，2)，(0，3)，(0，9)如果这9个数对都要出现，则由于一个顶点只连了两条边，故0至少要在5个顶点上标记才有可能同理，1、2、3、，9都至少要在5个顶点标记才行，这样这个多边形至少要有50个顶点故这个正45边形不可能出现满足要求的标记法 “习题40”解答：1解：由于平行四边形对角线互相平分，故设其顶点坐标依次为(xi，yi)，(i1，2，3，4)，且(x1，y1)、(x2，y2)、(x3，y3)为格点，则x4x1x3x2，y4y1y3y2，故(x4，y4)也是格点2解 把此棋盘按上题的方法染色，当n为奇数时，马只能从某色点跳到同色点而不能跳到异色点，故当n为奇数时，不可能当n为偶数时，只要说明马能从一点跳到其相邻的点即可，如图，马从(0，0)先跳到(1，n)，再跳到(n+1，n1)，(1，n2)，(1，0)即跳到相邻的点于是可以跳到任意一点(图中画的是一个14“超级马”)3证明 经过(，0)的与x轴垂直的直线l可写为x=，此直线上所有点的横坐标都等于，故都不是有理点经过(，0)的且不与x轴垂直的直线l可写为y=k(x)设l经过两个有理点(m，n)，(h，g)(m，n，h，g都是有理数，mh)，则n=k(m)，g=k(h)，ng=k(mh)，由知mh，且k为有理数若ng0，则k0此时，由m为无理数，故k(m)为无理数与n为有理数矛盾故ng=0，此时直线为y=0，经过无穷多个有理点即经过(，0)的直线有且只有一条经过至少两个有理点4解：设三边长分别为x、y、z，由于对称性，可设xyz，可得xyz50z50xy；故有 yx， xyz即xy25， yzx2y50， 问题即是满足条件的整数解有多少组？问题转化为求由条件确定的平面区域中整点的个数易于计数得解为52种5解 线段OAn的方程为yx(0xn)，故f(n)等于该线段内的格点数若n3k(kN*)，则得yx (0xn)(kN*)，其内有两个整点(k，k+1)，(2k，2k+2)，此时f(n)=2；若n3k1(kN*)，则由于n与n+3互质，故OAn内没有格点，此时f(n)=0 f(1)+f(2)+f(1990)=2=13266解 把这些正方形分为两类：边与格线平行的正方形；边不与格线平行的正方形 边与格线平行的正方形：边长为k的这类正方形有(nk) 2个；边不与格线平行的正方形：它们都是前一种正方形的内接正方形：每个边长为k的第一类正方形，其一条边内都有k1个格点，每个这种格点都对应一个内接正方形，从而都有k1个内接的正方形所以，共有格点正方形的总数S=k (nk)2=n2k2nk2+k3n2n(n1)2n(n1)n(2n1)+n2(n1)2n2(n1)6n4(2n1)+3(n1)n2(n21)7解 设三边长为x，y，n，且xyn，本题可以理解为满足yx，x+yn的区域中恰有600个整点故在坐标系内作直线y=x，x+y=n，y=n，由这三条直线围成的三角形PBC即为所求区域正方形内共有(n1)2个格点，线段AC、OB内各有n1个格点，当n为奇数时，P不是格点，当n为偶数时，P是格点由对称性，PAB、PBC、PCO、POA内的格点数相等故 (n1)22(n1)+k=6004(n为偶数时k=1，n为奇数时，k=0) n24n+3 =2400k当n为奇数时，(n2)2=2401=492，解为n=51当n为偶数时，(n2)2=2400，无整数解 n=518解 本题即，当0x，xN*时，可以表示直线x=k (0k)上满足0y0，x及y0，y表示的区域内的格点数由对称性，也表示x0，x及y0，y表示的区域内的格点数，此二区域的并集即区域P，但其中由x=0，y=0，x=，y=围成的正方形区域内的格点被计算了两次，从而应该减去其中的格点数一次故得证9证明 令Ai(xi，yi)(i=1，2，n，xi，yiZ)，则 (x2x1)2+(y2y1)2= (x3x2)2+(y3y2)2= (xnxn1)2+(ynyn1)2= (x1xn)2+(y1yn)2令i=xi+1xi，i=yi+1yi，i2+i2=M(i=1，2，n，xn+1=x1，yn+1=y1)， 则1+2+n=0，1+2+n0，若i、i全为偶数，则可在上面三式中约去2的最低次幂，因此可以假定i、i中至少有一个为奇数由于奇数的平方mod 4后余1，故M1或2(mod 4)若M1(mod 4)，则每对i、i中都必有一奇一偶，此时1+2+n+1+2+n偶数+n个奇数=0，故n为偶数若M2(mod 4)，则每个i、i都是奇数，于是1+2+n为n个奇数之和=0，仍得n为偶数故证10解 取一直角坐标系，用单位格点正方形的对角线来表示每张票投票的结果，若所开的1张票选甲，则用斜率为1的对角线表示，若选乙，则用斜率为1的对角线表示，第一张票从原点开始连线，以后每开一张票都是接着前面已连的线连线(若第k1张票已连线到(k1，p)，而第k张票选甲，则连(k1，p)与(k，p+1)表示，若选乙，则连(k1，p)与(k，p1)表示)于是开票的过程可用一条连结(0，0)与(18，4)的折线表示其中4=11(1811)，折线的每一小段都是单位格点正方形的对角线这样的折线共有C条若在某一次甲得票少于乙，则此折线与直线y1相交仍由反射原理得所求应为矩形ABPD内的最短折线数，这样的折线共有C条 甲得票数始终不少于乙的开票方法有CC种11解 如图，结点上放置的数标在结点旁则 a+d=x1+y1，x1+y2=y1+d， ay1=x1d=y1y2=，即，同一条线上注的数成等差数列 若a、b、c互不相等，则r=1；若a、b、c中有两个相等时，r= (n为偶数)，或r= (n为奇数) 把三角形绕中心旋转120，240，所得标数和不变，而每个结点三次标数之和都是a+b+c， 结点总个数=1+2+3+(n+1)= (n+1)(n+2)； S=(n+1)(n+2)(a+b+c)12解 如图，取点(1，0)，(0，1)，(1，1)，(1，2)，(1，3)，(2，1)，(3，1)，(2，3)，(3，2)共32个点从原点向此32个点引向量，得32个方向互不相同的向量现按逆时针方向从(1，0)表示的向量开始，按这些向量与x轴正方向所成角从小到大的顺序，依次把这32个向量连结成一个凸32边形，由于这些向量的和为零向量，故这32个向量可连成一条闭折线，该闭折线围成一个凸32边形，由于每个向量起点与终点都是格点，故此32边形是格点多边形由于任一凸多边形中，不能有两边的向量方向相同故这个32边形周长最小所求最小周长为4(1+2+2+2)