MathLabs

第6問

平面上に、どの2本も交わり、どの3本も1点で交わらないような n≥2n\ge2 本の線分がある。ジェフは各線分の端点を1つ選び、そこにカエルを置いて、もう一方の端点の方を向かせる。その後、彼は手を n−1n-1 回叩く。手を叩くたびに、すべてのカエルは即座に自分の線分上の次の交点まで前方に跳ぶ（カエルは決して跳ぶ向きを変えない）。ジェフは、どの2匹のカエルも同時に同じ交点を占めることがないようにカエルを配置したいと考えている。(a) nn が奇数のとき、ジェフは常にその望みを実現できることを証明せよ。(b) nn が偶数のとき、ジェフは決してその望みを実現できないことを証明せよ。
ステップ 3/4: (b) 部分：有効な配置が必ず持つ形
前のステップ次のステップ
ざっくり言うと

もし2匹のカエルが円上の連続する点から出発すると、最初の跳躍ですでに衝突してしまう。もし同じ線分の反対側の端から出発すると、その線分自体が衝突する。

no two frogs at adjacent Pi, none at antipodal Pi,Pi+n\text{no two frogs at adjacent }P_i,\ \text{none at antipodal }P_i,P_{i+n}
詳しい解説

背理法により、nn 匹のカエルのある配置（各線分に1匹ずつ、すなわち各ペア {Pi,Pi+n}\{P_i,P_{i+n}\} のどちらか一方を選ぶ）がすべての衝突を回避すると仮定する。カエルは巡回的に連続する2点 Pi,Pi+1P_i,P_{i+1} には置けないことが分かる（それらの最初の交点はただちに一致してしまう）ので、選ばれた nn 個の開始点は円の周りで交互に並ばなければならない。2n2n 個の位置のうち nn 個であることと合わせると、それらはちょうど1つおきの位置、すなわち単一の固定されたパリティの位置を占めなければならない。しかし、PiP_i と Pi+nP_{i+n} はまさに同じ線分の2つの端点であり、各線分には1匹しかカエルが置かれないので、対蹠のペア Pi,Pi+nP_i,P_{i+n} に2匹のカエルを置くこともできない。