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 值，以及所有使巴扎有必胜策略的情形。
第 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)。函数 t↦t+2−t2t\mapsto t+\sqrt{2-t^2} 在 [0,2][0,\sqrt2] 上仅在 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 贡献到累计和中。