第6問

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

n\ge2

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

n-1

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

n

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

n

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

ステップ 4/4: (b) 部分：

n

が偶数のときのパリティの衝突

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

ざっくり言うと

$n$ が偶数のとき、各線分の2つの端点は自動的に同じ指数のパリティを持つため、 $n$ 本の線分は奇数パリティの半分と偶数パリティの半分に分かれる。しかし配置は完全に1つのパリティでなければならなかった。

n\ \text{even} \Rightarrow\ \text{parity}(i)=\text{parity}(i+n)\ \Rightarrow\ \tfrac n2\ \text{segments both-odd},\ \tfrac n2\ \text{both-even}

詳しい解説

前のステップにより、選ばれた $n$ 個の開始点はすべて指数の固定された1つのパリティを共有しなければならない——一般性を失わずに、それらがちょうど $n$ 個の奇数番目の点 $P_1,P_3,\dots,P_{2n-1}$ であるとする（偶数番目の場合は対称的である）。さて、 $n$ が偶数ならば、すべての $i$ について指数 $i$ と $i+n$ は同じパリティを持つ（偶数を足してもパリティは変わらない）。したがって、 $n$ 本の各線分 $\{P_i,P_{i+n}\}$ はその指数のペアにおいて「両方奇数」か「両方偶数」のいずれかであり、ちょうど $\tfrac n2$ 本の線分が両方奇数で、残りの $\tfrac n2$ 本が両方偶数である（ $i$ が $1,\dots,n$ にわたるとき、ちょうど半分が奇数である）。しかし $n\ge2$ は偶数なので、少なくとも1本の線分は両方偶数であり、すなわちその線分の $P_i$ と $P_{i+n}$ の両方が偶数の指数を持つ——それでもその線分上のカエルはこの2点のどちらかから出発しなければならず、そのどちらも奇数番目ではないため、選ばれたすべての開始点が奇数番目であることと矛盾する。この矛盾により、 $n$ が偶数のとき有効な配置は存在しないことが示される：ジェフは決してその望みを実現できない。