정수론 | 격자다각형(Lattice Polygon)

격자평면(Lattice Plane)이란

평면 위에 가로 세로의 간격이 각각 1씩인 점들로 구성된 평면을 격자평면(lattice plane)이라고 부른다.

Visible point, Invisible point

원점 O에서 바로 볼 수 있는 점을 Visible point라 부르고 다른 격자점에 막혀서 보이지 않는 점을 Invisible point라고 부른다.

아래 그림의 경우 점 P가 Visible point이고 점 Q가 Invisible point가 된다.

정리: 격자평면에서 점 P(m,n)이 Visible point일 필요충분조건은 $gcd(m,n)=1$이고 Invisible point일 필요충분조건은 $gcd(m,n)\ne1$이다.

[증명] 어떠한 점이라도 점 P(m,n)을 원점 O에 대해 막지 않으려면 m, n보다 작은 정수 중 동일 기울기를 갖는 값이 존재해서는 안된다. 그러므로 $gcd(m,n)=1$이어야 점 P가 Visible point가 된다.

Invisible point에 대해서 다른 가로막는 격자점을 $Q(m',n')$이라고 하면 같은 기울기를 갖고 있기 때문에 임의의 정수 $k$에 대해 $k(m',n')=(m,n)$을 만족하는 정수 $k$가 존재한다. 따라서 $km'=m,\ kn'=n$이므로 $gcd(m,n)=k\ne1$이 된다.

정리: 직선 $y=ax$에서 기울기 $a$가 무리수이면 직선 $y=ax$는 원점 이외의 어떤 격자점도 지나가지 않는다.

[증명] $a$가 무리수일 때, 직선 $y=ax$에 어떤 격자점이 존재한다고 가정하자. 양의 정수 $m,n$에 대해 $n=am$이라 하면 $a=\cfrac{n}{m}$이므로 $a$는 유리수가 되어 모순이 된다.

∴ $a$가 무리수이면 그래프 $y=ax$는 원점을 제외한 어떤 격자점도 지나지 않는다.

정리: 양의 정수 $a,\ b$가 $gcd(a,b)=1$일 때, $[\frac{a}{b}]+[\frac{2a}{b}]+\cdots+[\frac{(b-1)a}{b}]$의 값은 $\frac{(b-1)(a-1)}{2}$이다.

[증명] $(0,0),\ (b,0),\ (0,a),\ (b,a)$를 연결하는 직사각형 안의 격자점에 대해 $gcd(a,b)=1$이므로 두개의 점$(0,0),\ (b,a)$를 연결하는 직선 $y=\cfrac{ax}{b},\ (0<x<b)$ 위에는 지나가는 격자점이 존재하지 않는다. 따라서, 네 개의 점을 연결하는 직사각형 내부 격자점 개수의 절반이고 그 값은 $\cfrac{(b-1)(a-1)}{2}$이다.

예제: $[1\cdot\cfrac{301}{201}]+[2\cdot\cfrac{301}{201}]+\cdots+[401\cdot\cfrac{301}{201}]$의 값을 구하여라.

$gcd(201,301)=1$이고 네 점 $(0,0),\ (402,0),\ (0,602),\ (402,602)$로 만들어진 직사각형 내부의 격자점을 생각했을 때 직선 $y=\cfrac{301}{201}x$가 지나가는 격자점은 $(201,301)$가 존재한다. 그러므로 직선이 직사각형을 절반으로 나누었지만 $(201,301)$은 어느 영역에도 속하지 않으므로 내부 격자점을 계산할 때는 제외해야 한다. 따라서 해당 점을 제외한 절반의 격자점의 개수는 $\cfrac{(402-1)(602-1)-1}{2}$이다. 그리고 직선 위에 존재하는 $(201,301)$도 포함해야 하므로 1을 더하여 주어진 식의 값은 $\cfrac{(402-1)(602-1)-1}{2}+1=120501$이다.

예제: 세 직선 $y=\frac{2}{3}x+\frac{1}{2}\ (0\le x\le12),\ y=0,\ x=12$로 이루어진 삼각형에서 삼각형 안과 변 위에 있는 정수 좌표의 개수를 구하여라.

주어진 영역은 엄연히 따지만 삼각형은 아니지만, 적당히 내부 영역과 변 위에 존재하는 격자점의 개수를 구하는 것으로 이해하기로 하자.

직선 $y=\cfrac{2}{3}x+\cfrac{1}{2}\ (0\le x\le12)$은 주어진 격자평면 내에 교차하는 격자점이 존재하지 않으므로 격자평면을 정확히 절반으로 양분함을 알 수 있다. 문제에서 제시된 조건에 따라 변 위에 있는 정수 좌표의 개수를 포함하면 가로와 세로 변의 길이를 1씩 빼지 않아도 되기 때문에 가로 길이가 13, 세로 길이가 10인 격자점 수의 절반에 해당한다. 따라서 구하고자 하는 값은 $\cfrac{13\cdot10}{2}=65$이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저