数学A 整数問題 問題 109 解説

方針・初手

格子点を数える問題なので、各点を座標 $(x,y)$ で表し、整数条件を式に落とす。

（1） では線分 $OA$ 上の点を直接数える。

（2） では各整数 $x$ に対して取り得る整数 $y$ の個数を足し上げる。

（3） では $\triangle OCD$ 内の格子点が

$$ x \geqq 0,\quad y \geqq 0,\quad x+y \leqq n $$

を満たす整数点であることを使い、和を計算する。

解法1

（1）

線分 $OA$ は $O(0,0)$ と $A(18,12)$ を結ぶので、その傾きは

$$ \frac{12}{18}=\frac{2}{3} $$

である。したがって、線分 $OA$ 上の点は

$$ y=\frac{2}{3}x $$

を満たす。

格子点であるためには $x,y$ がともに整数でなければならない。$x$ が整数のとき、$y=\frac{2}{3}x$ が整数となるには、$x$ が $3$ の倍数であればよい。

線分上では $0\leqq x\leqq 18$ だから、

$$ x=0,3,6,9,12,15,18 $$

である。これに対応して $y$ も整数になる。

よって、線分 $OA$ 上の格子点の個数は

$$ 7 $$

である。

（2）

$\triangle OAB$ は

$$ O(0,0),\quad A(18,12),\quad B(18,0) $$

を頂点とする三角形である。

線分 $OA$ は

$$ y=\frac{2}{3}x $$

であり、三角形の周または内部にある格子点は、整数 $x$ に対して

$$ 0\leqq x\leqq 18,\quad 0\leqq y\leqq \frac{2}{3}x $$

を満たす整数点である。

したがって、各整数 $x$ に対して取り得る $y$ の個数は

$$ \left\lfloor \frac{2x}{3}\right\rfloor+1 $$

である。よって求める個数は

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

である。

ここで $x=3q,3q+1,3q+2$ に分けると、

$$ \left\lfloor \frac{2(3q)}{3}\right\rfloor=2q,\quad \left\lfloor \frac{2(3q+1)}{3}\right\rfloor=2q,\quad \left\lfloor \frac{2(3q+2)}{3}\right\rfloor=2q+1 $$

である。

$x=0$ から $17$ までは $q=0,1,\dots,5$ の $3$ 個ずつに分けられ、最後に $x=18$ が残る。

したがって、

$$ \begin{aligned} \sum_{x=0}^{18}\left\lfloor \frac{2x}{3}\right\rfloor &=\sum_{q=0}^{5}{2q+2q+(2q+1)}+12\\ &=\sum_{q=0}^{5}(6q+1)+12\\ &=6\cdot \frac{5\cdot 6}{2}+6+12\\ &=108 \end{aligned} $$

である。よって格子点の総数は

$$ 108+19=127 $$

である。

（3）

$\triangle OCD$ の周または内部にある格子点を $P=(x,y)$ とする。このとき

$$ x,y\in \mathbb{Z},\quad x\geqq 0,\quad y\geqq 0,\quad x+y\leqq n $$

である。

$m_1$ の計算

$x$ を固定すると、$y$ は

$$ 0,1,2,\dots,n-x $$

を取り得る。したがって、同じ $x$ に対して格子点は $n-x+1$ 個ある。

よって、$P_x$ の総和 $m_1$ は

$$ m_1=\sum_{x=0}^{n}x(n-x+1) $$

である。これを計算すると、

$$ \begin{aligned} m_1 &=\sum_{x=0}^{n}{x(n+1)-x^2}\\ &=(n+1)\sum_{x=0}^{n}x-\sum_{x=0}^{n}x^2\\ &=(n+1)\cdot \frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6}\\ &=\frac{n(n+1)(n+2)}{6} \end{aligned} $$

である。降べきの順に整理すると、

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

である。

$|P_x-P_y|$ の総和

次に

$$ |P_x-P_y|=|x-y| $$

の総和を求める。

$x+y=t$ とおく。$t$ は

$$ 0,1,2,\dots,n $$

を動く。

固定した $t$ に対して、格子点は

$$ (x,y)=(0,t),(1,t-1),\dots,(t,0) $$

である。このとき

$$ |x-y|=|x-(t-x)|=|2x-t| $$

となる。

まず $t=2r$ のとき、

$$ \sum_{x=0}^{2r}|2x-2r| =2\sum_{x=0}^{2r}|x-r| =2r(r+1) $$

である。

次に $t=2r+1$ のとき、

$$ \sum_{x=0}^{2r+1}|2x-(2r+1)| =2{1+3+\cdots+(2r+1)} =2(r+1)^2 $$

である。

$n$ が偶数のとき

$n=2q$ とおく。

このとき、$t$ が偶数の場合は $t=0,2,\dots,2q$、奇数の場合は $t=1,3,\dots,2q-1$ である。よって

$$ \begin{aligned} m_2 &=\sum_{r=0}^{q}2r(r+1)+\sum_{r=0}^{q-1}2(r+1)^2\\ &=2\sum_{r=0}^{q}(r^2+r)+2\sum_{s=1}^{q}s^2\\ &=4\sum_{r=1}^{q}r^2+2\sum_{r=1}^{q}r\\ &=4\cdot \frac{q(q+1)(2q+1)}{6}+2\cdot \frac{q(q+1)}{2}\\ &=\frac{q(q+1)(4q+5)}{3} \end{aligned} $$

である。

$n=2q$、すなわち $q=\frac{n}{2}$ を代入すると、

$$ m_2=\frac{n(n+2)(2n+5)}{12} $$

である。降べきの順に整理して、

$$ m_2=\frac{1}{6}n^3+\frac{3}{4}n^2+\frac{5}{6}n $$

である。

$n$ が奇数のとき

$n=2q+1$ とおく。

このとき、$t$ が偶数の場合は $t=0,2,\dots,2q$、奇数の場合は $t=1,3,\dots,2q+1$ である。よって

$$ \begin{aligned} m_3 &=\sum_{r=0}^{q}2r(r+1)+\sum_{r=0}^{q}2(r+1)^2\\ &=2\sum_{r=0}^{q}(r^2+r)+2\sum_{s=1}^{q+1}s^2\\ &=\frac{q(q+1)(2q+1)}{3}+q(q+1)+\frac{(q+1)(q+2)(2q+3)}{3}\\ &=\frac{(q+1)(q+2)(4q+3)}{3} \end{aligned} $$

である。

$n=2q+1$、すなわち $q=\frac{n-1}{2}$ を代入すると、

$$ m_3=\frac{(n+1)(n+3)(2n+1)}{12} $$

である。降べきの順に整理して、

$$ m_3=\frac{1}{6}n^3+\frac{3}{4}n^2+\frac{5}{6}n+\frac{1}{4} $$

である。

解説

格子点の個数は、座標を整数として扱い、範囲条件を不等式で表すのが基本である。

（1） は線分の傾きから $y=\frac{2}{3}x$ とし、$y$ が整数になる $x$ を数えればよい。

（2） は三角形の内部を $x$ ごとに縦に切って数える。各 $x$ に対して $y$ の範囲が $0\leqq y\leqq \frac{2}{3}x$ となるため、床関数を使って個数を足し上げる。

（3） は $x+y\leqq n$ という条件に直すのが重要である。$m_1$ は $x$ を固定して数えると自然に求まる。一方、$|x-y|$ は $x+y=t$ でまとめると、同じ斜めの列ごとに処理できる。$t$ の偶奇によって和の形が変わるため、最後に $n$ の偶奇で場合分けする必要がある。

答え

(1)

$$ 7 $$

(2)

$$ 127 $$

(3)

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

$n$ が偶数のとき、

$$ m_2=\frac{1}{6}n^3+\frac{3}{4}n^2+\frac{5}{6}n $$

$n$ が奇数のとき、

$$ m_3=\frac{1}{6}n^3+\frac{3}{4}n^2+\frac{5}{6}n+\frac{1}{4} $$