格子点の個数の求め方

重要度 難易度

こんにちは、リンス(@Lins016)です。
今回は格子点の個数の求め方について学習していこう。

スポンサードリンク

格子点と数列

格子点とは「座標平面(空間座標)上の各成分(\(\small{ \ x \ }\)座標、\(\small{ \ y \ }\)座標、\(\small{ \ z\ }\)座標)が整数である点」のこと。

今回はある条件の中に含まれる格子点の数を求めるのに数列の和記号\(\small{ \ \displaystyle\sum \ }\)を利用する方法について勉強していこう。

格子点の個数の求め方

条件を満たす\(\small{ \ x=k \ }\)上の格子点の個数を\(\small{ \ a_k \ }\)とするとき
ただし\(\small{ \ 0\leqq k \leqq n \ }\)で、
\(\small{ \ k \ }\)は整数とすると
\(\small{ \ \displaystyle \sum_{ k=0 }^{ n }a_k \ }\)

格子点の個数の求め方-01

格子点の求め方の基本

格子点の求め方は、「\(\small{ \ x=k \ }\)または\(\small{ \ y=k \ }\)上の条件を満たす格子点の個数を求め、それを\(\small{ \ k=0 \ }\)(場合によっては\(\small{ \ k=0 \ }\)じゃないときもある)から足し合わせていく」ことで求めることができるんだ。

例題を確認
問題解答

\(\small{ \ x\geqq0, \ y\geqq0, \ x+y\leqq10 \ }\)を満たす整数\(\small{ \ x, \ y \ }\)の組の総数を求めよ。

\(\small{ \ x=k \ }\)と\(\small{ \ x+y=10 \ }\)の交点の\(\small{ \ y \ }\)座標は\(\small{ \ y=10-k \ }\)
つまり\(\small{ \ x=k \ }\)上の格子点は
\(\small{ \ 10-k+1=11-k \ }\)個ある
また\(\small{ \ y\geqq0 \ }\)から\(\small{ \ k=0, \ 1, \ 2\cdots,10 \ }\)
よって求める格子点の数は
\(\small{ \ \displaystyle \sum_{ k=0 }^{ 10 }(11-k)\\
=11+ \displaystyle \sum_{ k=1 }^{ 10 }(11-k)\\
=11+110-\displaystyle\frac{1}{2}\cdot10\cdot11\\
=66 \ }\)

格子点の個数の求め方-01

point
\(\small{ \ \displaystyle \sum_{ k=0 }^{ n }a_k=a_0+a_1+\cdots+a_n \ }\)だから\(\small{ \ \displaystyle \sum_{ k=0 }^{ n }a_k=a_0+\displaystyle \sum_{ k=1 }^{ n }a_k \ }\)に変形して計算しよう。
だってシグマの公式は\(\small{ \ k=1 \ }\)からの和になってるからね。

もちろん\(\small{ \ k=0 \ }\)から直接計算する方法もあるから計算できるなら計算してもいいけど、項数を\(\small{ \ n+1 \ }\)にしたりしないといけないから逆にミスする人もいるからね。

\(\small{ \ x=k \ }\)上の格子点の数は\(\small{ \ x \ }\)軸上の点まで含むから、\(\small{ \ x=k \ }\)と\(\small{ \ x+y=10 \ }\)の交点の\(\small{ \ y \ }\)座標に\(\small{ \ 1 \ }\)加えた数になるから注意しよう。

問題によっては\(\small{ \ x+y\lt 10 \ }\)のように直線上の点は含まない場合もあるからね。

格子点の数え方と場合分け

上の例題では\(\small{ \ x=k \ }\)上の格子点を求めて、\(\small{ \ k=0 \ }\)から\(\small{ \ k=10 \ }\)まで足したよね。
これは\(\small{ \ x=0 \ }\)上の格子点から\(\small{ \ x=10 \ }\)の格子点までを順に加えたことになる。
つまり格子点の数を縦に数えたことになるんだ。

これに対して\(\small{ \ y=k \ }\)上の格子点を求めて、それを足し合わせると格子点の数を横に数えることになるんだ。

もちろんどっちで数えても同じ数になるんだけど、問題によっては計算が複雑になる場合がある。

例えば\(\small{ \ x\geqq0, \ y\geqq0, \ x+y\leqq10 \ }\)は縦で数えても、横で数えても同じなんだけど、
\(\small{ \ x\geqq0, \ y\geqq0, \ x+2y\leqq10 \ }\)は縦で数えてるよりも横で数えたほうが簡単なんだ。

それじゃこの\(\small{ \ x\geqq0, \ y\geqq0, \ x+2y\leqq10 \ }\)を縦にも横にも数え上げて計算してみよう。

まずはさっきと同じように縦に数えてみよう。

\(\small{ \ x=k \ }\)と\(\small{ \ x+2y=10 \ }\)の交点の\(\small{ \ y \ }\)座標は\(\small{ \ k+2y=10 \ }\)から\(\small{ \ y=\displaystyle\frac{10-k}{2} \ }\)になるよね。

ってことは、この交点は\(\small{ \ k \ }\)が偶数の場合は格子点になるけど、奇数の場合は格子点にならないよね。

格子点の個数の求め方-02

これは図を見ても確認できるよね。だから偶数と奇数の場合に分けて格子点を数え上げる必要があるんだ。

(i)\(\small{ \ k=2m \ }\)のとき
\(\small{ \ y=\displaystyle\frac{10-2m}{2}=5-m \ }\)
\(\small{ \ k\geqq0, \ y\geqq0 \ }\)より\(\small{ \ m=0, \ 1,\cdots,5 \ }\)
\(\small{ \ x=k \ }\)上の格子点の数は
\(\small{ \ 5-m+1=6-m \ }\)個

(ii)\(\small{ \ k=2m-1 \ }\)のとき
\(\small{ \ y=\displaystyle\frac{10-2m+1}{2}=\displaystyle\frac{11}{2}-m \ }\)
\(\small{ \ k\geqq0, \ y\geqq0 \ }\)より\(\small{ \ m=1, \ 2,\cdots,5 \ }\)
\(\small{ \ x=k \ }\)上の格子点の数は
\(\small{ \ 5-m+1=6-m \ }\)個

つまり求める格子点の個数は(i)(ii)より
\(\small{ \ \displaystyle \sum_{ m=0 }^{ 5 }(6-m)+\displaystyle \sum_{ m=1 }^{ 5 }(6-m)\\
=6+2\displaystyle \sum_{ m=1 }^{ 5 }(6-m)\\
=6+2\left(30-\displaystyle\frac{1}{2}\cdot5\cdot6\right)\\
=36 \ }\)

次に横に数えてみよう。

\(\small{ \ y=k \ }\)と\(\small{ \ x+2y=10 \ }\)の交点の\(\small{ \ x \ }\)座標は
\(\small{ \ x=10-2k \ }\)になるよね。

ってことは\(\small{ \ x \ }\)は常に整数になるから場合分けする必要がないんだ。

だから\(\small{ \ y=k \ }\)上の格子点の個数は\(\small{ \ 10-2k+1=11-2k \ }\)個になるんだ。

また\(\small{ \ x\geqq0, \ y\geqq0 \ }\)から\(\small{ \ k=0, \ 1,\cdots,5 \ }\)

格子点の個数の求め方-03

だから求める格子点の数は
\(\small{ \ \displaystyle \sum_{ k=0 }^{ 5 }(11-2k)\\
=11+\displaystyle \sum_{ k=1 }^{ 5 }(11-2k)\\
=11+11\cdot5-2\cdot\displaystyle\frac{1}{2}\cdot5\cdot6\\
=11+55-30\\
=36 \ }\)
この問題の場合、横に数えることで場合分けが必要なかったよね。

問題によっては縦横のどっちを考えても場合分けが必要になる問題もあるけど、なるべく場合分けが少ない方を選んで計算しよう。

例題を確認
問題解答

\(\small{ \ 3x+2y\leqq2008 \ }\)を満たす\(\small{ \ 0 \ }\)以上の整数の組\(\small{ \ (x, \ y) \ }\)の個数を求めよ。

\(\small{ \ x=k \ }\)と\(\small{ \ 3x+2y=2008 \ }\)との交点の座標は
\(\small{ \ y=1004-\displaystyle\frac{3}{2}k \ }\)
\(\small{ \ y\geqq0 \ }\)より\(\small{ \ 0\leqq k \leqq 669+\displaystyle\frac{1}{3} \ }\)
よって直線\(\small{ \ x=k \ }\)上の格子点の個数は
(i)\(\small{ \ k=2m \ (m=0, \ 1, \ ,\cdots,334) \ }\)のとき
\(\small{ \ y=1004-\displaystyle\frac{3}{2}\cdot 2m=1004-3m \ }\)
よって格子点の個数は\(\small{ \ 1005-3m \ }\)個
(ii))\(\small{ \ k=2m+1 \ (m=0, \ 1, \ ,\cdots,334) \ }\)のとき
\(\small{ \ 1004-\displaystyle\frac{3}{2}\cdot(2m+1)=1002.5-3m \ }\)
よって格子点の個数は\(\small{ \ 1003-3m \ }\)個
(i)(ii)より求める個数は
\(\small{ \ \displaystyle \sum_{ m=0 }^{ 334 }(1005-3m)+\displaystyle \sum_{ m=0 }^{ 334 }(1003-3m)\\
=\displaystyle \sum_{ m=0 }^{ 334 }\left\{(1005-3m)+(1003-3m)\right\}\\
=\displaystyle \sum_{ m=0 }^{ 334 }(2008-6m)\\
=2008+\displaystyle \sum_{ m=1 }^{ 334 }(2008-6m)\\
=2008+334\cdot2008-6\cdot\displaystyle\frac{1}{2}\cdot334\cdot335\\
=337010 \ }\)

point
この問題の場合は縦に数えると偶奇の二つの場合分けだけど、横に数えると\(\small{ \ 3 \ }\)で割った余りの三つの場合分けになるから縦に数えたほうが楽だから縦で数えてあるんだ。

偶奇の場合分けの場合、奇数を\(\small{ \ k=2m+1 \ }\)っておけば\(\small{ \ m=0, \ 1,\cdots,334 \ }\)になるし、\(\small{ \ k=2m-1 \ }\)っておけば\(\small{ \ m=1, \ 2,\cdots,335 \ }\)になる。

この問題の場合、偶数と奇数のそれぞれの和を\(\small{ \ m=0 \ }\)から\(\small{ \ m=334 \ }\)に合わせて計算したほうが楽だから、奇数を\(\small{ \ k=2m+1 \ }\)にしてるけど、\(\small{ \ k=2m-1 \ }\)っておいて別々に計算しても問題ないからね。

それじゃあ次は入試レベルの問題にチャレンジしてみよう。
入試レベルにチャレンジ
問題解答

\(\small{ \ n \ }\)を自然数とする。
不等式\(\small{ \ y\leqq 2n^2, \ y=\displaystyle\frac{1}{2}x^2, \ x\geqq0 \ }\)を同時に満たす整数の組(\(\small{ \ x, \ y \ }\))の個数を求めよ。

\(\small{ \ y=2n^2 \ }\)と\(\small{ \ y=\displaystyle\frac{1}{2}x^2 \ }\)の交点の\(\small{ \ x \ }\)座標は
\(\small{ \ 2n^2=\displaystyle\frac{1}{2}x^2 \ }\)より\(\small{ \ x=2n \ }\)
格子点の個数の求め方-04
直線\(\small{ \ x=k \ (0\leqq k \leqq 2n) \ }\)上の格子点の個数は
(i)\(\small{ \ k=2m \ (0\leqq m \leqq n, \ }\)ただし\(\small{ \ m \ }\)は整数)のとき
\(\small{\begin{eqnarray} y&=&2n^2-\displaystyle\frac{1}{2}\left(2m\right)^2\\
&=&2n^2-2m^2 \ \end{eqnarray}}\)
よって格子点の個数は\(\small{ \ 2n^2-2m^2+1 \ }\)
(ii)\(\small{ \ k=2m-1 \ (1\leqq m \leqq n, \ }\)ただし\(\small{ \ m \ }\)は整数)のとき
\(\small{\begin{eqnarray} \ y&=&2n^2-\displaystyle\frac{1}{2}\left(2m-1\right)^2\\
&=&2n^2-2m^2+2m-\displaystyle\frac{1}{2} \ \end{eqnarray}}\)
よって格子点の個数は\(\small{ \ 2n^2-2m^2+2m \ }\)
(i)(ii)より求める格子点の数は

\(\small{ \ \displaystyle \sum_{ m=0 }^{ n }(2n^2-2m^2+1)+\displaystyle \sum_{ m=1 }^{ n }(2n^2-2m^2+2m)\\
=2n^2+1+\displaystyle \sum_{ m=1 }^{ n }(2n^2-2m^2+1)+\displaystyle \sum_{ m=1 }^{ n }(2n^2-2m^2+2m)\\
=2n^2+1+2n^3-2\cdot\displaystyle\frac{1}{6}n(n+1)(2n+1)+n+2n^3-2\cdot\displaystyle\frac{1}{6}n(n+1)(2n+1)+2\cdot\displaystyle\frac{1}{2}n(n+1)\\
=\displaystyle\frac{8}{3}n^3+n^2+\displaystyle\frac{4}{3}n+1\ }\)

point
\(\small{ \ x=k \ }\)と\(\small{ \ y=\displaystyle\frac{1}{2}x^2 \ }\)の交点の\(\small{ \ y \ }\)座標は\(\small{ \ y=\displaystyle\frac{k^2}{2} \ }\)だから\(\small{ \ k \ }\)が偶数の場合は整数になるけど奇数の場合は整数にならないから格子点にならないよね。

\(\small{ \ y=k \ }\)と\(\small{ \ y=\displaystyle\frac{1}{2}x^2 \ }\)の交点の\(\small{ \ x \ }\)座標は\(\small{ \ x=\sqrt{2k} \ }\)だから\(\small{ \ x=\sqrt{2k} \ }\)が整数になる場合とならない場合に場合分けしないといけないんだけど、これは難しいよね。

だから\(\small{ \ x=k \ }\)上の格子点を数えていくことになるんだ。

Point 格子点の個数の求め方

①\(\small{ \ x=k \ }\)または\(\small{ \ y=k \ }\)上の格子点の個数を求める
②\(\small{ \ k \ }\)の範囲に注意して格子点の和を求める

この記事が気に入ったら
いいね ! しよう

Twitter で

  数列

  , ,