MathLabs

第3题

设 nn 为正整数。刘邦与项羽有一根长度为 11 的木棍,想要在两人之间分配。刘邦先在木棍上标记至多 nn 个点,接着项羽在木棍上标记至多 nn 个点。所有被标记的点互不相同。然后在所有标记点处将木棍切断,得到若干小段。随后两人轮流取走任意一段尚未被取走的木棍,由刘邦先取。每个人的目标都是使自己拿到的木棍总长度最大。对每个 nn,求最大的常数 cc,使得无论项羽如何行动,刘邦都能保证自己拿到的总长度至少为 cc。
第 5/5 步:结论
c=2n2n+1−1c=\frac{2^n}{2^{n+1}-1}
详细分析

在第4步中取 k=nk=n(再除以缩放因子 2n+1−12^{n+1}-1),可知项羽的总长 x2+x4+⋯+x2nx_2+x_4+\cdots+x_{2n} 至多为 2n−12n+1−1\tfrac{2^n-1}{2^{n+1}-1},因此刘邦至少能保证拿到 1−2n−12n+1−1=2n2n+1−11-\tfrac{2^n-1}{2^{n+1}-1}=\tfrac{2^n}{2^{n+1}-1}。结合第3步项羽给出的上界,刘邦能保证的最大总长度为 c=2n2n+1−1c=\tfrac{2^n}{2^{n+1}-1}。