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 の値と、バザが必勝戦略を持つ場合をすべて求めよ。
ステップ 3/4: 最終的にバザはアリスに合法な手を残さない
前のステップ次のステップ
λ<12 ⟹ Bazza wins\lambda<\tfrac1{\sqrt2}\ \Longrightarrow\ \text{Bazza wins}
詳しい解説

ステップ2を kk 個の組 (x1,x2),…,(x2k−1,x2k)(x_1,x_2),\ldots,(x_{2k-1},x_{2k}) にわたって足し合わせると、バザの戦略の下でアリスの打ち方によらず x1+⋯+x2k≥k2x_1+\cdots+x_{2k}\ge k\sqrt2 を得る。アリスがターン 2k+12k+1 で合法な手 x2k+1≥0x_{2k+1}\ge0 を持つには x1+⋯+x2k≤λ(2k+1)x_1+\cdots+x_{2k}\le\lambda(2k+1) が必要であり、よって k2≤λ(2k+1)k\sqrt2\le\lambda(2k+1)。λ<1/2\lambda<1/\sqrt2 なら、k→∞k\to\infty のとき左辺は 2 k\sqrt2\,k のように増加するが右辺は 2λk<2 k2\lambda k<\sqrt2\,k のように増加するので、十分大きなすべての kk でこの不等式は成り立たなくなる;その時点でアリスは合法な手を持たず負ける。