MathLabs

第3题

设 nn 为正整数。刘邦与项羽有一根长度为 11 的木棍，想要在两人之间分配。刘邦先在木棍上标记至多 nn 个点，接着项羽在木棍上标记至多 nn 个点。所有被标记的点互不相同。然后在所有标记点处将木棍切断，得到若干小段。随后两人轮流取走任意一段尚未被取走的木棍，由刘邦先取。每个人的目标都是使自己拿到的木棍总长度最大。对每个 nn，求最大的常数 cc，使得无论项羽如何行动，刘邦都能保证自己拿到的总长度至少为 cc。
第 4/5 步：刘邦的 1 : 2 : 4 : ... : 2^n 分割从上方限制项羽
上一步下一步
segments 12n+1−1,22n+1−1,…,2n2n+1−1:x2+x4+⋯+x2k≤2n−1+2n−2+⋯+2n−k2n+1−1\text{segments }\frac{1}{2^{n+1}-1},\frac{2}{2^{n+1}-1},\ldots,\frac{2^n}{2^{n+1}-1}:\qquad x_2+x_4+\cdots+x_{2k}\le\frac{2^{n-1}+2^{n-2}+\cdots+2^{n-k}}{2^{n+1}-1}
详细分析

反过来，将木棍放大 2n+1−12^{n+1}-1 倍；刘邦安排切点，使 n+1n+1 个原始大段长度为 1,2,4,…,2n1,2,4,\ldots,2^n。项羽切割后，把所有小段按第1步排序。我们对 k=1,…,nk=1,\ldots,n 归纳证明 x2+x4+⋯+x2k≤2n−1+2n−2+⋯+2n−kx_2+x_4+\cdots+x_{2k}\le2^{n-1}+2^{n-2}+\cdots+2^{n-k}。当 k=1k=1 时即 x2≤2n−1x_2\le2^{n-1}：长度超过 2n−12^{n-1} 的小段只能完全来自唯一的长度 2n2^n 大段，而其中不可能放入两段互不相交的小段。假设命题对 k−1k-1 成立，却在 kk 首次失效。将对应 k−1k-1 的上界与下一上界相减，得 x2k>2n−kx_{2k}>2^{n-k}。由于小段已排序，x1,…,x2kx_1,\ldots,x_{2k} 全都严格长于 2n−k2^{n-k}。从长度不超过 2n−k2^{n-k} 的原始大段切出的部分不可能这么长，故这 2k2k 段必须完全来自长度为 2n−k+1,…,2n2^{n-k+1},\ldots,2^n 的最大 kk 个大段。因此 x1+⋯+x2kx_1+\cdots+x_{2k} 不超过它们的总长 2n−k+1+⋯+2n2^{n-k+1}+\cdots+2^n。又因每一对都有 x2i−1≥x2ix_{2i-1}\ge x_{2i}，偶数号小段之和至多为该总长的一半，即 2n−k+⋯+2n−12^{n-k}+\cdots+2^{n-1}，这与 kk 处失效矛盾。归纳完成；严格不等式也直接涵盖重合切点或零长度小段，无需取极限。