[ 掲示板に戻る ]
記事No.70253に関するスレッドです
★ 証明 / しんや
質問です。nを自然数とする。平面上の2n個の点を2個ずつ組にして、n個の組を作り、組となった2点を両端とするn本の線分をつくる。このときどのような配置の2n個の点に対してもn本の線分が互いに交わらないようなn個の組を作ることが出来ることを示しなさい。
この問題の自分の答えと解答が違っていましたので僕の答えは証明になっているのか教えて欲しいです。
No.70253 - 2020/10/17(Sat) 00:38:33
☆ Re: 証明 / らすかる
「多角形ができるように線分で結ぶことができる」は
今回の証明と似たようなことですから、証明が必要です。
よって証明になっているとは言えません。
No.70254 - 2020/10/17(Sat) 01:03:55
☆ Re: 証明 / URHANL
しんやさんがご覧になった模範回答はどのようなものだったのでしょうか。興味があります。

ところでこれから下に書く方法は、とある書籍に出ていたもっと難しい問題からヒントを得て、簡略化したものです。

2n個の点がある平面に座標軸(x軸y軸)をおきます。

各点に対して、x座標の値が小さい順に番号 i をつけます。ただし、x座標の値が同一の点が複数あった場合には、それらの点のy座標の値が小さい順に番号 i を振ります。
こうして番号を振られた点を P_i (1≦i≦2n)と表記します。

n 本の線分を以下のようにつくります。

P_1 と P_2 とを結んだ線分をつくります。

P_3 と P_4 とを結んだ線分をつくります。

P_5 と P_6 とを結んだ線分をつくります。

同様にして あわせて n 本の線分をつくります。

これらの線分は互いに交わりません。
No.70316 - 2020/10/18(Sun) 22:04:37
☆ Re: 証明 / URHANL
参考にした書籍は以下です。

●アルゴリズムパズル
――プログラマのための数学パズル入門
Anany Levitin、Maria Levitin　著、黒川 洋、松崎 公紀　訳 オライリー・ジャパン発行

参考にした問題は以下です。

平面上に2000個の点が存在する。どの3点も同一直線上にないものとする。これらの点のどれかを頂点とする八角形を250個作成するアルゴリズムを考案せよ。これらの八角形は各辺が自身と交差せず、どの２つの八角形も頂点を共有してはならない。
No.70318 - 2020/10/18(Sun) 22:20:35
☆ Re: 証明 / URHANL
出典：2007 年 名古屋大学なのでしたか。

[PDF] 図チャレ 第67回 (2007年4月) - 早稲田数学フォーラム
wasmath.la.coocan.jp/zukei067.pdf
No.70530 - 2020/10/28(Wed) 23:16:08