格子点の問題
数列(入試の標準) ★★★
難関大学でも度々出題される,
格子点の個数の求め方
格子点とは,$x$ 座標も $y$ 座標も整数である点のことをいいます.
格子点の個数の求め方
Ⅰ 格子点を直接数えていき,等差数列などの規則が見つかれば,既存の公式を使う.
Ⅱ $\boldsymbol{x=k}$ $\boldsymbol{(y=k)}$ のときの格子点の個数を $\boldsymbol{k}$ の関数で表し,該当範囲で和(シグマ)をとる.
※ 領域の境界線が格子点でない場合は一括で計算できないので注意!
Ⅱの方が一般的な方法です.まるで積分をして面積を求めるかのように格子点をシグマで計算します.
例題と練習問題
例題
例題
座標平面上で,$x$ 座標と $y$ 座標がいずれも整数である点 $(x,y)$ を格子点という.$n$ を自然数とする.
(1) $x\geqq 0$,$y\geqq0$,$x+y\leqq 2n$ を満たす格子点 $(x,y)$ の個数を求めよ.
(2) $x\geqq0$,$y\geqq0$,$y\leqq2x$,$x+2y\leqq20$を満たす格子点 $(x,y)$ の個数を求めよ.
(3) $y=-x^{2}+7x+2$,$y=-x+2$ で囲まれた部分の格子点 $(x,y)$ の個数を求めよ.
講義
まず領域を丁寧に書きます.
上のⅡの方法をメインとして説明します.
例題の解答
(1)
$x=k$ のときの格子点の個数を求めます.
算数の植木算の要領で出します.距離(間の数)が $-k+2n$ です.木の本数は $1$ を足しますので,$x=k$ のときの格子点は $-k+2n+1$ 個になります.
これを $0$ から $2n$ まで和をとればOKです.
(総数)
$\displaystyle =\sum_{k=0}^{2n}(-k+2n+1)$
$\displaystyle =(2n+1)+(2n)+\cdots+2+1 \ \cdots$ ☆
$\displaystyle =\{(2n+1)+1\}(2n+1)\cdot\dfrac{1}{2}$
$=\boldsymbol{(n+1)(2n+1)}$
※直接数えていけば,等差数列とわかり,いきなり☆の式が書けるはずです.それがⅠの方法.
(2)
$x\leqq 3$ と $x\geqq 4$ で場合分けをします.
$x\leqq 3$ のときは,$x=k$ のときの格子点の個数を求めます.$2k+1$ 個になります.
$x\geqq 4$ のときは,今まで通り縦の格子点を求めようとすると,境界線に格子点が来ないので偶奇で場合分けが必要で面倒です.そこで,$y=j$ のときの格子点(横の格子点)を求めて,$j=0$ から $j=8$ まで和をとります.
(総数)
$\displaystyle =\sum_{k=0}^{3}(2k+1)+\sum_{j=0}^{8}(-2j+17)$
$\displaystyle =1+3+5+7+17+15+\cdots+3+1 \ \cdots$ ☆
$\displaystyle =16+(17+1)\cdot9\cdot\dfrac{1}{2}$
$=\boldsymbol{97}$
※これも $x\leqq 3$ と $x\geqq 4$ で場合分けをして直接数えていけば,等差数列とわかり,いきなり☆の式を書いてもいいですね.
(3)
$x=k$ のときの格子点が $-k^{2}+8k+1$ 個です.
(総数)
$\displaystyle =\sum_{k=0}^{8}(-k^{2}+8k+1)$
$\displaystyle =1+\sum_{k=1}^{8}(-k^{2}+8k+1)$
$\displaystyle =1-\dfrac{1}{6}\cdot 8 \cdot9 \cdot 17+8\cdot \dfrac{1}{2}\cdot 8 \cdot 9+8$
$=\boldsymbol{93}$
※Ⅱの方法です.直接足していくと大変です.
練習問題
練習
(1) $y=x^{2}-4x-13$,$y=x+1$ で囲まれた部分の $x$,$y$ 座標がともに整数である点の個数を求めよ.
(2) $n$ を正の整数とし,$y=n-x^2$ で表されるグラフと $x$ 軸とで囲まれる領域を考える.この領域の内部および周に含まれ,$x$,$y$ 座標がともに整数である点の個数を $a(n)$ とする.$\sqrt{n}$ をこえない最大の整数を $m$ とするとき,$a(n)$ を $m$ と $n$ の多項式で表せ.
解答
(1)
$x=k$ のときの格子点が $-k^{2}+5k+15$ 個です.$k=-2$ のとき $1$ 個,$k=-1$ のとき $9$ 個,$k=0$ のとき $15$ 個は別でカウントして,$k=1$ から $k=7$ までシグマ計算すると
(総数)
$\displaystyle =1+9+15+\sum_{k=1}^{7}(-k^{2}+5k+15)$
$\displaystyle =25-\dfrac{1}{6}\cdot 7 \cdot8 \cdot 15+5\cdot \dfrac{1}{2}\cdot 7 \cdot 8+15\cdot 7$
$=\boldsymbol{130}$
※ すべてを $x$ 軸方向に $3$ 平行移動すると一括計算できて面白そうです.
(2) 出典:1999年早稲田大理工改
$x=k$ のときの格子点が $n-k^{2}+1$ 個.
$y=n-x^{2}$ が $y$ 軸に関して対象なので,$k=0$ のときの格子点に,$k\geqq 1$ のときの格子点の $2$ 倍を足す.
$a(n)$
$\displaystyle =n+1+2\sum_{k=1}^{m}(n-k^{2}+1)$
$\displaystyle =n+1+2\left\{nm-\dfrac{1}{6}m(m+1)(2m+1)+m\right\}$
$\displaystyle =n+1+2m(n+1)-\dfrac{1}{3}m(m+1)(2m+1)$
$\displaystyle =(n+1)(2m+1)-\dfrac{1}{3}m(m+1)(2m+1)$
$=\boldsymbol{\dfrac{1}{3}(2m+1)(3n+3-m^{2}-m)}$