直接进入正文(?)

定义格点多边形是指多边形的每个顶点A(x,y),都满足x,y是整数.其中A称为格点.

Part1.可能会用到的定理

引理的证明：

(i),(ii)直接使用正切公式即可

(iii)我们设第k条边的向量为(x_{k},y_{k}),长度为l_{k},我们有 sum_{i=1}^{n}{x_{i}}=0,sum_{i=1}^{n}{y_{i}}=0 ,设 x_{i},y_{i}(i=1,2,…,n) 两个数中a_{i}有个奇数，注意到a_{i}与第i条边的奇偶性相同，且sum_{i=1}^{n}{a_{i}}equiv0(mod2)(由sum_{i=1}^{n}{x_{i}}=0,sum_{i=1}^{n}{y_{i}}=0推出),从而有 sum_{i=1}^{n}{l_{i}}equiv0(mod2)

(iv)我们分几步证明：

• 对于边平行于坐标轴的格点长方形，容易验证结论成立.
• 对于直角边平行于坐标轴的直角三角形，假设边上的格点有B'个，内部的格点有I' 个，斜边上有t个格点.我们将其扩展为一个边平行于坐标轴的格点长方形，则长方形边上的格点有B=2B'-2t-2个,内部格点有I=2I'+t个，代入2Striangle=frac{B}{2}+I-1知结论成立.
• 对于一般的三角形可以将其扩展为边平行于坐标轴的格点长方形，类似上一步中的计算可知结论成立.

• 假设结论对于k边形成立，则对于k+1边形P_{k+1}，我们可以将其分割为一个三角形triangle和一个k边形P_{k}.假设triangle与P_{k}的公共边上有t个格点.我们有I=I_{triangle}+I_{k}+t,B=B_{triangle}+B_{k}-2t-2,故 S=S_{triangle}+S_{k}=(frac{B_{k}}{2}+I_{k}-1)+(frac{B_{triangle}}{2}+I_{triangle}-1)=frac{B}{2}+I-1 ,结论成立.

(v)假设存在格点正n边形（ngeq 5,nne 6),我们取边长最短的格点正n边形，任选顶点A及与它相邻的两个顶点构造平行四边形，设A在平行四边形中的对顶点为A'，类似的得到另外n个点，显然这n个点都在n边形内且构成一个更小的格点正n边形，矛盾.因此我们只需证明n=3,6时不存在格点正n边形即可.而当n=3时，设边长为a，则面积为frac{sqrt{3}}{4}a^{2}是一个无理数，这与(iv)所得面积是有理数矛盾.同理我们知道也不存在格点正六边形.

(事实上，这种递降的思路在格点问题中经常出现，之后的笔记也会时常用到)

(vi)直接对奇偶性进行分析即可，思路类似于(iii)但比(iii)略难.详细证明略去.

(vii)n=4时取边长为1的正方形即可，n=8时，如下图

接下来证明当ngeq 3,nne 4,8时，tanfrac{2pi}{n}notin Q（此时结合(ii)即得结论成立）.设theta=frac{2pi}{n}且 tanfrac{2pi}{n}in Q ，由Euler恒等式e^{2pi i}+1=0,e^{itheta},e^{-itheta}是方程x^{n}=-1的根，因此e^{itheta},e^{-itheta}是代数整数，从而left( e^{itheta}+e^{-itheta} right)^2=4cos^2theta也是代数整数.注意到frac{1}{cos^2theta}=1+tan^2thetain Q,所以有4cos^2thetain Q,结合4cos^2theta是代数整数，我们有4cos^2thetain Z，故有4cos^2theta=0,1,2,3,4.解得theta=frac{pi}{2},frac{pi}{3},frac{pi}{4},frac{pi}{6},0,其中当thetanefrac{pi}{2},frac{pi}{4}时，tanthetanotin Q.证毕

（代数整数定义：所有首一整系数多项式的根的集合构成的数域.代数整数在加法和乘法下是封闭的，但是对除法不封闭.之前的笔记提及了它的一个性质：若alphain Q,则alphain Z.定理(vii)的核心证明思路就是利用首一整系数多项式的这个性质.由于相关性不强以及我对抽象代数并不是很了解，有关代数数的内容在此略去)

(viii)设A,B中垂线上存在格点O(p,q)，则OA的奇偶性等于(p-a)+(q-b)的奇偶性，OB的奇偶性等于(p-c)+(q-d)的奇偶性，由OA=OB知结论成立.

(ix)即格点三角形面积公式，实际上可以直接暴算推导owo

(x)设三角形三个顶点为A,B,C,内部的格点为S，由Pick定理易知Striangle ASB=Striangle BSC=Striangle CSA=frac{1}{2},故S为triangle ABC重心.

事实上，边界和内部不含格点的三角形被称为基本三角形，且

(xi)将坐标平面分为若干个1×1的方格并将它们重叠，由抽屉原理知存在至少n+1个点重叠，它们即为满足条件的n+1个点A_{1},A_{2},…,A_{n+1}.

(xii)我们对K做位似变换(x,y)rightarrow(frac{x}{2},frac{y}{2}),得到Krightarrow K'.注意到K'的面积大于1，由（xii）知存在两个点A'(x_{1},y_{1}),B'(x_{2},y_{2})in K'满足x_{1}-x_{2},y_{1}-y_{2}均是正整数.考虑点A(2x_{1},2y_{1}),B(2x_{2},2y_{2}).由K中心对称知C(-2x_{2},-2y_{2})in K.从而AC中点M(x_{1}-x_{2},y_{1}-y_{2})in K，证毕.

格点问题通常只需要用到二维的Minkowski定理(据某文说，可以使用Minkowski定理给出Fermat二平方和定理与Lagrange四平方和定理的简洁证明，然而我没有找到ta引用的参考文献qwq)

(我找到了一个有关这个的回答ww,但是里面使用的Minkowski定理超过二维..

https://www.zhihu.com/answer/221648081

Part2.Farey序列相关

先介绍Farey序列的定义：

（图片来自《初等数论》）

由于我们可以将每个Farey序列中的数frac{a}{b}对应坐标系上的一点(a,b)，且可以由Farey序列导出一些性质，因此Farey序列也可能出现在一些较复杂的格点问题中.Farey序列的一个性质可以用上面的知识给出证明.

证明：取Farey序列相邻的两项frac{a}{b},frac{a'}{b'}，将其对应到平面上的点A(a,b),A'(a',b')，坐标原点为O，由定义知triangle OAA'的边上和内部没有整点，故由Pick定理知S_{triangle}OAA'=frac{1}{2}，由三角形坐标公式知 S_{triangle}OAA'=frac{1}{2}|ab'-a'b| ,再结合a'b>ab',结论成立.

与Farey序列相关的竞赛题较少，比如今年罗马尼亚大师杯P5：

Part3基础例题部分.

证明：设椭圆内所有格点的最大凸包为K，顶点及边上的格点数为B，内部格点数为I，周长为P'，面积为S'.注意到椭圆内部的格点均在该凸包边或内部，且K边上及内部不包含除椭圆内部的点以外的点，故我们有L=B+I.又注意到K边上相邻的格点距离至少为1，因此Bleq P'leq P，结合Pick定理S'=frac{B}{2}+I-1,我们有frac{P}{2}+S+1geq frac{B}{2}+S'+1geq frac{B}{2}+(frac{B}{2}+I-1)+1=B+I=L,证毕

（注：本题是清华19年秋令营第一天第四题，难度很小，估计考场上人均第四题（全卷最简单，然而我去年直接白给了qwq

证明：设正方形顶点及边上的格点数为B，内部格点数为I，我们有n^2=frac{B}{2}+I-1,而要整的结论是B+Ileq(n+1)^2,结合两式我们只需证明Bleq 4n.这是简单的，因为正方形边长为4n，而正方形边上相邻两个格点距离至少为1，因此正方形顶点及边上最多有4n个格点.

证明：注意到五个格点中必有两个格点的横纵坐标奇偶性相同，从而它们的中点是格点，由Pick定理知含这两点的三角形面积不小于1.假设只有这三个三角形的面积大于frac{1}{2}，又设这五个点为A,B,C,D,E,其中线段AB上有一个格点.不妨假设四边形四个顶点顺时针依次为ACDE，注意到Striangle ACE=Striangle ACD=frac{1}{2},故AC||DE.同理AE||CD,因此ACDE是平行四边形.同理B,C,D,E四个点组成的四边形也是平行四边形.但是C,D,E三个点确定一个平行四边形，矛盾.因此至少四个三角形面积大于frac{1}{2}.只有四个三角形面积大于frac{1}{2}是可以做到的，构造如下图.

注1：开头“平面上五个格点必存在两点，它们连线上存在格点”的三维拓展就是第32届Putnam数学竞赛的第一题.

注2：平面上五个无三点共线的选定点（不一定是格点）还有如下性质：可以从中选出三个点构造折线，且该折线的两条线段斜率同正或同负.这在Dilworth定理或Erdös-Szekeres引理的观点下是显然的.不用这两个定理也不难证明.

实际上Erdös-Szekeres引理只是Dilworth定理的一个简单推论.由于Dilworth定理比较抽象(初学的时候确实觉得它挺抽象的..)，所以应用范围非常之广owo.然而这与本笔记内容相关性不大，所以直接略过（？

证明：我们采取类似定理(v)的思路.使用反证法，设存在这样的五边形ABCDE，它的对角线交出的五边形A_{1}B_{1}C_{1}D_{1}E_{1}内部和边界上均不存在格点.取其中面积最小的凸五边形ABCDE.考虑五个三角形triangle ABC,triangle BCD,triangle CDE,triangle DEA,triangle EAB,不妨设其中面积最小的三角形为triangle BCD.过B,C,D做平行四边形BCDX，简单推理后我们知道X在五边形ABCDE内部，而根据假设，X不在五边形A_{1}B_{1}C_{1}D_{1}E_{1}的内部.不妨设X在triangle ABC内部.显然格点五边形AXCDE对角线交出的五边形在A_{1}B_{1}C_{1}D_{1}E_{1}内部且不含格点，于是我们得到了更小的满足条件的格点五边形，矛盾.

注：一个简单的中间结论是：

Part3 几个小性质（有一些看着显然(雾)，但是证起来并不是特别显然.

证明：若该正方形面积大于1，注意到左边界和右边界距离大于1，因此它们之间必存在直线x=a,使得k为整数.同理上下边界之间存在直线y=b使得b为整数，此时正方形内部存在格点(a,b)，矛盾.

证明:在圆的内部做正方形使得正方形的边与坐标轴平行.由5知正方形面积不超过1，故圆的半径rleqfrac{sqrt{2}}{2},证毕.

证明：做正方形的内切圆，知其半径rleqfrac{sqrt{2}}{2}，故正方形边长不大于sqrt{2}.

证明：假设某格点在圆内，我们考虑它周围的八个格点，圆心一定位于这八个点围成的正方形内.以这八个点为圆心1为半径做圆,八个圆覆蓋了这个正方形，因此圆心与距离最近的点距离不超过1，从而圆的半径不超过1，证毕.

证明类似于7，不再赘述.

上面几个简单性质的证明方法非常之多，这里为了偷懒(划掉)缩短篇幅略去.有关格点的基本性质到这里结束owo

Part4例题部分

证明：我们使用Minkowski定理来解这道题.

假设可以看到园外的点P.设直线OP交圆O于C,D，过C,D做OP的垂线并取出距离为r的点P,Q,R,S.由于r>0.02m，故矩形PQRS的面积大于4，由Minkowski定理矩形PQRS内存在格点A以及其关于O的对称点B.若格点在圆内，则以A,B为圆心半径为r的圆定与CD相交,此时无法从O看到G，矛盾.因此A在圆外.注意到2500=OC^2<OA^2<OD^2<2501,但是OA^2是整数，矛盾.证毕.

(明显感觉即使是看起来简单漂亮的格点问题难度依然不小qwq，这些题目多多少少沾点构造)

本题唯一的入手点显然是考虑圆与圆之间的间隙.如果我们能够说明对于三个圆，它们之间的间隙必存在格点，即证毕.而结合我们在前文所证的题6，我们考虑做与三个相邻圆相切的圆并对该圆的半径进行估计.

证明:假设存在这样的族Gamma，显然我们可以做一个与三个族Gamma的圆相切的圆c，它不与其他任何圆相交(不是相切).设这三个圆圆心为A,B,C,c的圆心为O,半径为r.易知∠AOB,∠BOC,∠COA中必有一个角不大于120°.不妨设∠AOBleq 120°.又设OA=a,OB=b，由余弦定理我们有(r+a)^2+(r+b)^2+(r+a)(r+b)geq (a+b)^2,即3r^2+3r(a+b)-(a+b)^2geq 0.我们来证明r>frac{3}{4}.使用求根公式，要证的结论等价于-3(a+b)+sqrt{9(a+b)^2+12ab}>frac{9}{2}①,对其进行代数变形得到①Leftrightarrow (2a-frac{9}{2})(2b-frac{9}{2})>30,结合ageq5,bgeq5即证.但是由题7，r>frac{3}{4}>frac{sqrt{2}}{2},圆O内必存在格点，矛盾.

注：直接证明r>frac{sqrt{2}}{2}也是可行的(

证明：若三角形A'B'C'是最小的满足条件的三角形且外心为格点，设A'(a,b),B'(c,d),则以A'B',A'C'为底边沿同一方向(顺或逆时针,下设为逆)做等腰直角三角形.，设直角顶点分别为B'',C'',由全等显然有A''(frac{a-b}{2},frac{a+b}{2}),B''(frac{c-d}{2},frac{c+d}{2}),而由定理(vii)我们知道A'',B''均为格点，此时形成了更小的满足条件的格点三角形，矛盾.

这道题的难点在于无法通过猜答案或者考虑较小情况来导出证明（我一开始从较小情况入手手，想探索使得triangle ABC的面积是k的A,B要满足的条件,再使用类似于题3的手法估计各顶点之间的格点个数（然而我失败了，是我太鶸了qwq））

证明：我们来说明k=180180是满足条件的最小正整数.由于|T|>200>14^2,故对于1leq tleq14,T中总存在两个格点A(a,b),B(c,d)满足aequiv c(mod t),bequiv d(mod t).由题意知存在点C(x,y)使得triangle ABC的面积是k.由(ix)知pm2k=pm2Striangle ABC=(ad-bc)+(c-a)y+(b-d)xequiv0(mod t),从而对于1leq tleq14，t|2kRightarrow [1,2,…,13,14]|2kRightarrow180180|k.构造是简单的，我们取k=180180,T=left{ (x,y)|0leq x,yleq14,x,yin Z right}，对于T的两个格点A(a,b),B(c,d)，取C(c+frac{2k}{d-b},d)知结论成立.

本题难度不大，有两种类似的解法.

证1：我们来证明n最大为8.将平面上所有的格点分划为以下九个集合.

A_{i}=left{ (x,y)|xequiv varepsilon_{1}(mod 3),yequiv varepsilon_{2}(mod 3) right},其中varepsilon_{1}equiv-1,0,1(mod 3),varepsilon_{2}equiv-1,0,1(mod 3),i=1,2,…,9.定义(a,b)+(c,d)=(a+c,b+d),其中的加法是模3意义下的绝对最小剩余系的加法.设A=left{ 1,2,…,9 right},对于x,y,zin A,映射f满足f(x,y)=z,若A_z=-(A_x+A_y).显然E中不存在点Xin A_x,Yin A_y,Zin A_z满足f(x,y)=z，否则由定义X,Y,Z的横纵坐标之和均为3的倍数，即triangle XYZ的重心是格点，矛盾.而且显然有若x,y,z不全相同，则x,y,z两两不同.若存在E中的五个点属于不同的A_i,不妨设为A_1,A_2,…,A_5,则由前面的结论，f(x,y)=z(x,y=1,2,3,4,5,xne y.z=6,7,8,9).x,y取遍1,2,3,4,5时，f(x,y)=z取10个值，由抽屉原理必存在f(x_1,y_1)=f(x_2,y_2)=f(x_3,y_3),x_1,x_2,x_3,y_1,y_2,y_3中必有两个数相同，不妨设x_1=x_2，这告诉我们y_1=y_2，矛盾.故E中最多存在四个点属于不同的A_i,而显然不存在三个点同属于一个A_i，因此nleq 2times 4=8.n=8时，下图八个点显然满足条件.

第二种证明的思路与第一种证明思路相仿：将坐标平面上的所有点重叠地平移到一个3×3的格点阵中，证明E中的点最多在四个位置上.这个证明类似于Blichfeidt定理（即定理(xi)）的证明.本题的一个中间结论是：

考虑到笔记过长，还是分上下两篇吧

11.14更新，没有下篇了qwq