关于格点多边形的性质的讨论

关于格点多边形的性质的讨论

湖南师范大学数学与计算机科学学院

张

垚

平面直角坐标系中,纵坐标和横坐标都为整数的点称为格点,顶点都为格点的凸n边形称为平面格点凸n边形,1×1的格点正方形称为单位格点正方形.

文[1]中提出了下列关于格点凸九边形的几个性质而没有给出证明:

命题A(1)平面格点凸九边形的内部至少有11个格点;

(2)平面格点凸九边形的内部及边界包含一个长为3,宽为2的格点长方形;

(3)平面格点凸九边形的内部及边界最少包含10个两两不同的单位格点正方形.

经研究后发现上述3个结论都不正确,事实上如下图,我们取格点A1(0,0),A2(3,1),A3(7,2),A4(12,3),A5(18,4),A6(16,3),A7(12,2),A8(7,1),A9(1,0).则格点凸九边形A1A2

A9的内部只含有10个格点,并且它的内部及边界不包含任何单位格点正方形,故命题A中的3个结论都不正确

.

进一步,我们还可以证明下列结论.定理B对任意正整数n≥3,存在平面格点凸n边形,其内部及边界不包含任何单位格点正方形.

为了证明定理B,我们需要下列明显成立的几何事实:

引理给定4个格点(A(a,),B(b,),C(c,+1),D(d,+1),其中a,b,c,d,为整数,且a<b,d<c,则

(1)△ABC和△ACD的内部及边界不包

含单位格点正方形;

(2)当a<b≤d<c时,平面格点凸四边形ABCD的内部及边界不包含单位格点正方形.

定理B的证明n=2m(m≥2)为偶数时,(m1)2令k(m1)2

0=[4]为不大于4

的最大整

数.作数列ai=k0+(i1),i=1,2,,m,记si=

∑i

a

=k1

k

0i+2

i(i1),i=1,2,

,m,取格点A0(0,

k=1

0),A1(s1,1),A2(s2,2),Am(sm,m),Am+1(sm

s1,m1),Am+2(sm

s2,m2),

,A2m1(sm

sm1,

1),则格点凸2m边形A0A1,

,A2m1的内部及边界不包含单位格点正方形.

事实上(如下图),设直线Ai1Ai的斜率为

k(i=1,2,2m,A1

i2m=A0),则易算出ki=

a,ikm+i=

1

a(i=1,2,,m),因为0≤a1<a2<

<

i

am,所以k1>k2>>km,km+1>km+2>

>k2m

且km<km+1,k2m<k1(当m=2时,a1=0,k1=k3=+∞),所以格点2m边形A0A1A2m1为格点

凸2m边形

.

其次,在格点凸四边形AiAi+1A2mi1A2mi

中(当m=2时,这个四边形不存在,不必讨论)(i=1,2,,m2),顶点坐标为Ai(si,i),Ai+1(Si+1,i+1),A2m

i1

(smsm

i1

,i+1),A2mi(sm

smi,i),它们满足

si=a1+a2++ai

<am

i+1

+am

i+2

+

+am=smsmi,si+1=a1+a2++ai+1<ami+ami+1

+

+am=sm

sm

i1

,

si+1

(sm

smi)

13