MathLabs

第6题

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

当 nn 为偶数时，每条线段的两个端点会自动具有相同的指标奇偶性，把 nn 条线段分成奇数一半和偶数一半；但放置方式却被迫完全属于同一种奇偶性。

n even⇒ parity(i)=parity(i+n) ⇒ n2 segments both-odd, n2 both-evenn\ \text{even} \Rightarrow\ \text{parity}(i)=\text{parity}(i+n)\ \Rightarrow\ \tfrac n2\ \text{segments both-odd},\ \tfrac n2\ \text{both-even}
详细分析

由上一步，所选的 nn 个起始点必须全部具有同一固定的指标奇偶性——不妨设它们恰好是 nn 个奇数标号的点 P1,P3,…,P2n−1P_1,P_3,\dots,P_{2n-1}（偶数标号的情形是对称的）。现在，若 nn 为偶数，则对每个 ii，指标 ii 与 i+ni+n 具有相同的奇偶性（加上一个偶数不改变奇偶性）。因此这 nn 条线段 {Pi,Pi+n}\{P_i,P_{i+n}\} 中的每一条，其指标对要么“都是奇数”，要么“都是偶数”，且恰好有 n2\tfrac n2 条线段是都为奇数，另外 n2\tfrac n2 条是都为偶数（当 ii 取遍 1,…,n1,\dots,n 时，恰好一半为奇数）。但由于 n≥2n\ge2 为偶数，至少存在一条线段是都为偶数，即该线段的 PiP_i 与 Pi+nP_{i+n} 都是偶数标号——然而那条线段上的青蛙必须从这两点之一出发，而这两点都不是奇数标号，这与每个所选起始点都是奇数标号相矛盾。这一矛盾表明，当 nn 为偶数时不存在有效的放置方式：Geoff 永远无法实现他的愿望。