MathLabs

第3题

设 nn 为正整数。刘邦与项羽有一根长度为 11 的木棍，想要在两人之间分配。刘邦先在木棍上标记至多 nn 个点，接着项羽在木棍上标记至多 nn 个点。所有被标记的点互不相同。然后在所有标记点处将木棍切断，得到若干小段。随后两人轮流取走任意一段尚未被取走的木棍，由刘邦先取。每个人的目标都是使自己拿到的木棍总长度最大。对每个 nn，求最大的常数 cc，使得无论项羽如何行动，刘邦都能保证自己拿到的总长度至少为 cc。
第 1/5 步：把轮流取段阶段归约为交错差 G
上一步下一步
x1≥x2≥⋯≥x2n+1≥0,G:=x1−x2+x3−x4+⋯+x2n+1,Liu’s total=1+G2x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0,\qquad G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1},\qquad \text{Liu's total}=\frac{1+G}{2}
详细分析

允许切点重合(产生长度为 00 的小段)，从而每人恰好切 nn 刀，得到 2n+12n+1 段，其长度满足 x1≥x2≥⋯≥x2n+1≥0x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0 且 ∑i=12n+1xi=1\sum_{i=1}^{2n+1}x_i=1。在轮流取段阶段，双方最优策略都是在自己回合取走剩余最长的一段，故刘邦拿到 x1+x3+⋯+x2n+1x_1+x_3+\cdots+x_{2n+1}，项羽拿到 x2+x4+⋯+x2nx_2+x_4+\cdots+x_{2n}。用差距 G:=x1−x2+x3−x4+⋯+x2n+1G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1} 表示，刘邦的总长为 1+G2\tfrac{1+G}{2}，项羽的总长为 1−G2\tfrac{1-G}{2}，因此最大化刘邦的总长等价于最大化 GG。