MathLabs

第3問

nn を正の整数とする。Liu Bang と Xiang Yu は長さ 11 の棒を1本持っており、それを2人で分けたい。まず Liu が棒の上に高々 nn 個の点に印を付け、次に Xiang が棒の上に高々 nn 個の点に印を付ける。印を付けられた点はすべて異なる。その後、印を付けられたすべての点で棒を切り、いくつかの断片を作る。続いて、Liu から始めて交互にまだ取られていない断片を1つずつ取っていき、各プレイヤーは自分の断片の長さの合計を最大化することを目指す。各 nn に対し、Xiang の打ち方にかかわらず Liu が少なくとも長さの合計 cc を保証できるような最大の値 cc を求めよ。
ステップ 1/5: 取り合いの段階を交互差 G に帰着させる
前のステップ次のステップ
x1≥x2≥⋯≥x2n+1≥0,G:=x1−x2+x3−x4+⋯+x2n+1,Liu’s total=1+G2x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0,\qquad G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1},\qquad \text{Liu's total}=\frac{1+G}{2}
詳しい解説

重なるカット(長さ 00 の断片を生む)を許すことで、各プレイヤーがちょうど nn 回カットし、∑i=12n+1xi=1\sum_{i=1}^{2n+1}x_i=1 を満たす長さ x1≥x2≥⋯≥x2n+1≥0x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0 の 2n+12n+1 個の断片ができるとする。取り合いの段階では、各プレイヤーは自分の番に残っている最大の断片を取るのが最適なので、Liu は x1+x3+⋯+x2n+1x_1+x_3+\cdots+x_{2n+1} を、Xiang は x2+x4+⋯+x2nx_2+x_4+\cdots+x_{2n} を得る。差 G:=x1−x2+x3−x4+⋯+x2n+1G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1} を用いると、Liu の合計は 1+G2\tfrac{1+G}{2}、Xiang の合計は 1−G2\tfrac{1-G}{2} となるので、Liu の合計の最大化は GG の最大化と同値である。