格子点の個数を数える問題のいろいろな解法
格子点とは,座標平面(or 座標空間)において,各成分が全て整数であるような点のこと。
例えば などは格子点ですが, などは格子点ではありません。
格子点の個数を数える問題
座標軸に平行な直線で切る
長方形の半分とみなす
格子点の個数を数える問題
「特定の領域に含まれる格子点の数」を数える問題は頻出です。
今回は2008年名古屋大学の問題を考えます。
を満たす 以上の整数の組 の個数を求めよ。
いろいろな方法で数えることができます!
- を固定
- を固定→今回は を固定したほうが楽
- を固定→もっとめんどう
- 長方形の半分
- ピックの定理→頂点が格子点でないのであまり楽にならない
1と4を詳しく解説します。
座標軸に平行な直線で切る
まず を固定して 上に格子点が何個あるか数え,それを足し上げます。
と固定した部分で領域内にある格子点の数は,
を満たす整数 の数と等しい。これは,
- が偶数のとき, 個
- が奇数のとき, 個
よって,求める格子点の数は
コメント: を固定しても同様にできますが,分母に が登場してしまい,3つに場合分けする必要があるのでややめんどうです。
また, を固定(斜めに切る)してもできますが,6つに場合分けする必要があるのでもっとめんどうです。
長方形の半分とみなす
「長方形領域なら格子点の数は簡単に数えられる」ことを用います。対角線部分に注意する必要があります。
-
と を結ぶ線分を対角線とする長方形上(周も含む)にある格子点の数は,
-
線分 上にある格子点の数は, 以上 以下の偶数の数と等しいので
よって,数えたい格子点のうち, を満たす格子点の数は,
「対角線上にない格子点の数」+ 「対角線上にある格子点の数」
最後に 上にある格子点の数( 個)と 上にある格子点の数( 個)を足し合わせると,
コメント:格子点の数を数える裏技としてピックの定理がありますが,ピックの定理は領域の各頂点が格子点でないと使えません(今回は が頂点になっている)。それでも強引に使おうとすると「領域を二つに分割して,大きい方をピックの定理で求めて,小さい方は直接数える」という方法になります。
で分割する or で分割する,いずれにせよ上記の解答と手間はほとんど変わりません。
読み方は「かくしてん」ではなく「こうしてん」です。