1. 高校数学の美しい物語
  2. 格子点の個数を数える問題のいろんな解法

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

更新日時 2021/03/07

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

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

目次
  • 格子点の個数を数える問題

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

  • 長方形の半分とみなす

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

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

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

問題

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

いろいろな方法で数えます!

1と4を詳しく解説します。

1. xx を固定

2. yy を固定→今回は xx を固定したほうが楽

3. 3x+2y3x+2y を固定→もっとめんどくさい

4.長方形の半分

5.ピックの定理→頂点が格子点でないのであまり楽にならない

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

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

解答

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

0y100432a0\leq y\leq 1004-\dfrac{3}{2}a を満たす整数 yy の数と等しい。これは,

格子点の数を数える

  • aa が偶数のとき,N(a)=100432a+1N(a)=1004-\dfrac{3}{2}a+1
  • aa が奇数のとき,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

コメント: yy を固定しても同様にできますが,分母に 33 が登場してしまい,3つに場合分けする必要があるのでややめんどうです。

また,3x+2y3x+2y を固定(斜めに切る)してもできますが,6つに場合分けする必要があるのでもっとめんどうです。

長方形の半分とみなす

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

解答

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

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

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

x=668x=668 で分割する or y=2y=2 で分割する,いずれにせよ上記の解答と手間はほとんど変わりません。

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

人気記事
  1. 高校数学の美しい物語
  2. 格子点の個数を数える問題のいろんな解法