第6题

平面上有

n\ge2

条线段，任意两条都相交，且没有三条线段共点。Geoff 必须为每条线段选定一个端点，在那里放一只青蛙，面朝另一个端点。然后他会拍手

n-1

次；每拍一次手，每只青蛙都立即向前跳到其所在线段上的下一个交点（青蛙从不改变跳跃的方向）。Geoff 希望这样放置青蛙，使得任何两只青蛙都不会在同一时刻占据同一个交点。(a) 证明当

n

为奇数时，Geoff 总能实现他的愿望。(b) 证明当

n

为偶数时，Geoff 永远无法实现他的愿望。

第 1/4 步：把整个构型围起来并重新标号

上一步下一步

通俗地说

把每条线段的端点向外投影到一个大的外接圆上，可以保持循环顺序，同时不改变哪些线段互相相交的关系。

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

详细分析

取一个足够大的圆 $\omega$ ，使其内部包含 $n$ 条线段的全部 $\binom n2$ 个交点，并把每条线段向两个方向向外延长，直到与 $\omega$ 相交；把 $\omega$ 上得到的 $2n$ 个点按顺时针方向重新标记为 $P_1,P_2,\dots,P_{2n}$ 。由于原来的任意两条线段都相交，而 $\omega$ 中不相交的弦的端点在内部永远不会相交，所以这 $n$ 条线段中的每一条实际上都必须连接一个点 $P_i$ 与在这种循环标号下与它恰好相对的点 $P_{i+n}$ （指标取模 $2n$ ）：如果某条线段连接的是 $P_i$ 与满足 $j-i\ne n\pmod{2n}$ 的 $P_j$ ，那么它对应的弦就无法与连接另一对点的弦相交，这与任意两条线段都相交矛盾。