2015/05/05

格子点の個数を数える問題のいろいろな解法

分野: 整数問題  レベル: 最難関大学

格子点:座標平面(or 座標空間)において,各成分が全て整数であるような点。


例えば$(0,0),(1,3),(-3,0)$ などは格子点ですが,$(-0.5,2)$ などは格子点ではありません。

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

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

今回解説するのは2008年名古屋大学の問題です。

問題

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

いろいろな方法で数えます!
1と4を詳しく解説します。

1. $x$ を固定
2. $y$ を固定→今回は $x$ を固定したほうが楽
3. $3x+2y$ を固定→もっとめんどくさい
4.長方形の半分
5.ピックの定理→頂点が格子点でないのであまり楽にならない

座標軸に平行な直線で切る

方針:まず $x$ を固定して,$x=a$ 上に格子点が何個あるか数え,それを足し上げます。

解答

$x=a$ と固定した部分で領域内にある格子点の数は,
$0\leq y\leq 1004-\dfrac{3}{2}a$ を満たす整数 $y$ の数と等しい。これは,

格子点の数を数える
  • $a$ が偶数のとき,$N(a)=1004-\dfrac{3}{2}a+1$ 個
  • $a$ が奇数のとき,$N(a)=1004-\dfrac{3}{2}a-\dfrac{1}{2}+1$ 個

よって,求める格子点の数は
$N=\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$


コメント:$y$ を固定しても同様にできますが,分母に $3$ が登場してしまい,3つに場合分けする必要があるのでややめんどくさいです。
また,$3x+2y$ を固定(斜めに切る)してもできますが,6つに場合分けする必要があるのでもっとめんどくさいです。

長方形の半分とみなす

方針:長方形領域なら格子点の数は簡単に数えれることを用います。対角線部分に注意する必要があります。

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

解答

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

・線分 $AB$ 上にある格子点の数は,$0$ 以上 $668$ 以下の偶数の数と等しいので $335$
よって,数えたい格子点のうち,$y\geq 2$ を満たす格子点の数は,
$\dfrac{1}{2}(671007-335)+335=335671$

・最後に $y=1$ 上にある格子点の数($669$ 個)と $y=0$ 上にある格子点の数($670$ 個)を足し合わせると,
$335671+669+670=337010$


コメント:格子点の数を数える裏技としてピックの定理がありますが,ピックの定理は領域の各頂点が格子点じゃないと使えません(今回は$(\frac{2008}{3},0)$ が頂点になっている)。それでも強引に使おうとすると「領域を二つに分割して,大きい方をピックの定理で求めて,小さい方は直接数える」という方法になります。
$x=668$ で分割する or $y=2$ で分割する,いずれにせよ上記の解答と手間はほとんど変わりません。

読み方は「かくしてん」ではなく「こうしてん」です。
分野: 整数問題  レベル: 最難関大学