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 值,以及所有使巴扎有必胜策略的情形。
第 1/4 步:爱丽丝一直打 0,随后祭出一步巨大的棋
λ>12 ⟹ Alice wins\lambda>\tfrac1{\sqrt2}\ \Longrightarrow\ \text{Alice wins}
详细分析

设爱丽丝在每个奇数轮都打 x2i−1=0x_{2i-1}=0。无论巴扎怎么做,他自己的约束都迫使 x22+⋯+x2k2≤2kx_2^2+\cdots+x_{2k}^2\le2k,故由柯西—施瓦茨不等式 x2+⋯+x2k≤k⋅2k=k2x_2+\cdots+x_{2k}\le\sqrt{k\cdot2k}=k\sqrt2;由于奇数项都是 00,第 2k2k 轮后的累计和 x1+⋯+x2k≤k2x_1+\cdots+x_{2k}\le k\sqrt2。若 λ>1/2\lambda>1/\sqrt2,选取足够大的 kk 使 λ(2k+1)−k2>2k+2\lambda(2k+1)-k\sqrt2>\sqrt{2k+2}(这是可能的,因为左边随 kk 线性增长,右边只按 k\sqrt k 增长)。此时爱丽丝可以合法地把 x2k+1x_{2k+1} 打成不超过 λ(2k+1)−(x1+⋯+x2k)\lambda(2k+1)-(x_1+\cdots+x_{2k}) 的任意值,而这个上限至少为 λ(2k+1)−k2>2k+2\lambda(2k+1)-k\sqrt2>\sqrt{2k+2};打出这样的值会使 x12+⋯+x2k+12>2k+2x_1^2+\cdots+x_{2k+1}^2>2k+2 立即成立,于是巴扎在下一轮没有合法的 x2k+2≥0x_{2k+2}\ge0 而落败。