MathLabs

第5题

爱丽丝(Alice)与巴扎(Bazza)在玩 inekoalaty 游戏,这是一个双人游戏,其规则依赖于双方都知道的正实数 λ\lambda。在游戏的第 nn 轮(从 n=1n=1 开始)会发生以下情况:若 nn 为奇数,爱丽丝选取一个非负实数 xnx_n,使得 x1+x2+⋯+xn≤λnx_1+x_2+\cdots+x_n\le\lambda n;若 nn 为偶数,巴扎选取一个非负实数 xnx_n,使得 x12+x22+⋯+xn2≤nx_1^2+x_2^2+\cdots+x_n^2\le 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 都不成立;此时爱丽丝没有合法的棋可下,落败。