Aller au contenu

Shortlist 2025, A3

Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Italy

Concepts : Jeux et stratégies gagnantes · Cauchy-Schwarz et lemme de Titu

Solution officielle : Shortlist officielle 2025 (avec solutions), section A3 (livret PDF)

Problème 5 de l'OIM 2025

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2025, où il était le problème 5 (jour 2).

Énoncé

Coral and Joey 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, the following happens:

  • If \(n\) is odd, Coral chooses a nonnegative real number \(x_n\) such that

    \[x_1 + x_2 + \cdots + x_n \leq \lambda n.\]

  • If \(n\) is even, Joey chooses a nonnegative real number \(x_n\) such that

    \[x_1^2 + x_2^2 + \cdots + x_n^2 \leq n.\]

All chosen numbers are known to both players. If a player cannot make a move, the game ends and the other player wins.

Determine all values of \(\lambda\) for which Coral has a winning strategy and all those for which Joey has a winning strategy.

Indices : les idées clés
  • Stratégies gagnantes : stratégies gloutonnes simples — Joey prend toujours le plus grand nombre permis, Coral joue \(0\) longtemps puis un seul grand coup.
  • Inégalité \(x + \sqrt{2 - x^2} \geq \sqrt 2\) sur \([0, \sqrt 2]\) : chaque paire de coups de la stratégie de Joey ajoute au moins \(\sqrt 2\) à la somme.
  • Cauchy-Schwarz (inégalité entre moyennes arithmétique et quadratique) : \(x_2 + x_4 + \cdots + x_{2k} \leq \sqrt{k(x_2^2 + \cdots + x_{2k}^2)} \leq k\sqrt 2\).
  • Le seuil \(\lambda = \frac{1}{\sqrt 2}\) apparaît en comparant \(k\sqrt 2\) à \(\lambda(2k+1)\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2025 (une solution).

Réponse.

Solution

  • Si \(\lambda < \frac{1}{\sqrt 2}\), Joey a une stratégie gagnante.
  • Si \(\lambda > \frac{1}{\sqrt 2}\), Coral a une stratégie gagnante.
  • Si \(\lambda = \frac{1}{\sqrt 2}\), aucun des deux joueurs n'a de stratégie gagnante.

On traite séparément les trois régimes.

(a) Cas \(\lambda < \frac{1}{\sqrt 2}\). Montrons que Joey gagne en choisissant à chaque tour le plus grand nombre possible, c'est-à-dire

\[x_{2k} = \sqrt{2 - x_{2k-1}^2}\]

à chaque tour pair (stratégie gagnante).

Au premier tour, Coral choisit \(x_1 \in [0, \lambda]\). Comme \(\lambda < \frac{1}{\sqrt 2}\), on a \(2 - x_1^2 \geq 0\), donc Joey peut choisir \(x_2 = \sqrt{2 - x_1^2}\), ce qui donne \(x_1^2 + x_2^2 = 2\).

Au troisième tour, Coral doit choisir \(x_3 \geq 0\) avec \(x_1 + x_2 + x_3 \leq 3\lambda\). Ou bien elle ne le peut pas et Joey gagne, ou bien

\[x_3 \leq 3\lambda - x_1 - \sqrt{2 - x_1^2} \leq 3\lambda - \sqrt 2 < \lambda.\]

On a utilisé que \(x + \sqrt{2 - x^2} \geq \sqrt 2\) pour tout \(x \in [0, \sqrt 2]\), ce qui s'établit en élevant au carré (cela équivaut à \(2x\sqrt{2 - x^2} \geq 0\)). Comme \(x_3 < \lambda\), on a \(2 - x_3^2 \geq 0\) et Joey peut choisir \(x_4 = \sqrt{2 - x_3^2}\), ce qui donne \(x_1^2 + x_2^2 + x_3^2 + x_4^2 = 4\).

En répétant cet argument, on montre par récurrence que, tant que Joey joue \(x_{2k} = \sqrt{2 - x_{2k-1}^2}\), Coral soit perd au tour suivant, soit doit choisir \(x_{2k+1} < \lambda\). Autrement dit, la stratégie de Joey est toujours légale (il a toujours un coup permis), et tous les nombres choisis par Coral sont inférieurs à \(\lambda\). D'autre part, la stratégie de Joey implique

\[x_1 + x_2 + \cdots + x_{2k} = \sum_{i=1}^{k} \left( x_{2i-1} + \sqrt{2 - x_{2i-1}^2} \right) \geq k\sqrt 2,\]

en utilisant de nouveau \(x + \sqrt{2 - x^2} \geq \sqrt 2\). Par conséquent, dès que \(k\) est assez grand pour que \(k\sqrt 2 > \lambda(2k+1)\) (un tel \(k\) existe car \(\lambda < \frac{1}{\sqrt 2}\), c'est-à-dire \(2\lambda < \sqrt 2\)), Coral n'a pas de coup légal au tour \(2k+1\) et Joey gagne.

(b) Cas \(\lambda > \frac{1}{\sqrt 2}\). La stratégie gagnante de Coral consiste à jouer \(x_n = 0\) pendant un certain nombre de tours, puis à jouer un nombre « grand ».

Montrons d'abord que Coral peut jouer \(0\) autant de tours consécutifs qu'elle le souhaite. C'est évident au premier tour. Après \(2k\) tours, si Coral a joué \(0\) aux tours \(1, 3, \ldots, 2k-1\), alors par Cauchy-Schwarz (inégalité entre moyenne arithmétique et moyenne quadratique)

\[x_1 + x_2 + \cdots + x_{2k} = x_2 + x_4 + \cdots + x_{2k} \leq \sqrt{k\,(x_2^2 + x_4^2 + \cdots + x_{2k}^2)}.\]

Si Joey n'a pas encore perdu, on a \(x_2^2 + x_4^2 + \cdots + x_{2k}^2 \leq 2k\), donc

\[x_1 + x_2 + \cdots + x_{2k} \leq k\sqrt 2 < \lambda(2k+1),\]

car \(\lambda > \frac{1}{\sqrt 2}\). Ainsi Coral peut légalement jouer \(x_{2k+1} = 0\) au tour \(2k+1\), quels que soient les choix de Joey. Plus précisément, elle peut jouer n'importe quel nombre positif vérifiant

\[x_{2k+1} \leq \lambda(2k+1) - k\sqrt 2 = k(2\lambda - \sqrt 2) + \lambda.\]

Cette borne devient arbitrairement grande quand \(k\) augmente, puisque \(2\lambda - \sqrt 2 > 0\).

Décrivons la stratégie gagnante de Coral. Soit \(\ell\) un entier assez grand pour que

\[\frac{\ell\sqrt 2 + \sqrt{2\ell + 2}}{2\ell + 1} < \lambda ;\]

un tel \(\ell\) existe car le membre de gauche tend vers \(\frac{1}{\sqrt 2} < \lambda\). Coral joue \(x_n = 0\) aux tours \(n = 1, 3, \ldots, 2\ell - 1\), puis

\[x_{2\ell+1} = \lambda(2\ell + 1) - \ell\sqrt 2\]

au tour \(2\ell + 1\). On a vu que ces choix sont toujours légaux, quels que soient les coups de Joey. Or

\[x_1^2 + x_2^2 + \cdots + x_{2\ell+1}^2 \geq x_{2\ell+1}^2 = \big(\lambda(2\ell+1) - \ell\sqrt 2\big)^2 > 2\ell + 2,\]

par définition de \(x_{2\ell+1}\) et de \(\ell\). Joey n'a donc aucun coup légal au tour \(2\ell + 2\) et perd.

(c) Cas \(\lambda = \frac{1}{\sqrt 2}\). Montrons qu'aucun joueur n'a de stratégie gagnante. Le même argument qu'en (a) montre que Joey peut toujours jouer légalement en choisissant \(x_{2k} = \sqrt{2 - x_{2k-1}^2}\) au tour \(2k\) ; il est donc sûr de ne jamais perdre. De même, l'argument de (b) montre que Coral peut toujours jouer légalement \(x_{2k+1} = 0\) au tour \(2k+1\) ; elle est donc sûre de ne jamais perdre. \(\blacksquare\)