格子点の問題。可能な限り易しく教えて下さい。

「x,y平面上で、ｘ座標とｙ座標がともに整数であるような点（ｍ、ｎ）を格子点とよぶ。

各格子点を中心として半径ｒの円が描かれており、傾き２/５の任意の直線は、これらの円のどれかと共有点をもつとする。このような性質をもつ半径ｒの最小値を求めよ。」

東大の過去問です。馬鹿な私にもわかるように詳しくご教授ください。

No.2 ベストアンサー 回答者： stomachman 回答日時： 2013/09/24 03:01

　「半径ｒの最小値を求めよ」と書いてあるせいで混乱しちゃいそうですけど、「このような性質」を持たない、という条件を考えてみれば、問いが求めているのは結局の所「『直線と、任意の格子点との距離』の最小値」の（bを動かしたときの）最大値。

まずこれが分からんとアキマセン。

　あとは、とりあえずグラフを描いてみれば、答だけならスグ出るんじゃないでしょうか。

　以下は図を描けば直ちにわかることを、わざとヤヤコシく言い直しているだけ：

　記号を用意する。直線の方程式を
　　y=f(x,b)
　　f(x,b) = (2/5)x + b
とする。格子点(m,n)と直線y=f(x,b)の距離D(b,m,n)は
　　tanθ = 2/5
　　α = cos(|θ|)
　　H(b,m,n) = | f(m,b)-n |
と書くと
　　D(b,m,n) = α H(b,m,n)
である(上の図）。

　そして「『直線と格子点の距離』の最小値」
　　d(b) = min{ D(b,m,n) | m∈Z, n∈Z}　(Zは整数）
の最大値
　　r = max{ d(b) | b∈R }　(Rは実数）
を計算したい。

　bの範囲を絞ります。任意のx,b,m,nについて
　　D(b,m,n) = D(b+2/5, m+1, n)
より
　　d(b) = d(b+2/5)
だから
　　r = max{ d(b) | -1/5≦b＜1/5 }
さらに
　　D(b,m,n)=D(-b,-m,-n)
つまり
　　d(b) = d(-b)
なので、
　　r = max{ d(b) | 0≦b≦1/5 }
要するに、0≦b≦1/5についてだけ調べれば良い。

　次にmの範囲を絞ります。任意のx,b,m,nについて
　　D(b,m,n)=D(b,m+5,n+2)
なので、
　　d(b) = min{ D(b,m,n) | 0≦m＜5, n∈Z}
つまり、m∈{0,1,2,3,4}だけ調べれば良い。

　最終的に、(m,n)の範囲を絞ります。
　　s(m,b) = min{ H(b,m,n) | n∈Z}
と書く事にすると、任意のbについて
　　0≦b≦1/5 ⇒ d(b)= α min{ s(m,b) | 0≦m＜5}
である。そして、0≦b≦1/5のとき、（下の図）
　　s(0,b) = H(b,0,0) ≦1/5
　　s(1,b) = min{H(b,1,0), H(b,1,1)} ≧1/5
　　s(2,b) = H(b,2,1) ≦1/5
　　s(3,b) = H(b,3,1) ≧1/5
　　s(4,b) = H(b,4,2) ≧1/5
要するに、(m,n)∈{(0,0),(2,1)} (●)以外(○)は関係ない。
　で、
　　r = α max{ min{s(0,b), s(2,b)} | 0≦b≦1/5}

この回答へのお礼

回答ありがとうございます＞＜

お礼日時：2013/09/24 13:56

No.1 回答者： naniwacchi 回答日時： 2013/09/23 16:05

こんにちわ。

「だだっ広く」考えてしまうと切りがないので、うまく絞り込みます。
うまくというほどでもないのですが、
・まず、円は格子点を中心に同じ半径で規則正しく並んでいます。
　つまり、円は周期性をもって並んでいることになります。その周期は 1です。
・動くのは、傾き 2/5の直線の y切片だけです。

ということから、
直線が y＝ 2x/5から y＝ 2x/5+ 1の間を動くときを考えればよいことがわかります。
式で書けば、y＝ 2x/5+ L、0≦ L≦ 1ということです。
（見づらいので、ここでは Lを大文字で表現します。）

直線が動いていくと、直線からもっとも「遠い」格子点が変わっていきます。
そして、直線：y＝ 2x/5+ Lが半径：rの円に「接する」ときがどうなるかを考えます。
その中で最大となる半径が答えになります。

この回答へのお礼

回答ありがとうございます＞＜

お礼日時：2013/09/23 16:38