MathLabs

第3問

nn を正の整数とする。Liu Bang と Xiang Yu は長さ 11 の棒を1本持っており、それを2人で分けたい。まず Liu が棒の上に高々 nn 個の点に印を付け、次に Xiang が棒の上に高々 nn 個の点に印を付ける。印を付けられた点はすべて異なる。その後、印を付けられたすべての点で棒を切り、いくつかの断片を作る。続いて、Liu から始めて交互にまだ取られていない断片を1つずつ取っていき、各プレイヤーは自分の断片の長さの合計を最大化することを目指す。各 nn に対し、Xiang の打ち方にかかわらず Liu が少なくとも長さの合計 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 で割り戻す)、Xiang の合計 x2+x4+⋯+x2nx_2+x_4+\cdots+x_{2n} が高々 2n−12n+1−1\tfrac{2^n-1}{2^{n+1}-1} であることが分かるので、Liu は少なくとも 1−2n−12n+1−1=2n2n+1−11-\tfrac{2^n-1}{2^{n+1}-1}=\tfrac{2^n}{2^{n+1}-1} を保証できる。ステップ3の Xiang による上界と合わせると、Liu が保証できる最大の合計長は c=2n2n+1−1c=\tfrac{2^n}{2^{n+1}-1} である。