数学A 場合の数 問題 6 解説

方針・初手

求める点は、$x,y$ がともに整数で、三角形の内部または周上にある点である。

三角形は第1象限にあり、境界は

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

であるから、数えるべき点は

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

を満たす整数点である。したがって、$x$ を固定して、そのとき取り得る $y$ の個数を数える。

解法1

条件 $3x+2y\leqq 6n$ より、

$$ 2y\leqq 6n-3x $$

である。よって、$x$ を固定したとき、$y$ は

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

を満たす整数である。

また、$y\geqq 0$ となるためには

$$ 6n-3x\geqq 0 $$

であればよいから、

$$ 0\leqq x\leqq 2n $$

である。

したがって、求める個数は

$$ \sum_{x=0}^{2n}\left(\left\lfloor \frac{6n-3x}{2}\right\rfloor+1\right) $$

である。

ここで、$x$ の偶奇で分ける。

(i)

$x=2k$ のとき

$0\leqq x\leqq 2n$ より、$k=0,1,\dots,n$ である。このとき

$$ \begin{aligned} \left\lfloor \frac{6n-3x}{2}\right\rfloor &= \left\lfloor \frac{6n-6k}{2}\right\rfloor \\ 3n-3k \end{aligned} $$

であるから、$y$ の個数は

$$ 3n-3k+1 $$

である。よって、この場合の個数は

$$ \sum_{k=0}^{n}(3n-3k+1) $$

である。

これを計算すると、

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

である。

(ii)

$x=2k+1$ のとき

$0\leqq x\leqq 2n$ より、$k=0,1,\dots,n-1$ である。このとき

$$ \begin{aligned} \left\lfloor \frac{6n-3x}{2}\right\rfloor &= \left\lfloor \frac{6n-3(2k+1)}{2}\right\rfloor \\ \left\lfloor 3n-3k-\frac{3}{2}\right\rfloor \\ 3n-3k-2 \end{aligned} $$

である。

したがって、$y$ の個数は

$$ 3n-3k-1 $$

である。よって、この場合の個数は

$$ \sum_{k=0}^{n-1}(3n-3k-1) $$

である。

これを計算すると、

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

である。

以上より、求める個数は

$$ \begin{aligned} \left(\frac{3n(n+1)}{2}+n+1\right) + \left(\frac{3n(n+1)}{2}-n\right) &=3n(n+1)+1 \end{aligned} $$

である。

解法2

三角形の頂点は

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

である。

格子点を数えるために、ピックの定理を用いる。ピックの定理より、格子多角形について

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

が成り立つ。ただし、$S$ は面積、$I$ は内部の格子点数、$B$ は境界上の格子点数である。

この三角形の面積は

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

である。

次に、境界上の格子点数 $B$ を求める。

$x$ 軸上の辺は $(0,0)$ から $(2n,0)$ までであり、格子点は $2n+1$ 個ある。

$y$ 軸上の辺は $(0,0)$ から $(0,3n)$ までであり、格子点は $3n+1$ 個ある。

斜辺は $(2n,0)$ から $(0,3n)$ までである。この線分上の格子点数は

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

である。

ただし、3つの頂点は各辺の数え上げで重複して数えられている。各頂点は2回ずつ数えられているので、重複分として $3$ を引く。

したがって、

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

である。

ピックの定理より、

$$ \begin{aligned} 3n^2 &=I+\frac{6n}{2}-1 \\ &=I+3n-1 \end{aligned} $$

であるから、

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

である。

求めるのは内部および周上の格子点数なので、

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

である。

よって、

$$ 3n^2+3n+1=3n(n+1)+1 $$

である。

解説

この問題は、三角形内の格子点を数える問題である。基本方針は、条件を不等式

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

に直して、整数解の個数を数えることである。

直接数える場合は、$x$ を固定して $y$ の範囲を調べる。ただし、$\left\lfloor \dfrac{6n-3x}{2}\right\rfloor$ が出てくるため、$x$ の偶奇で分ける必要がある。

また、頂点がすべて格子点である三角形なので、ピックの定理を使うと短く処理できる。特に、斜辺上の格子点数が $\gcd(2n,3n)+1=n+1$ になる点が重要である。

答え

$$ \boxed{3n(n+1)+1} $$