2012年12月6日木曜日

格子点

「解答例を見ても,さっぱり・・・」
と質問を受けた.

「\(x\geq0\),\(y\geq0\),\(2x+3y\leq6n\) の領域に含まれる格子点の個数を求めよ.」

解答例には図も,考え方も解説されていなかった.
これは考え方がわからないと,解答例はなんにも役に立たないなぁ.
解答例は,偶数段目と奇数段目を別々に分けて数えている.図にするとそうするわけがわかるのだが.


まず,
\(2x+3y\leq6n\)
は直線 \(2x+3y=6n\) の下側である.

そして,直線 \(2x+3y=6n\) は,\(\frac{x}{3n}+\frac{y}{2n}=1\) より,\(x\)軸上の切片が \((3n,0)\),\(y\)軸上の切片が \((0,2n)\)

ここで,「???」な感じになっていたので,直線について解説.
直線の方程式は最初は,「\(y\)が,\(x\) の関数」になっている形を習う.
傾き\(m\).\(y\)軸上の切片 \(k\) ならば,\(y=mx+k\) という寸法.
これって,\(y\)が,\(x\) の関数だから,変数としては対等ではなく,「\(x\)が偉くて,\(y\)が従っている感じ」を受けるし,「\(y\)軸に平行な直線」は傾きが存在しないから,表すことができない.

これを,2つの変数が対等にしたのが,「\(x\),\(y\)の1次方程式」の形 \(ax+by+c=0\).
ここまでは教科書に出ている.
もう一つ便利なのが,座標軸上の切片がわかる \(\frac{x}{p}+\frac{y}{q}=1\).実際,\(x=0\)や \(y=0\)
を代入すると,\(p\),\(q\) がそれぞれ切片になっていることがわかる.
もちろんこれは,原点を通る直線を表すことはできないけれど.

さて,\(n=1\) のとき,\(\frac{x}{3}+\frac{y}{2}\leq0\) で \((3,0)\) と \((0,2)\) を結ぶ直線上とその下の格子点である.つまり,
□□□
□□□
の対角線上及びその下の格子点を数える.
上辺より\(1+2+4\) となっている.

さて,\(n=2\) のとき,\(\frac{x}{6}+\frac{y}{4}\leq0\) で \((6,0)\) と \((0,4)\) を結ぶ直線上とその下の格子点である.つまり,
□□□
□□□
□□□□□□
□□□□□□
の左上から右下に直線を引いて,直線上とその下にある格子点を数えると,上から
\(1+2+4+5+7\)
となっている.

このパターンで増えていくわけだが,この数列の規則性を考える.

n がひとつ増えると,2段増えるが,そのことで,格子点の数は,2段上よりも3個増える.
ということは,数列の奇数番目と偶数番目はどちらも「公差3の等差数列」である.これで奇数段目と偶数段目で分ける理由がわかる.それは「2段ずつ増えているから」といえる.
これが「5段ずつ増える」なら「\(5k+1\),\(5k+2\),\(5k+3\),\(5k+4\),\(5k\)」段目ごとに分けるとどれも等差数列になるわけである.これが「考え方」

実際,奇数段目は
\(1+4+7\)
だし,偶数弾目は,
\(2+5\)
となる.

1,4,7 は初項1,公差 3 で一般項は \(3n-2\),
2,5 初項2,公差 3 で一般項は \(3n-1\),

そして,\(n=2\) のとき奇数段の項数は 3,偶数段の項数は2 だったから,
奇数段 \(3n-2\) の項数は \(n+1\),偶数段 \(3n-1\) の項数は \(n\).

ということで,
奇数段の格子点の数は
初項1,末項\(3(n+1)-2\),項数 \(n+1\) より,
\(\frac{(1+3n+3-2)(n+1)}{2}=\frac{3n^2+5n+2}{2}\)

偶数段の格子点の数は
初項2,末項3n-1,項数 n より,
\(\frac{(2+3n-1)n}{2}=\frac{3n^2+n}{2}\)

それらの合計は
\(\frac{6n^2+6n+2}{2}=3n^2+3n+1\)
これが答え.

したがって,\(n=1, \cdots, 10\) のときの格子点の数は
\(1+2+4=7, \)
\(1+2+4+5+7=19, \)
\(1+2+4+5+7+8+10=37, \)
\(1+2+4+5+7+8+10+11+13=61, \)
\(1+2+4+5+7+8+10+11+13+14+16=91, \)
\(1+2+4+5+7+8+10+11+13+14+16+17+19=127, \)
\(1+2+4+5+7+8+10+11+13+14+16+17+19+20+22=169, \)
\(1+2+4+5+7+8+10+11+13+14+16+17+19+20+22+23+25=217, \)
\(1+2+4+5+7+8+10+11+13+14+16+17+19+20+22+23+25+26+28=271, \)
\(1+2+4+5+7+8+10+11+13+14+16+17+19+20+22+23+25+26+28+29+31=331\)

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.