MathLabs

第6题

平面上有 n≥2n\ge2 条线段，任意两条都相交，且没有三条线段共点。Geoff 必须为每条线段选定一个端点，在那里放一只青蛙，面朝另一个端点。然后他会拍手 n−1n-1 次；每拍一次手，每只青蛙都立即向前跳到其所在线段上的下一个交点（青蛙从不改变跳跃的方向）。Geoff 希望这样放置青蛙，使得任何两只青蛙都不会在同一时刻占据同一个交点。(a) 证明当 nn 为奇数时，Geoff 总能实现他的愿望。(b) 证明当 nn 为偶数时，Geoff 永远无法实现他的愿望。
第 3/4 步：(b) 部分：任何有效放置必须具备的形态
上一步下一步
通俗地说

如果两只青蛙从圆上相邻的两点出发，那么它们第一次跳跃就已经相撞；如果它们从同一条线段的两个相对端点出发，那条线段本身就会自相碰撞。

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 只青蛙的某种放置（每条线段一只，即在每对 {Pi,Pi+n}\{P_i,P_{i+n}\} 中选一个点）避免了所有碰撞。可以验证，青蛙不能放在圆上循环相邻的两点 Pi,Pi+1P_i,P_{i+1} 上（它们的第一个交点会立即重合），所以所选的 nn 个起始点必须沿圆交替分布；再结合这 nn 个点在 2n2n 个位置中的事实，它们必须恰好占据每隔一个的位置，即具有同一固定奇偶性的位置。但两只青蛙也不能放在一对直径相对的点 Pi,Pi+nP_i,P_{i+n} 上，因为 PiP_i 与 Pi+nP_{i+n} 正是同一条线段的两个端点，而每条线段只放一只青蛙。