MathLabs

第5問

平面上に nn 本の線分があり、どの3本も一点で交わらず、どの2本もそれぞれの内部でちょうど1回交わっている。Tony と 2n−12n-1 人の友人は、それぞれ異なる線分の端点に立っている。Tony は次のようにして友人たちにクリスマスプレゼントを送りたい。まず、各線分の一方の端点を「シンク」として選ぶ。次に、自分が立っている端点にプレゼントを置く。プレゼントは次のように動く：線分上にあるときはその線分のシンクに向かって進み、2本の線分の交点に達すると乗っている線分を乗り換えて新しい線分のシンクに向かって進み始める。プレゼントがある端点に到達すると、その端点にいる友人がプレゼントを受け取れる。Tony は 2n−12n-1 人の友人のうちちょうど nn 人にプレゼントを送れることを示せ。
ステップ 3/3: 帰納的なシンクの選び方で各偶数頂点 2k に到達する
前のステップ次のステップ
For 1≤k≤n, set sinks {k+1,…,k+n}:source k−i ⟶ sink k+i+1(mod2n)\text{For }1\le k\le n,\text{ set sinks }\{k+1,\ldots,k+n\}:\quad\text{source }k-i\ \longrightarrow\ \text{sink }k+i+1\pmod{2n}
詳しい解説

k∈{1,…,n}k\in\{1,\ldots,n\} を固定し、弦 i↔i+ni\leftrightarrow i+n を 1≤i≤k1\le i\le k では i+ni+n 向き、k<i≤nk<i\le n では ii 向きに定めると、シンクは k+1,k+2,…,k+nk+1,k+2,\ldots,k+n となる。シンクでない nn 個の端点から同時に nn 個のプレゼントを出発させる。nn に関する帰納法により、i=0,1,…,n−1i=0,1,\ldots,n-1 について k−ik-i からのプレゼントは互いに交差しない経路を通って k+i+1k+i+1（法 2n2n）へ到達することを示す。弦 k→k+nk\to k+n を除くと、帰納法の仮定から 1≤i≤n−11\le i\le n-1 に対し k−ik-i は互いに交差しない経路で k+i+2k+i+2 へ進み、これらの経路は ii の順に弦 k→k+nk\to k+n と交わる。弦 k→k+nk\to k+n を戻すと、kk からのプレゼントは最初の経路に乗って k+1k+1 へ進み、続く各 k−ik-i からの経路は順に1つ手前の旧経路へ乗り換えて k+i+1k+i+1 に達する。i=k−1i=k-1 とすれば、Tony のいる 1=k−(k−1)1=k-(k-1) からのプレゼントは k+(k−1)+1=2kk+(k-1)+1=2k に届く。k=1,…,nk=1,\ldots,n を動かせば nn 個の偶数頂点 2,4,…,2n2,4,\ldots,2n すべてに到達できる。