MathLabs

第3题

设 nn 为正整数。刘邦与项羽有一根长度为 11 的木棍，想要在两人之间分配。刘邦先在木棍上标记至多 nn 个点，接着项羽在木棍上标记至多 nn 个点。所有被标记的点互不相同。然后在所有标记点处将木棍切断，得到若干小段。随后两人轮流取走任意一段尚未被取走的木棍，由刘邦先取。每个人的目标都是使自己拿到的木棍总长度最大。对每个 nn，求最大的常数 cc，使得无论项羽如何行动，刘邦都能保证自己拿到的总长度至少为 cc。
第 3/5 步：对 2^(n+1) 个子集和用抽屉原理给出刘邦的上界
上一步下一步
2n+1 subset sums Σ(S)∈[0,1] ⟹ ∃ S≠T: 0≤Σ(S)−Σ(T)≤12n+1−1 ⟹ G≤12n+1−12^{n+1}\ \text{subset sums }\Sigma(S)\in[0,1]\ \Longrightarrow\ \exists\,S\ne T:\ 0\le\Sigma(S)-\Sigma(T)\le\frac1{2^{n+1}-1}\ \Longrightarrow\ G\le\frac1{2^{n+1}-1}
详细分析

当 SS 取遍 n+1n+1 个大段的全部 2n+12^{n+1} 个子集时，子集和 Σ(S)\Sigma(S) 都落在 [0,1][0,1] 内，且 Σ(∅)=0\Sigma(\varnothing)=0、Σ(all)=1\Sigma(\text{all})=1。将 [0,1][0,1] 均分为 2n+1−12^{n+1}-1 个长为 12n+1−1\tfrac1{2^{n+1}-1} 的小区间，由抽屉原理存在两个不同子集 S,TS,T 满足 0≤Σ(S)−Σ(T)≤12n+1−10\le\Sigma(S)-\Sigma(T)\le\tfrac1{2^{n+1}-1}。从二者中同时删去 S∩TS\cap T，既不改变 Σ(S)−Σ(T)\Sigma(S)-\Sigma(T) 又使 S,TS,T 不相交，故由第2步项羽可保证 G≤12n+1−1G\le\tfrac1{2^{n+1}-1}，即刘邦的总长至多为 12(1+12n+1−1)=2n2n+1−1\tfrac12\bigl(1+\tfrac1{2^{n+1}-1}\bigr)=\tfrac{2^n}{2^{n+1}-1}。