|
uchinyan |
|
#26194の問題
＞問題 平面上に点を100個とります。片側に50個の点があるような ＞直線を引くことができることを示せ。 昨夜、一応考えてみたのですが、どうもうまい方法が思いつかず、他の方に譲ろうと思ったものの、 どなたも書き込まないようなので、一応、拙い、泥臭い、証明を。見落としがあるかもしれません (^^; まず、平面に適当な直交座標系を導入し、各点に座標を与えます。 その座標で y 座標の値が一番大きいものから順番に、y 座標の値が等しい場合には x 座標の値が小さいものから順番に、 点に番号を振っていき、50 番目の点を P(p,q)、51番目の点を A(x0,y0) とします。 もし、q > y0 ならば、q > c > y0 となる c をとってきて、y = c とすれば、この直線が題意を満たします。 しかし、番号の与え方から、q < y0 はありえませんが、q = y0 は可能です。このときは次のようにします。 点 A と、1 番目、...、50 番目の点とを結んだ直線の傾きを計算し、傾きに正の値があればそれらの最小のものを a1 とし、 正の値がなければ a1 = 1 とします。 同様に、点 A と、52 番目、...、100 番目の点とを結んだ直線の傾きを計算し、傾きに正の値があればそれらの最小のものを a2 とし、 正の値がなければ a2 = 1 とします。 そして、a1, a2 のどちらよりも小さな正の値 a をとってきて、直線 y = a * (x - x0) + y0 をつくります。 これが、(両側ではなくて)「片側に50個の点がある」という題意を満たします。 すなわち、1 番目、...、50 番目の点 (x,y) に対しては、y >= y0 なので、 x > x0 ならば、番号の振り方から、y > y0 で、(y - y0)/(x - x0) > a より、y > a * (x - x0) + y0 x = x0 ならば、明らかに、y > y0 = a * (x - x0) + y0 x < x0 ならば、一般に y >= y0 ですが、a > 0 >= (y - y0)/(x - x0) より、y > a * (x - x0) + y0 となり、1 番目 〜 50 番目のすべての点は、直線 y = a * (x - x0) + y0 より上にあります。 また、52 番目、...、100 番目の点 (x,y) に対しては、y <= y0 なので、 x > x0 ならば、一般に y <= y0 ですが、a > 0 >= (y - y0)/(x - x0) より、y < a * (x - x0) + y0 x = x0 ならば、明らかに、y < y0 = a * (x - x0) + y0 x < x0 ならば、番号の振り方から、y < y0 で、a > (y - y0)/(x - x0) より、y < a * (x - x0) + y0 となり、52 番目 〜 100 番目のすべての点は、直線 y = a * (x - x0) + y0 より下にあります。 なお、51 番目は、直線 y = a * (x - x0) + y0 にのっています。 これが気持ち悪い、又は、問題が「直線の両側に 50 個ずつの点がある」の場合でも、1 番目 〜 50 番目のすべての点の y 座標と、 直線 y = a * (x - x0) + y0 で x を 1 番目 〜 50 番目の点の x 座標に一致させたときの y の値との 50 組を比較して、 その「差」の最小を ymin とすると、ymin は 0 ではないので、0 < b < ymin となる b をとることができまず。 そこで、直線 y = a * (x - x0) + (y0 + b) とすれば、51 番目の点はこの直線の下にきて、他は変わらないので、 「直線の両側に 50 個ずつの点がある」の場合でも大丈夫です。 なお、この証明は、非常にナイーブで拙い方法ですが、50 とか 100 とかには依存しません。 したがって、今の証明をそのまま拡張して、一般に、 ・平面上に点を n 個とり、片側に m 個の点があるような直線を引くことができる。 ・平面上に点を 2n 個とり、両側に n 個ずつの点があるような直線を引くことができる。 など、がいえるものと思います。 |
|
ネコの住む家
11月23日（水） 13:46:43
MAIL:uchi@sco.bekkoame.ne.jp 26195 |