MathLabs

第5题

平面上有 nn 条线段，任意三条不共点，且任意两条都在各自内部恰好相交一次。Tony 和他的 2n−12n-1 位朋友分别站在不同线段的端点处。Tony 希望按如下方式给朋友们送圣诞礼物：首先，他在每条线段上选定一个端点作为“汇点”；然后把礼物放在自己所在的端点。礼物按如下规则移动：在线段上时朝该线段的汇点移动；到达两条线段的交点时，转到另一条线段上并朝新的汇点移动。若礼物到达某个端点，站在该端点处的朋友就能收到礼物。证明 Tony 恰好能把礼物送给 2n−12n-1 位朋友中的 nn 位。
第 3/3 步：归纳构造汇点以到达每个偶数顶点 2k
上一步下一步
For 1≤k≤n, set sinks {k+1,…,k+n}:source k−i ⟶ sink k+i+1(mod2n)\text{For }1\le k\le n,\text{ set sinks }\{k+1,\ldots,k+n\}:\quad\text{source }k-i\ \longrightarrow\ \text{sink }k+i+1\pmod{2n}
详细分析

固定 k∈{1,…,n}k\in\{1,\ldots,n\}，将弦 i↔i+ni\leftrightarrow i+n 在 1≤i≤k1\le i\le k 时定向指向 i+ni+n，在 k<i≤nk<i\le n 时定向指向 ii，使汇点恰为 k+1,k+2,…,k+nk+1,k+2,\ldots,k+n。从 nn 个非汇点同时发出 nn 份礼物。对 nn 归纳证明：对 i=0,1,…,n−1i=0,1,\ldots,n-1，从 k−ik-i 出发的礼物沿两两不相交的路径到达 k+i+1k+i+1（模 2n2n）。事实上，去掉弦 k→k+nk\to k+n 后，由归纳假设知对 1≤i≤n−11\le i\le n-1，从 k−ik-i 出发的路径两两不相交地通往 k+i+2k+i+2，且按 ii 递增的顺序依次与弦 k→k+nk\to k+n 相交；放回弦 k→k+nk\to k+n 后，从 kk 出发的礼物转入第一条路径到达 k+1k+1，而每条从 k−ik-i 出发的路径依次改道进入通往 k+i+1k+i+1 的旧路径。取 i=k−1i=k-1，Tony 从 1=k−(k−1)1=k-(k-1) 发出的礼物就到达 k+(k−1)+1=2kk+(k-1)+1=2k。令 k=1,…,nk=1,\ldots,n 变化，即可到达全部 nn 个偶数顶点 2,4,…,2n2,4,\ldots,2n。