Problem 5. Alice and Bazza are playing the inekoalaty game, a two-player game whose rules depend on a positive real number λ which is known to both players. On the nth turn of the game (starting with n = 1) the following happens:

• If n is odd, Alice chooses a nonnegative real number xn such that

x1+x2+ ...+xn≤λn

• If n is even, Bazza chooses a nonnegative real number xn such that

x 1 2 + x 2 2 + ...+ x n 2 ≤n

If a player cannot choose a suitable number xn, the game ends and the other player wins. If the game goes on forever, neither player wins. All chosen numbers are known to both players.

Determine all values of λ for which Alice has a winning strategy and all those for which Bazza has a winning strategy.

Solution 1Solution 2

Solution 1

Let $c=\frac1{\sqrt2}$. We claim Alice wins for $\lambda>c$, Bazza wins for $\lambda<c$, and they tie when $\lambda=c$.

First consider Alice. Her safe strategy is to sandbag and always set $x_n=0$. We first show inductively she does not lose for $\lambda\ge c$. For the base case, she is initially safe. Suppose she is safe up to turn $2n$. Then we have

\[2n\ge x_2^2+x_4^2+\dots+x_{2n}^2\ge\frac1n(x_2+x_4+\dots+x_{2n})^2,\]

so $x_2+x_4+\dots+x_{2n}\le n\sqrt2\le\lambda(2n+1)$, so she is safe for turns $2n+1$ and $2n+2$. Thus she does not lose.

Now to show she wins at $\lambda>c$, instead she stops sandbagging at turn $2n+1$, instead forcing equality with $x_2+x_4+\dots+x_{2n}+x_{2n+1}=\lambda(2n+1)$. Then

\[x_2^2+x_4^2+\dots+x_{2n}^2+x_{2n+1}^2\ge\frac1{n+1}(x_2+x_4+\dots+x_{2n}+x_{2n+1})^2=\frac{\lambda^2(2n+1)^2}{n+1}.\]

Since $\lambda>c$, we can find some $n$ such that $\lambda^2>\left(\frac{2n+2}{2n+1}\right)^2\cdot\frac12$ for Alice to stop sandbagging and win.

Now Bazza's strategy is to go all in every turn, always making the inequality strict and thus having $x_{2i-1}^2+x_{2i}^2=2$. First we show inductively he is safe for $\lambda\le c$. For the base case, he is initially safe. Suppose he is safe up to turn $2n$. Then we have $x_{2i-1}^2+x_{2i}^2=2$, so $x_{2i-1}+x_{2i}\ge\sqrt2$. Thus

\[x_{2n+1}=(x_1+\dots+x_{2n+1})-(x_1+\dots+x_{2n})\le\lambda(2n+1)-n\sqrt2,\]

which is $\le\sqrt2$ for $\lambda\le c$, so he is safe on turns $2n+1$ and $2n+2$. Thus he does not lose.

Now to show he wins at $\lambda<c$, he uses the same strategy. Then we get

\[x_1+\dots+x_{2n}\ge n\sqrt2\]

again, and since $\lambda<c$ we can choose $n$ such that $\lambda<\frac n{2n+1}\sqrt2$. This implies $n\sqrt2>\lambda(2n+1)$, so Alice loses her next turn and Bazza wins.

Thus Alice wins at $\lambda>c$, Bazza wins at $\lambda<c$ and neither can lose at $\lambda=c$, as desired.

Solution 2

Alice wins if $\lambda > \sqrt{2}/2$, Bazza wins if $\lambda < \sqrt{2}/2$, and it's a tie if $\lambda = \sqrt{2}/2$.

If $\lambda < \sqrt{2}/2$, then whatever Alice picks for $x_1$, Bazza picks $x_2 = \sqrt{2 - x_1^2}$. Then $x_1 + x_2 \geq \sqrt{2} > 2 \lambda$ by concavity, so Alice has no moves for $x_3$. We show later that this strategy also prevents loss from Bazza if $\lambda = \sqrt{2}/2$.

If $\lambda > \sqrt{2}/2$, then Alice picks $x_1 = x_3 = \ldots = x_{2k - 1} = 0$, whatever Bazza does, where $k$ is a positive integer to be determined later. Whatever choices Bazza have for $x_2, \ldots, x_{2k}$, at any moment Bazza can move, say at turn $2m$ where $m \leq k$, we have


\[ x_2^2 + x_4^2 + \ldots + x_{2m}^2 \leq 2m \iff \frac{x_2^2 + x_4^2 + \ldots + x_{2m}^2}{m} \leq 2. \]

By QM-AM, we then get


\[ \frac{x_2 + x_4 + \ldots + x_{2m}}{m} \leq \sqrt{2} \iff x_2 + x_4 + \ldots + x_{2m} \leq \sqrt{2} m < \lambda \cdot 2m. \]

So Alice can move. Now for $k$ large enough, Alice strikes back with


\[ x_{2k + 1} = \lambda(2k + 1) - (x_2 + x_4 + \ldots + x_n) \geq \lambda(2k + 1) - \sqrt{2} k > (2 \lambda - \sqrt{2}) k. \]

Then $x_{2k + 1}^2 \geq (2 \lambda - \sqrt{2})^2 k^2 > 2k + 1$ for $k$ very large, since $2 \lambda - \sqrt{2} > 0$. This immobilizes Bazza and wins the game for Alice.

Finally, if $\lambda = \sqrt{2}/2$, the same analysis as above shows that Alice holds on by picking $x_n = 0$ for each $n$ odd. It remains to show that Bazza holds on as well by picking $x_{2k} = \sqrt{2 - x_{2k - 1}^2}$ for each $k$. Indeed, this makes sure that $x_1^2 + x_2^2 + \ldots + x_{2k}^2 = 2k$ and also $x_{2k - 1} + x_{2k} \geq \sqrt{2}$ for each $k$. Thus Alice is forced to have $x_{2k + 1} \leq \sqrt{2}/2$, so Bazza can move again.

(In fact, Alice loses once she stops picking zero.)

Solution 3 Solution3
Solution 4 Solution4