電子書籍の厳選無料作品が豊富!

「x,y平面上で、x座標とy座標がともに整数であるような点(m、n)を格子点とよぶ。

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

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

A 回答 (2件)

 「半径rの最小値を求めよ」と書いてあるせいで混乱しちゃいそうですけど、「このような性質」を持たない、という条件を考えてみれば、問いが求めているのは結局の所「『直線と、任意の格子点との距離』の最小値」の(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}
「 格子点の問題。可能な限り易しく教えて下」の回答画像2
    • good
    • 0
この回答へのお礼

回答ありがとうございます><

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

こんにちわ。



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

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

直線が動いていくと、直線からもっとも「遠い」格子点が変わっていきます。
そして、直線:y= 2x/5+ Lが半径:rの円に「接する」ときがどうなるかを考えます。
その中で最大となる半径が答えになります。
「 格子点の問題。可能な限り易しく教えて下」の回答画像1
    • good
    • 0
この回答へのお礼

回答ありがとうございます><

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!