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é¶
Corail et Joey jouent au jeu inékoalaté, un jeu à deux joueurs dont les règles dépendent d'un nombre réel \(\lambda\) strictement positif, connu des deux joueurs. Au \(n\)-ième tour du jeu :
-
si \(n\) est impair, Corail choisit un nombre réel \(x_n\) positif ou nul tel que
\[x_1 + x_2 + \cdots + x_n \leq \lambda n ;\] -
si \(n\) est pair, Joey choisit un nombre réel \(x_n\) positif ou nul tel que
\[x_1^2 + x_2^2 + \cdots + x_n^2 \leq n.\]
Tous les nombres choisis sont connus des deux joueurs. Si un joueur ne peut pas jouer, la partie s'arrête et l'autre joueur gagne.
Déterminer toutes les valeurs de \(\lambda\) pour lesquelles Corail a une stratégie gagnante, et toutes celles pour lesquelles Joey en a une.
Énoncé original (anglais)
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
à 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
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
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)
Si Joey n'a pas encore perdu, on a \(x_2^2 + x_4^2 + \cdots + x_{2k}^2 \leq 2k\), donc
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
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
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
au tour \(2\ell + 1\). On a vu que ces choix sont toujours légaux, quels que soient les coups de Joey. Or
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\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2024 C4 ★★☆☆☆ · OIM P5 : Turbo traverse une grille où se cachent des monstres, un par ligne intermédiaire : combien de tentatives lui faut-il ?
- 2024 C5 ★★★☆☆ : On efface des classes de congruence modulo \(2^k\) ; qui efface le dernier perd : pour quels \(N\) le premier gagne-t-il ?
- 2023 C5 ★★★☆☆ : Elisa ajoute des gemmes, une fée verrouille des coffres : Elisa garde les coffres équilibrés à une constante près.
- 2017 C5 ★★★☆☆ · OIM P3 : Un chasseur suit un lapin invisible avec un pisteur imprécis : peut-il rester à moins de \(100\) après \(10^9\) tours ?