解説

方針・初手

三角形の頂点は、座標軸との交点から

$$ (0,0),\quad (3n,0),\quad (0,2n)

$$

である。

求めるのは、この三角形の周および内部にある格子点の総数である。格子多角形なので、面積と境界上の格子点数から Pick の定理を用いるのが自然である。

解法1

三角形の面積を $S$ とする。底辺を $3n$、高さを $2n$ と見れば、

$$ S=\frac{1}{2}\cdot 3n\cdot 2n=3n^2

$$

である。

次に、境界上の格子点数を数える。

$x$ 軸上の辺は $(0,0)$ から $(3n,0)$ までなので、格子点数は

$$ 3n+1

$$

である。

$y$ 軸上の辺は $(0,0)$ から $(0,2n)$ までなので、格子点数は

$$ 2n+1

$$

である。

斜辺は $(3n,0)$ から $(0,2n)$ までである。この線分上の格子点数は、座標差の最大公約数を用いて

$$ \gcd(3n,2n)+1=n+1

$$

である。

ただし、この3辺の格子点数を単純に足すと、3つの頂点をそれぞれ2回ずつ数えている。したがって境界上の格子点数 $B$ は

$$ B=(3n+1)+(2n+1)+(n+1)-3=6n

$$

である。

Pick の定理より、内部の格子点数を $I$ とすると

$$ S=I+\frac{B}{2}-1

$$

が成り立つ。よって

$$ 3n^2=I+\frac{6n}{2}-1

$$

であるから、

$$ I=3n^2-3n+1

$$

である。

したがって、周および内部にある格子点の総数は

$$ I+B=(3n^2-3n+1)+6n=3n^2+3n+1

$$

となる。

解法2

三角形の周および内部の格子点は、整数 $x,y$ について

$$ x\geqq 0,\quad y\geqq 0,\quad 2x+3y\leqq 6n

$$

を満たす点である。

$y$ を固定して数える。$y$ は $0$ から $2n$ まで動く。

このとき

$$ 2x\leqq 6n-3y

$$

より、

$$ 0\leqq x\leqq \left\lfloor 3n-\frac{3y}{2}\right\rfloor

$$

である。

$y$ の偶奇で分ける。

**(i)**

$y=2k$ のとき、$k=0,1,\dots,n$ であり、

$$ 0\leqq x\leqq 3n-3k

$$

だから、このときの $x$ の個数は

$$ 3n-3k+1

$$

である。

**(ii)**

$y=2k+1$ のとき、$k=0,1,\dots,n-1$ であり、

$$ 0\leqq x\leqq \left\lfloor 3n-3k-\frac{3}{2}\right\rfloor=3n-3k-2

$$

だから、このときの $x$ の個数は

$$ 3n-3k-1

$$

である。

よって総数 $N$ は

$$ \begin{aligned} N &=\sum_{k=0}^{n}(3n-3k+1)+\sum_{k=0}^{n-1}(3n-3k-1)\\ &=\left\{(n+1)(3n+1)-3\cdot\frac{n(n+1)}{2}\right\} +\left\{n(3n-1)-3\cdot\frac{n(n-1)}{2}\right\}\\ &=\frac{(n+1)(3n+2)}{2}+\frac{n(3n+1)}{2}\\ &=3n^2+3n+1 \end{aligned}

$$

である。

解説

この問題は、三角形の内部・境界を合わせた格子点数を求める問題である。頂点がすべて格子点であるため、Pick の定理を用いると最短で処理できる。

斜辺上の格子点数を数えるときは、線分の両端の座標差が $(3n,-2n)$ であることから、

$$ \gcd(3n,2n)+1=n+1

$$

とする点が重要である。

直接数える場合は、$y$ を固定して $x$ の範囲を求めればよい。ただし、$\left\lfloor 3n-\frac{3y}{2}\right\rfloor$ が出るため、$y$ の偶奇で場合分けする必要がある。

答え

$$ 3n^2+3n+1

$$