格子点の個数を数える問題の5通りの解法

座標平面において,各成分が全て整数である点を格子点(こうしてん)と呼ぶ。

例えば (0,0),(1,3),(3,0)(0,0),(1,3),(-3,0) などは格子点です。

格子点の個数を数える問題

「特定の領域に含まれる格子点の数」を数える問題は頻出です。

まずは簡単な例を見てみましょう。

例題1

x0,y0,x+y4x\geqq 0,y\geqq 0,x+y\leqq 4 内の格子点の数を求めよ。

解答

格子点

x=0x=0 上の格子点の数は5個
x=1x=1 上の格子点の数は4個
x=2x=2 上の格子点の数は3個
x=3x=3 上の格子点の数は2個
x=4x=4 上の格子点の数は1個

よって,全部で 5+4+3+2+1=155+4+3+2+1=15

このように,xx の値で場合分けして数えると数えやすいです。

次は難しい問題です。2008年名古屋大学の問題を考えます。

例題2

3x+2y20083x+2y\leqq 2008 を満たす 00 以上の整数の組 (x,y)(x,y) の個数を求めよ。

同じく,xx の値で場合分けして考えましょう。

解答

x=ax=a と固定した部分で領域内にある格子点の数 N(a)N(a) は,

3a+2y20083a+2y\leqq 2008
つまり
0y100432a0\leqq y\leqq 1004-\dfrac{3}{2}a
を満たす整数 yy の数と等しい。

格子点の数を数える

  • aa が偶数のとき,y=0y=0 から y=100432ay=1004-\dfrac{3}{2}a までの整数なので,
    N(a)=100432a+1N(a)=1004-\dfrac{3}{2}a+1 個(→補足)
  • aa が奇数のとき,y=0y=0 から y=100432a12y=1004-\dfrac{3}{2}a-\dfrac{1}{2} までの整数なので,
    N(a)=100432a12+1N(a)=1004-\dfrac{3}{2}a-\dfrac{1}{2}+1

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

N=a=0669N(a)=n=0334N(2n)+n=0334N(2n+1)=n=0334(10053n)+n=0334(10033n)=1005335+100333533343352×2=337010N=\displaystyle\sum_{a=0}^{669}N(a)\\ =\displaystyle\sum_{n=0}^{334}N(2n)+\sum_{n=0}^{334}N(2n+1)\\ =\displaystyle\sum_{n=0}^{334}(1005-3n)+\sum_{n=0}^{334}(1003-3n)\\ =1005\cdot 335+1003\cdot 335-\dfrac{3\cdot 334\cdot 335}{2}\times 2\\ =337010

補足:00 から 33 までの整数の個数は 0,1,2,30,1,2,3 の4個です。3個ではありません。同様に,00 から 100432a1004-\dfrac{3}{2}a までの整数の個数は 100432a1004-\dfrac{3}{2}a+1+1個になります。

yを固定して考える

さきほどは xx の値で場合分けして数えましたが,yy の値で場合分けして数えることもできます。

例題1の別解

格子点

y=0y=0 上の格子点の数は5個
y=1y=1 上の格子点の数は4個
y=2y=2 上の格子点の数は3個
y=3y=3 上の格子点の数は2個
y=4y=4 上の格子点の数は1個

よって,全部で 5+4+3+2+1=155+4+3+2+1=15

例題1の場合は,xx で場合分けしても yy で場合分けしても実質同じでした。

例題2の場合は,yy で場合分けすると計算が少しめんどうになります。分母に3が登場してしまうからです。

練習問題

例題2を yy を固定して計算してみよう。

斜めに切る

「斜めに切る」ことで格子点を数えることもできます。計算がめんどうになるのであまり使いませんが,一応紹介しておきます。

例題1の別解

格子点

x+y=4x+y=4 上の格子点の数は5個
x+y=3x+y=3 上の格子点の数は4個
x+y=2x+y=2 上の格子点の数は3個
x+y=1x+y=1 上の格子点の数は2個
x+y=0x+y=0 上の格子点の数は1個

練習問題

例題2を 3x+2y3x+2y を固定して計算してみよう。

長方形の半分とみなす

「長方形領域なら格子点の数は簡単に数えられる」ことを使って解いてみましょう。対角線部分に注意する必要があります。

例題1の別解

図の大きな正方形には 5×5=255\times 5=25 個の格子点がある。 格子点

  • は同じ数
  • 対角線上のは5個

よって,=25 より (255)÷2=10(25-5)\div 2=10

よって,求める格子点の数は,=15

例題2(再掲)

3x+2y20083x+2y\leqq 2008 を満たす 00 以上の整数の組 (x,y)(x,y) の個数を求めよ。

解答

長方形を用いて格子点を数える

  • A(0,1004)A(0,1004)B(668,2)B(668,2) を結ぶ線分を対角線とする長方形上(周も含む)にある格子点の数は,6691003=671007669\cdot 1003=671007

  • 線分 ABAB 上にある格子点の数は,00 以上 668668 以下の偶数の数と等しいので 335335

よって,数えたい格子点のうち,y2y\geq 2 を満たす格子点の数は,

「対角線上にない格子点の数」+ 「対角線上にある格子点の数」
=12(671007335)+335=335671=\dfrac{1}{2}(671007-335)+335=335671

最後に y=1y=1 上にある格子点の数(669669 個)と y=0y=0 上にある格子点の数(670670 個)を足し合わせると,

335671+669+670=337010335671+669+670=337010

ピックの定理を使う方法

格子点の数を数える裏技としてピックの定理があります。

ピックの定理を使う方法

頂点がすべて格子点である多角形について,

S=12E+I1S=\dfrac{1}{2}E+I-1

が成立する。ただし SS は面積,EE は辺上にある格子点の数,II は内部にある格子点の数。

例題1の別解

I=3I=3S=8S=8 はすぐにわかる。

よってピックの定理より,E=2(S+1I)=12E=2(S+1-I)=12

よって求める格子点の数は E+I=15E+I=15

例題2をピックの定理で解く方針

ピックの定理は領域の各頂点が格子点でないと使えません。(今回は (20083,0)(\frac{2008}{3},0) が頂点になっている)。それでも強引に使おうとすると「領域を二つに分割して,大きい方をピックの定理で求めて,小さい方は直接数える」という方法になります。

x=668x=668 で分割する or y=2y=2 で分割する,いずれにせよ計算はそんなに楽にはなりません。やってみてください。

読み方は「かくしてん」ではなく「こうしてん」です。