MathLabs

第5题

平面上有 nn 条线段,任意三条不共点,且任意两条都在各自内部恰好相交一次。Tony 和他的 2n−12n-1 位朋友分别站在不同线段的端点处。Tony 希望按如下方式给朋友们送圣诞礼物:首先,他在每条线段上选定一个端点作为“汇点”;然后把礼物放在自己所在的端点。礼物按如下规则移动:在线段上时朝该线段的汇点移动;到达两条线段的交点时,转到另一条线段上并朝新的汇点移动。若礼物到达某个端点,站在该端点处的朋友就能收到礼物。证明 Tony 恰好能把礼物送给 2n−12n-1 位朋友中的 nn 位。
第 1/3 步:圆弦模型与对径顶点配对
Vertices 1,…,2n on a circle (Tony at 1);each chord connects k and k+n(mod2n)\text{Vertices }1,\ldots,2n\text{ on a circle (Tony at }1\text{)};\quad\text{each chord connects }k\text{ and }k+n\pmod{2n}
详细分析

作一个包含全部 (n2)\binom{n}{2} 个内部交点的大圆,将 nn 条线段延长为圆的弦,并从 Tony 所在的端点 11 起逆时针将 2n2n 个弦端点编号为 1,2,…,2n1,2,\ldots,2n。由于任意两条弦都在圆内相交,每条弦两侧各有 n−1n-1 个端点,故每条弦连接 kk 与 k+nk+n(1≤k≤n1\le k\le n)。