MathLabs

第5問

平面上に nn 本の線分があり、どの3本も一点で交わらず、どの2本もそれぞれの内部でちょうど1回交わっている。Tony と 2n−12n-1 人の友人は、それぞれ異なる線分の端点に立っている。Tony は次のようにして友人たちにクリスマスプレゼントを送りたい。まず、各線分の一方の端点を「シンク」として選ぶ。次に、自分が立っている端点にプレゼントを置く。プレゼントは次のように動く：線分上にあるときはその線分のシンクに向かって進み、2本の線分の交点に達すると乗っている線分を乗り換えて新しい線分のシンクに向かって進み始める。プレゼントがある端点に到達すると、その端点にいる友人がプレゼントを受け取れる。Tony は 2n−12n-1 人の友人のうちちょうど nn 人にプレゼントを送れることを示せ。
ステップ 2/3: プレゼントを受け取れるのは高々 n 個の偶数頂点
前のステップ次のステップ
2-color regions red (clockwise) / blue (anticlockwise) ⟹ boundary directions alternate: odd outgoing, even incoming\text{2-color regions red (clockwise) / blue (anticlockwise)}\ \Longrightarrow\ \text{boundary directions alternate: odd outgoing, even incoming}
詳しい解説

nn 本の弦で分けられた円内の領域を赤と青に2彩色し、隣り合う領域が異なる色になるようにし、頂点 11 に接する二つの領域は 11 から見て右側を赤、左側を青とする。各赤領域の境界を時計回り、各青領域の境界を反時計回りに向きづけると、赤と青の領域を隔てる各弦の区間は両側から同じ向きを受ける。11 から出発したプレゼントは隣接する二領域の向きに従って弦上を進み、交点に達するたびに交差する弦へ乗り換えるがその二領域の一方に接し続けるため、常に領域の向きに沿って進む。外周の円に沿っては領域の色が交互に並ぶので、頂点 1,2,…,2n1,2,\ldots,2n における弦の向きは奇数頂点で出発方向、偶数頂点で到着方向と交互になる。したがって 11 からのプレゼントが到達できるのは nn 個の偶数頂点 2,4,…,2n2,4,\ldots,2n に限られる。