Math Labs

Bài 5

Alice và Bazza chơi trò inekoalaty, một trò chơi hai người mà luật lệ phụ thuộc vào một số thực dương λ\lambda mà cả hai người chơi đều biết. Ở lượt thứ nn của trò chơi (bắt đầu từ n=1n=1), điều sau xảy ra: nếu nn lẻ, Alice chọn một số thực không âm xnx_n sao cho x1+x2+⋯+xn≤λnx_1+x_2+\cdots+x_n\le\lambda n; nếu nn chẵn, Bazza chọn một số thực không âm xnx_n sao cho x12+x22+⋯+xn2≤nx_1^2+x_2^2+\cdots+x_n^2\le n. Nếu một người chơi không thể chọn được số phù hợp xnx_n, trò chơi kết thúc và người kia thắng. Nếu trò chơi diễn ra mãi mãi, không ai thắng. Mọi số đã chọn đều được cả hai người chơi biết. Hãy xác định tất cả giá trị của λ\lambda mà Alice có chiến lược thắng và tất cả giá trị mà Bazza có chiến lược thắng.
Bước 1 trên 4: Alice chơi 0 mãi mãi, rồi tung ra một nước cực lớn
λ>12 ⟹ Alice wins\lambda>\tfrac1{\sqrt2}\ \Longrightarrow\ \text{Alice wins}
Phân tích chi tiết

Giả sử Alice chơi x2i−1=0x_{2i-1}=0 ở mọi lượt lẻ. Dù Bazza làm gì, ràng buộc của chính anh ta buộc x22+⋯+x2k2≤2kx_2^2+\cdots+x_{2k}^2\le2k, nên theo Cauchy–Schwarz x2+⋯+x2k≤k⋅2k=k2x_2+\cdots+x_{2k}\le\sqrt{k\cdot2k}=k\sqrt2; vì các số hạng lẻ bằng 00, tổng chạy sau lượt 2k2k là x1+⋯+x2k≤k2x_1+\cdots+x_{2k}\le k\sqrt2. Nếu λ>1/2\lambda>1/\sqrt2, chọn kk đủ lớn sao cho λ(2k+1)−k2>2k+2\lambda(2k+1)-k\sqrt2>\sqrt{2k+2} (có thể vì vế trái tăng tuyến tính theo kk trong khi vế phải tăng như k\sqrt k). Khi đó Alice có thể hợp lệ chơi x2k+1x_{2k+1} bằng bất kỳ giá trị nào tới λ(2k+1)−(x1+⋯+x2k)\lambda(2k+1)-(x_1+\cdots+x_{2k}), ít nhất là λ(2k+1)−k2>2k+2\lambda(2k+1)-k\sqrt2>\sqrt{2k+2}; chơi giá trị như vậy làm x12+⋯+x2k+12>2k+2x_1^2+\cdots+x_{2k+1}^2>2k+2 ngay, nên Bazza không có x2k+2≥0x_{2k+2}\ge0 hợp lệ ở lượt sau và thua.