通过l×m×n的格点阵中至少两点的直线条数的探究

姚 璐 李 洋

(首都师范大学附属中学 100048)

引理1对任意的j≥k≥2，定义集合

Ak(j)={(x1,x2,…,xk)|1≤x1

证明对任意的(x1,x2,…,xk)∈Ak(j)，设x1,x2,…,xk的公差为d，则

由加法原理

特别地，我们有

ak(j)j234567…k2136101521…3012469…4001235…5000123…6000012…7000001………………………

特别地，我们规定当k>j时，ak(j)=0.

定义1对任意的正整数l，m，n，记

Ωl×m×n={(x,y,z)|1≤x≤l,1≤y≤m,1≤z≤n,x,y,z∈N*}.

定义2对任意的正整数k(2≤k≤n)，如果点列(P1,P2,…,Pk)满足

①Pi(xi,yi,zi)∈Ωl×m×n,i=1,2,…,k；

②(x1,x2,…,xk)∈Bk(l),(y1,y2,…,yk)∈Bk(m),(z1,z2,…,zk)∈Bk(n)；

其中Bk(j)={(x1,x2,…,xk)|1≤xi≤j(i=1,2,…,k),x1,x2,…,xk是等差数列}，则称点列(P1,P2,…,Pk)为Ωl×m×n的一个“好”k点组.

定义3Ωl×m×n的所有“好”k点组构成的集合为Bk(l,m,n)，记bk(l,m,n)= |Bk(l,m,n)|.

引理2设恰经过Ωl×m×n中j个点的直线条数为cj(l,m,n)，令bk(j)=2ak(j)+j，则

证明有两种方式计算bk(l,m,n)，

(1)一方面，由x1,x2,…,xk∈Bk(l)，设x1,x2,…,xk的公差为dx,

①当dx=0时，x1=x2=…=xk；

②当dx>0时，(x1,x2,…,xk)∈Bk(l)⟺(x1,x2,…,xk)∈Ak(l)；

③当dx<0时，(x1,x2,…,xk)∈Bk(l)⟺(xk,xk-1,…,x1)∈Ak(l).

所以，x1,x2,…,xk有l+ak(l)+ak(l)=bk(l)种选择.

同理y1,y2,…,yk有bk(m)种选择；

z1,z2,…,zk有bk(n)种选择.

由乘法原理

bk(l,m,n)=bk(l)·bk(m)·bk(n).

(2)另一方面，Ωl×m×n的所有“好”k点组(P1,P2,…,Pk)可以分为两类：

①P1=P2=…=Pk，这样的等距共线k点组共lmn个；

②P1,P2,…,Pk为同一条直线的等间隔的k个不同的点，设其所在直线上恰经过Ωl×m×n的j个点，则k≤j≤n.

设直线L恰经过Ωl×m×n中的j个点(其中k≤j≤n)，顺次记作P1,P2,…,Pj，则

Pi1,Pi2,…,Pik∈Bk(l,m,n)的充要条件是

i1=i2=…=ik，(i1,i2,…,ik)∈Ak(j)

或(ik,ik-1,…,i1)∈Ak(j)，

所以，直线L上的k个不同的点组成的“好”k点组共2ak(j)个，故

注意到，当2≤j≤k-1时，ak(j)=0，故

由(1)，(2)得

=bk(l)·bk(m)·bk(n)，故

定理至少通过Ωl×m×n中两点的直线条数记作N(l,m,n)，则

其中Un-1=(ui,j)(n-1)×(n-1)，

ui,j=ai+1(j+1)(1≤i,j≤n-1)；

Vn-1(l,m,n)=(v1,v2,…,vn-1)T，

(1≤i≤n-1).

证明令wi=ci+1(l,m,n)(1≤i≤n-1)，则由引理2

(v1,v2,…,vn-1)T=Un-1·(w1,w2,…,wn-1)T,

例如：N(5,6,7)可通过下述方式求出：

N(5,6,7)=(1,1,1,1,1,1)·

推论m×n的格点阵可以看作Ω1×m×n，若m×n的格点阵中，至少通过两点的直线条数记作N(m,n)，则有N(m,n)=N(1,m,n).

特别地，我们有

N(m,n)n234567…m261118273851…320355275100…46293136181…5140207274…6306405…7536………………………