第3题
设 为正整数。刘邦与项羽有一根长度为 的木棍，想要在两人之间分配。刘邦先在木棍上标记至多 个点，接着项羽在木棍上标记至多 个点。所有被标记的点互不相同。然后在所有标记点处将木棍切断，得到若干小段。随后两人轮流取走任意一段尚未被取走的木棍，由刘邦先取。每个人的目标都是使自己拿到的木棍总长度最大。对每个 ，求最大的常数 ，使得无论项羽如何行动，刘邦都能保证自己拿到的总长度至少为 。
详细分析
把刘邦切出的 个区间称为原始大段，对大段子集 记其长度和为 。取两个不相交且不同时为空的子集 ，并设 。将 、 中的大段分别按从左到右的顺序排成两行，使两行从同一原点开始。沿原点向前扫描：每当一行的累计端点到达另一行某大段的端点，就在相应的实际大段的该距离处下刀。于是较短一行结束以前的部分逐一配成等长小段，较长一行留下一个长度为 的超出部分。项羽把 之外的每个原始大段平分；在超出部分内，他还把其中完整的每个 大段平分，使超出部分不会产生额外的未配对交错贡献。现在精确计数。设超出部分内完整的 S 大段有 q 个。在 T 行结束以前，S 行至多有 S 大段数减 q 减一 个内部端点，T 行有比其大段数少一个的内部端点；每个端点至多导致一刀镜像切割。因此镜像阶段至多用 S 大段数加 T 大段数减 q 减二 刀。再把超出部分的 q 个大段以及 S,T 之外的所有大段平分，增加其余大段的刀数，总数至多为 n-1，当然不超过 n。若 T 为空，则把 n+1 个大段中的一个留下，其余平分，恰用 n 刀。 每个配对小段都有等长伙伴。在按长度排序的列表中，等长伙伴在 中符号相反而抵消；抵消后至多只剩超出部分末端的一个小段，其长度不超过 。故项羽能保证 。