【数学小話】格子点を数える問題の解法研究

数Bの数列の単元で登場するやや難しめの問題として、格子点の個数を求める問題があります。このタイプの問題の解法を研究してみます。

問題
解法①xまたはyを固定する
解法②長方形内にある格子点の半分
解法③nを1増やしたときの格子点の増加に注目する
解法④ズル？穴埋めであることを悪用

問題

$n$ を自然数とする。 $x＞ 0,\ y＞ 0,\ 3x+4y＜12n$ を満たす整数の組 $(x,y)$ の個数は、
$\displaystyle \fbox{ア}n^2-\fbox{イ}n+\fbox{ウ}$
である。

f:id:hby:20200212211831j:plain

n=2の場合の図を用意しました。問題の不等式はすべて＝がついていないので、この青の三角形の内部(周を含まない)にある格子点の個数を求めることになります。

今日はこの問題を複数の解法で求めます。問題によって不等号に＝が入っていたり入っていなかったりしますが、基本的な考え方はどれも同じです。

解法①xまたはyを固定する

xを固定するときは、x=aという直線上に格子点がいくつあるかをaで表し、aについて和をとります。yを固定するときも同様。今回はyを固定して解いてみます。

y=1という直線上にある三角形内の格子点の個数はいくつか
y=2という直線上にある三角形内の格子点の個数はいくつか
y=3という直線上にある三角形内の格子点の個数はいくつか

…

y=3n-1という直線上にある三角形内の格子点の個数はいくつか

というのをそれぞれ数え上げ、和をとればよい、という考え方です。一般に、

y=aという直線上にある三角形内の格子点の個数をN(a)と書くことにし、N(a)をaで表します。

f:id:hby:20200212213122j:plain

y=aを固定したとき、N(a)は、
$0＜x＜4n-\frac{4}{3}a$
を満たす整数xの個数となるので、
(y=aと固定されているので $3x+4y＜12n$ は $x＜4n-\frac{4}{3}a$ に変わる)

a=3m-2のときN(a)=4n-4m+2
a=3m-1のときN(a)=4n-4m+1
a=3mのときN(a)=4n-4m-1

と表すことができるので、aを1から3n-1まで動かしたときの和が求める答えなので、

$\displaystyle\sum_{a=1}^{3n-1}N(a)\\\displaystyle=\sum_{m=1}^{n}(4n-4m+2)+\sum_{m=1}^{n}(4n-4m+1)+\sum_{m=1}^{n-1}(4n-4m-1)\\\displaystyle=2n^2+(2n^2-n)+(2n^2-3n+1)\\=6n^2-4n+1$

とすれば出ます。

ちなみに、yを固定した今回はaの値によって3つの場合分けになりましたが、xを固定した場合は4つの場合分けをすることになるので、今回はyで固定した方が楽です。

利点
領域の形状にかかわらずできる(領域の境界が放物線などでもよい)

欠点
aの値によって場合分けをするのが面倒、シグマの計算の回数も増えがち

解法②長方形内にある格子点の半分

求める格子点の個数は、 $1\leqq x\leqq4n-1,\ 1\leqq y\leqq3n-1$ が表す長方形内にある格子点の（ほぼ）半分であることを用いて出します。
領域の境界上の格子点も数えるような問題なら、それに応じて適切な長方形を考えればOK。

f:id:hby:20200212224829j:plain

n=2の図で説明します。nの値がもっと大きいときの図は脳内で補完してください。
このオレンジの長方形内にある格子点の個数は、 $(4n-1)(3n-1)$ 個です。ここで、直線 $3x+4y=12n$ 上にある格子点が $n-1$ 個（この図における赤い点）あるので、これを引くと残りは $(4n-1)(3n-1)-(n-1)$ 個。これのちょうど半分が求める個数です。なので、
$\displaystyle\frac{(4n-1)(3n-1)-(n-1)}{2}\\=6n^2-4n+1$