MathLabs

第5题

平面上有 nn 条线段,任意三条不共点,且任意两条都在各自内部恰好相交一次。Tony 和他的 2n−12n-1 位朋友分别站在不同线段的端点处。Tony 希望按如下方式给朋友们送圣诞礼物:首先,他在每条线段上选定一个端点作为“汇点”;然后把礼物放在自己所在的端点。礼物按如下规则移动:在线段上时朝该线段的汇点移动;到达两条线段的交点时,转到另一条线段上并朝新的汇点移动。若礼物到达某个端点,站在该端点处的朋友就能收到礼物。证明 Tony 恰好能把礼物送给 2n−12n-1 位朋友中的 nn 位。
第 2/3 步:至多 n 个偶数号顶点能收到礼物
2-color regions red (clockwise) / blue (anticlockwise) ⟹ boundary directions alternate: odd outgoing, even incoming\text{2-color regions red (clockwise) / blue (anticlockwise)}\ \Longrightarrow\ \text{boundary directions alternate: odd outgoing, even incoming}
详细分析

将圆内被 nn 条弦分割出的区域用红、蓝二染色,使相邻区域异色,且与顶点 11 相邻的两个区域从 11 望去右侧为红、左侧为蓝。令每个红区域的边界顺时针定向,每个蓝区域的边界逆时针定向;则分隔红、蓝区域的每一小段弦从两侧获得相同的方向。从 11 出发的礼物沿与两侧区域一致的方向在弦上移动,每到交点转上相交弦时仍紧贴原来两个区域之一,故始终顺着区域定向前行。沿外圆周各区域颜色交替,故顶点 1,2,…,2n1,2,\ldots,2n 处的弦方向在奇数顶点处向外、偶数顶点处向内交替出现。因此从 11 出发的礼物只能到达 nn 个偶数号顶点 2,4,…,2n2,4,\ldots,2n。