第6問

平面上に、どの2本も交わり、どの3本も1点で交わらないような

n\ge2

本の線分がある。ジェフは各線分の端点を1つ選び、そこにカエルを置いて、もう一方の端点の方を向かせる。その後、彼は手を

n-1

回叩く。手を叩くたびに、すべてのカエルは即座に自分の線分上の次の交点まで前方に跳ぶ（カエルは決して跳ぶ向きを変えない）。ジェフは、どの2匹のカエルも同時に同じ交点を占めることがないようにカエルを配置したいと考えている。(a)

n

が奇数のとき、ジェフは常にその望みを実現できることを証明せよ。(b)

n

が偶数のとき、ジェフは決してその望みを実現できないことを証明せよ。

ステップ 1/4: 配置を囲み、ラベルを付け直す

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

ざっくり言うと

各線分の端点を外側の大きな円へ射影することで、どの線分がどの線分と交わるかを変えることなく、巡回的な順序を保持できる。

\omega\supset\{\text{all }\tbinom n2\text{ intersection points}\},\qquad P_1,\dots,P_{2n}\ \text{in clockwise order}

詳しい解説

$n$ 本の線分の $\binom n2$ 個の交点をすべて内部に含むのに十分大きい円 $\omega$ を取り、各線分を両方向に外側へ延長して $\omega$ と交わるまで伸ばす。 $\omega$ 上に得られる $2n$ 個の点を時計回りに $P_1,P_2,\dots,P_{2n}$ とラベル付け直す。もとの線分のどの2本も交わり、 $\omega$ の交わらない弦の端点同士は内部で決して交わらないので、 $n$ 本の各線分は実際にはこの巡回的なラベル付けにおいて（指数は $2n$ を法として取る）ちょうど反対側にある点 $P_i$ と $P_{i+n}$ を結ばなければならない：もし線分が $j-i\ne n\pmod{2n}$ を満たす $P_i$ と $P_j$ を結んでいたら、その弦は他のあるペアを結ぶ弦と交わらないことになり、どの2本の線分も交わるという条件に矛盾する。