(cache)【格子点】放物線と直線で囲まれた領域の格子点の個数｜お茶の水女子大学

【お茶の水女子大学】

n を自然数とする．不等式

y≦2n2 , y≧12x2 , x≧0

を同時に満たす整数の組 (x,y) の個数を求めよ．

格子点問題の考え方

格子点

⇒　x or y 軸に平行な直線ごとにカウントし，総和(Σ)を考える

【格子点】x+y≦n(x,yは0以上の整数)を満たす格子点の個数｜2014中央大学

( ⅰ )　x=2k ( 0≦k≦n ) 上には

(2k,2k2) , (2k,2k2+1) , (2k,2k2+2) , ⋯ , (2k,2n2) の

2n2−2k2+1 個の格子点がある．

( ⅱ )　x=2k−1 ( 0≦k≦n ) 上には

x=2k−1 を y=12x2 に代入すると

y=12(2k−1)2=2k2−2k+12

これは格子点ではないため，領域に含まれる格子点は y 軸方向に 12 だけ上にある，(2k−1,2k2−2k+1) が格子点となる！

(2k−1,2k2−2k+1) , (2k−1,2k2−2k+2) , ⋯ , (2k,2n2) の

2n2−(2k2−2k+1)+1=2n2−2k2+2k 個の格子点がある．

よって求める格子点の個数は

∑k=0n(2n2−2k2+1)+∑k=1n(2n2−2k2+2k)

=2n2+1+∑k=1n(2n2−2k2+1)+∑k=1n(2n2−2k2+2k)

=2n2+1+∑k=1n(−4k2+2k+4n2+1)

=2n2+1−46n(n+1)(2n+1)+22n(n+1)+n(4n2+1)

=13(8n3+3n2+4n+3)