第5問

平面上に

n

本の線分があり、どの3本も一点で交わらず、どの2本もそれぞれの内部でちょうど1回交わっている。Tony と

2n-1

人の友人は、それぞれ異なる線分の端点に立っている。Tony は次のようにして友人たちにクリスマスプレゼントを送りたい。まず、各線分の一方の端点を「シンク」として選ぶ。次に、自分が立っている端点にプレゼントを置く。プレゼントは次のように動く：線分上にあるときはその線分のシンクに向かって進み、2本の線分の交点に達すると乗っている線分を乗り換えて新しい線分のシンクに向かって進み始める。プレゼントがある端点に到達すると、その端点にいる友人がプレゼントを受け取れる。Tony は

2n-1

人の友人のうちちょうど

n

人にプレゼントを送れることを示せ。

ステップ 1/3: 円の弦モデルと対蹠頂点の組

前のステップ次のステップ

\text{Vertices }1,\ldots,2n\text{ on a circle (Tony at }1\text{)};\quad\text{each chord connects }k\text{ and }k+n\pmod{2n}

詳しい解説

$\binom{n}{2}$ 個の内部交点をすべて囲む大きな円をとり、 $n$ 本の線分をこの円の弦に延長して、Tony のいる点 $1$ から反時計回りに $2n$ 個の端点を $1,2,\ldots,2n$ と番号づける。どの2本の弦も円内で交わるので、各弦の両側にはそれぞれ $n-1$ 個の端点があり、したがって各弦は $k$ と $k+n$ （ $1\le k\le n$ ）を結ぶ。