MathLabs

第5問

アリスとバザは、両者に知られている正の実数 λ\lambda に依存するルールを持つ2人ゲーム inekoalaty game をプレイする。ゲームの第 nn ターン(n=1n=1 から始まる)では次のことが起こる:nn が奇数ならアリスは x1+x2+⋯+xn≤λnx_1+x_2+\cdots+x_n\le\lambda n を満たす非負実数 xnx_n を選ぶ;nn が偶数ならバザは x12+x22+⋯+xn2≤nx_1^2+x_2^2+\cdots+x_n^2\le n を満たす非負実数 xnx_n を選ぶ。ある選手が適切な数 xnx_n を選べなければ、ゲームは終了しもう一方の選手が勝つ。ゲームが永遠に続くなら、どちらも勝たない。選ばれた数はすべて両選手に知られている。アリスが必勝戦略を持つ λ\lambda の値と、バザが必勝戦略を持つ場合をすべて求めよ。
ステップ 2/4: バザの貪欲な応手により各組の合計は少なくとも √2 になる
前のステップ次のステップ
t+2−t2≥2for all t∈[0,2]t+\sqrt{2-t^2}\ge\sqrt2\quad\text{for all }t\in[0,\sqrt2]
詳しい解説

バザの戦略は常に合法な最大値を打つことである;帰納法により、ターン 2i2i の後、彼の累計平方和はちょうど 2i2i になるので、ターン 2i2i では x2i=2−x2i−12x_{2i}=\sqrt{2-x_{2i-1}^2} を打つ(ターン 2i−22i-2 以降に加わる予算がちょうど 22 であるため)。[0,2][0,\sqrt2] 上の関数 t↦t+2−t2t\mapsto t+\sqrt{2-t^2} は t=1t=1 でのみ導関数がゼロになり(最大値 22)、端点 t=0,2t=0,\sqrt2 で最小となりそこで 2\sqrt2 に等しい;よって常に t+2−t2≥2t+\sqrt{2-t^2}\ge\sqrt2 である。したがってアリスが x2i−1x_{2i-1} をどう選んでも、その組は累計に x2i−1+x2i≥2x_{2i-1}+x_{2i}\ge\sqrt2 を寄与する。