格子点

質問

x,y,zを整数とするとき、xy平面上の点(x,y)を2次元格子点,
xyz空間内の点(x,y,z)を3次元格子点という。また、m,nを0以上の整数とする。
(1)x≧0,y≧0かつ(1/3)x+(1/5)y≦mを満たす2次元格子点(x,y)の
総数を求めよ。
(2)x≧0,y≧0,z≧0かつ(1/3)x+(1/5)y+z≦nを満たす3次元格子点
(x,y,z)の総数を求めよ。

という問題でわからないところがあるので教えてください。

まず(1)では、長方形を作ってそこから格子点の数を求めようしました。すると、(1/3)x+(1/5)y≦mがx軸と交わるのは(3m,0)で
y軸と交わるのは(0,5m)となりました。
4点(0,0),(3m,0),(3m,5m),(0,5m)を頂点とする長方形上の格子点の
個数は(3m+1)(5m+1)
ここから分からないんですが、(1/3)x+(1/5)y=m(0≦x≦3m)上の格子点の個数はどのように求めればいいんでしょうか？
y=0のときは(3m,0)なりますがy=1のときは分数になり格子点には
数えられません。代入していくとy=5のとき(3m,5)となりました…
これはnを用いてどのように表すことができますか？

また、(2)は上の方法が使えないので困っています。
どなたか教えてくださるとうれしいです。

説明下手ですみません＞＜
ではよろしくおねがいします!

回答No.1

stomachman · ベストアンサー

もし(1)が解けたとしますと、(2)は
　　(1/3)x+(1/5)y≦m ただし m = n-z
と読み替えれば、(1)に帰着します。つまり、zが0,1,2,…の場合の(1)の答の和を計算すれば良い。

さて、(1)は
　　(1/3)x≦c/5 ただし　c = 5m-y
と読み替えれば…

回答No.2

Ishiwara

とても良いところまで行っていますね。あと一息です。
ヨコに（５ｍ＋１）個、タテに（３ｍ＋１）個の長方形は、そのとおりです。この格子点の総数（５ｍ＋１）×（３ｍ＋１）のうちの「約半数」が「合格」です。「約」とは「２で割る前に無条件合格とすべきものがある」という意味です。この無条件合格格子点は、左上から右下にかけた対角線の上にある（５ｍと３ｍの最大公約数）＋１個の点です。
ですから（（総数）＋（無条件合格数））を２で割れば、求める答が出ます。
３次元格子の場合には、「対角線」が「切断面」になりますが、幸いｚの係数が１のため、最大公約数の処理が非常にラクで、まったく類似の方法で解けます。