IMO 2025 · Problem 5

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

  • If \(n\) is odd, Alice chooses a nonnegative real number \(x_n\) such that \[ x_1+x_2+\cdots+x_n\leq \lambda n. \]

  • If \(n\) is even, Bazza chooses a nonnegative real number \(x_n\) such that \[ x_1^2+x_2^2+\cdots+x_n^2\leq n. \]

If a player cannot choose a suitable number \(x_n\), 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 \(\lambda\) for which Alice has a winning strategy and all those for which Bazza has a winning strategy.

Official text of the problem. Official problem paper (PDF)

Answer

  • Alice has a winning strategy exactly when \(\displaystyle \lambda>\frac1{\sqrt2}\).
  • Bazza has a winning strategy exactly when \(\displaystyle 0<\lambda<\frac1{\sqrt2}\).
  • When \(\displaystyle \lambda=\frac1{\sqrt2}\), neither player has a winning strategy.

Solution

Write \[ S_n=\sum_{i=1}^{n}x_i,\qquad Q_n=\sum_{i=1}^{n}x_i^2, \] with \(S_0=Q_0=0\). Call turns \(2k-1\) and \(2k\) the \(k\)th pair of turns.

Bazza’s strategy when \(\lambda\leq 1/\sqrt2\). After Alice chooses \(a=x_{2k-1}\), Bazza chooses \[ b=x_{2k}=\sqrt{2-a^2}. \] We prove inductively that this is always a legal response and that, after every completed pair, \[ Q_{2k}=2k,\qquad S_{2k}\geq k\sqrt2. \]

These equalities and inequalities hold for \(k=0\). Suppose the first \(k-1\) pairs have been completed. If Alice has no legal move, Bazza has already won. Otherwise, her legal choice \(a\) satisfies \[ \begin{aligned} 0\leq a &\leq \lambda(2k-1)-S_{2k-2}\\ &\leq \lambda(2k-1)-(k-1)\sqrt2\\ &=\lambda+(k-1)(2\lambda-\sqrt2) \leq \lambda \leq \frac1{\sqrt2}. \end{aligned} \] Thus \(b=\sqrt{2-a^2}\) is well-defined and nonnegative. Moreover, \[ Q_{2k}=Q_{2k-2}+a^2+b^2=(2k-2)+2=2k, \] so Bazza’s response is legal. Since \(a,b\geq0\), \[ (a+b)^2=a^2+b^2+2ab\geq2, \] and hence \[ S_{2k}\geq (k-1)\sqrt2+\sqrt2=k\sqrt2. \] This proves the induction and, in particular, shows that Bazza can always prevent Alice from winning when \(\lambda\leq1/\sqrt2\).

If \(\lambda<1/\sqrt2\), choose a positive integer \(k\) such that \[ k(\sqrt2-2\lambda)>\lambda. \] If the game reaches the end of the \(k\)th pair, then \[ S_{2k}\geq k\sqrt2>\lambda(2k+1). \] Alice therefore has no legal move on turn \(2k+1\). Since Bazza never lacks a legal response, his strategy forces a win in finitely many turns.

Alice’s strategy when \(\lambda\geq1/\sqrt2\). First observe that Alice can safely choose zero for as many turns as she wishes. Indeed, if her first \(k\) choices are zero, then after Bazza’s \(k\)th move, \[ Q_{2k}=\sum_{j=1}^{k}x_{2j}^2\leq2k. \] By the Cauchy–Schwarz inequality, \[ S_{2k}=\sum_{j=1}^{k}x_{2j} \leq \sqrt{k\sum_{j=1}^{k}x_{2j}^2} \leq k\sqrt2 \leq \lambda(2k+1). \] Consequently, zero is again legal on Alice’s next turn. Her initial choice of zero is also legal, so this proves the assertion inductively. In particular, Bazza has no winning strategy when \(\lambda\geq1/\sqrt2\).

Now suppose that \(\lambda>1/\sqrt2\), and put \[ \delta=2\lambda-\sqrt2>0. \] Choose an integer \(k\geq1\) sufficiently large that \[ \lambda+\delta k>\sqrt{2k+2}. \] Such an integer exists; for example, any integer \(k>\max\{1,4/\delta^2\}\) works, since then \[ \delta k>2\sqrt{k}\geq\sqrt{2k+2}. \]

Alice chooses zero on her first \(k\) turns. As proved above, all these choices are legal, regardless of Bazza’s moves. On turn \(2k+1\), she chooses \[ x_{2k+1}=\lambda(2k+1)-S_{2k}. \] Using \(S_{2k}\leq k\sqrt2\), we obtain \[ x_{2k+1}\geq\lambda(2k+1)-k\sqrt2 =\lambda+\delta k >\sqrt{2k+2}. \] Thus her choice is nonnegative and legal, but \[ Q_{2k+1}\geq x_{2k+1}^2>2k+2. \] Bazza cannot satisfy his constraint on turn \(2k+2\), whatever nonnegative number he chooses. Alice therefore wins.

Finally, at \(\lambda=1/\sqrt2\), Bazza’s strategy above prevents Alice from winning, while Alice’s strategy of always choosing zero prevents Bazza from winning. Hence neither player has a winning strategy at this boundary value.

The solution was checked against the official IMO shortlist solutions.