Aller au contenu

Shortlist 2025, A8

Domaine : Algèbre · Difficulté : ★★★★★ · Proposé par : France

Concepts : Jeux et stratégies gagnantes · Polynômes : racines, relations de Viète, factorisation · AM-GM et moyennes

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

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Tim and Tam play a game. To start the game, Tim writes some nonzero real numbers, not necessarily distinct, on a blackboard. In each round, the following happens:

  • First, Tam chooses a polynomial \(P_k(x) = a_k x^k + a_{k-1} x^{k-1} + \cdots + a_1 x + a_0\) whose coefficients \(a_k, a_{k-1}, \ldots, a_1, a_0\) are all of the numbers currently written on the blackboard in some order. (For example, if the numbers on the blackboard are \(4, -3, 4\), then \(k = 2\) and Tam may choose the polynomial \(4x^2 - 3x + 4\) or \(-3x^2 + 4x + 4\) but not \(4x - 3\) or \(-3x^2 - 3x + 4\).)
  • Then, if the equation \(P_k(x) = 0\) has no real solutions, the game is stopped. Otherwise, Tim chooses a real number \(r\) such that \(P_k(r) = 0\) and writes it on the blackboard, so there is now one more number on the blackboard.

Determine whether Tim can ensure that the game is never stopped, no matter what Tam does.

Indices : les idées clés
  • Jeux et stratégies gagnantes : Tam gagne en enchaînant des états intermédiaires (que des nombres positifs ajoutés, puis une réserve de « grands » nombres positifs, puis un polynôme sans racine réelle).
  • Polynômes : racines, relations de Viète, factorisation : en plaçant les gros coefficients positifs sur les puissances paires, Tam empêche toute racine négative ; en contrôlant aussi les petits \(t > 0\), elle force les racines à être grandes, puis supprime toutes les racines réelles.
  • AM-GM et moyennes : \(Ct^i + Ct^{2n-i} \geq 2Ct^n\) permet à un bloc de coefficients positifs d'« absorber » un coefficient négatif au milieu (lemme 1.3).
  • Recollement de polynômes (solution 1) : l'ensemble \(G\) des \(t\) où une forme « à demi-extrémités » est positive se comporte bien par concaténation de suites de coefficients (lemme 1.2).
  • Suites alternées et dominées (solution 2) : coefficients en zigzag pour exclure les racines négatives, terme constant dominant (inégalité triangulaire) pour garder les racines loin de \(0\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions et deux remarques).

Réponse : non, Tim ne peut pas garantir que le jeu ne s'arrête jamais.

Remarques communes. Dans chaque tour, on note simplement \(P(x)\) le polynôme choisi par Tam. La stratégie de Tam se résume ainsi : (1) en choisissant le coefficient de \(x^{2j}\) plus grand que ses voisins pour chaque \(j\), elle empêche \(P\) d'avoir des racines négatives, de sorte qu'à partir d'un certain moment tous les nombres écrits sont positifs ; (2) en choisissant plus soigneusement les coefficients de l'étape (1), elle s'assure que les nombres écrits sont non seulement positifs, mais minorés par une constante strictement positive une infinité de fois : elle se constitue une réserve de « grands nombres positifs » ; (3) en choisissant les coefficients de sorte que chaque coefficient négatif soit entouré de nombreux grands nombres positifs, elle empêche aussi les racines positives, et le jeu s'arrête.

Solution 1

Outils. Pour une suite \(a_0, \ldots, a_{2n}\) de longueur impaire, on pose

\[F(a_0, \ldots, a_{2n}) = \left\{t : \sum_{i=0}^{2n} a_i t^i > 0\right\}, \qquad G(a_0, \ldots, a_{2n}) = \left\{t : \frac{a_0 + a_{2n}t^{2n}}{2} + \sum_{i=1}^{2n-1} a_i t^i \geq 0\right\}.\]

Si \(a_0, a_{2n} > 0\), alors \(G(a_0, \ldots, a_{2n}) \subseteq F(a_0, \ldots, a_{2n})\). Donc si les nombres du tableau sont, dans un certain ordre, \(a_0, \ldots, a_{2n}\) avec \(a_0, a_{2n} > 0\) et \(G(a_0, \ldots, a_{2n}) = \mathbb{R}\), alors \(F(a_0, \ldots, a_{2n}) = \mathbb{R}\) et Tam peut choisir \(P(x) = \sum_{i=0}^{2n} a_i x^i\), qui n'a pas de racine réelle : le jeu s'arrête.

Pour \(A > 0\), une suite \(a_0, \ldots, a_{2n}\) est \(A\)-séparée si \(a_i \geq A\) pour \(i\) pair et \(a_i \leq A\) pour \(i\) impair ; elle est séparée si elle est \(A\)-séparée pour un certain \(A > 0\). Toute suite de réels non nuls de longueur impaire contenant plus de nombres positifs que de négatifs peut être réordonnée en une suite séparée.

Lemme 1.1. Si \(A, B > 0\) et si \(a_0, \ldots, a_{2n}\) est \(A\)-séparée avec \(a_i \geq -B\) pour tout \(i\), alors \(t \in G(a_0, \ldots, a_{2n}) \subseteq F(a_0, \ldots, a_{2n})\) pour tout \(t \leq \frac{A}{2B}\).

Preuve. Notons \(P(t) = \frac{a_0 + a_{2n}t^{2n}}{2} + \sum_{i=1}^{2n-1} a_i t^i\). Pour \(t < 0\) (les termes pairs sont \(\geq At^i\), et pour \(i\) impair \(a_i t^i \geq At^i\) car \(t^i < 0\)) :

\[P(t) \geq \frac{A + At^{2n}}{2} + \sum_{i=1}^{2n-1} At^i = \frac{A}{2}\sum_{j=1}^{n} \left(t^j + t^{j-1}\right)^2 \geq 0.\]

Pour \(0 \leq t \leq \frac{A}{2B}\) :

\[P(t) \geq \frac{A + At^{2n}}{2} + \sum_{j=1}^{n-1} At^{2j} - \sum_{j=1}^{n} Bt^{2j-1} = \frac{A}{2}t^{2n} + \frac{A}{2} - Bt + \sum_{j=1}^{n-1} (A - Bt)t^{2j} \geq 0.\]

Ainsi \(P(t) \geq 0\) pour tout \(t \leq \frac{A}{2B}\), d'où le lemme puisque \(a_0, a_{2n} > 0\). \(\square\)

En particulier, \(t \in G \subseteq F\) pour tout \(t \leq 0\) dès que la suite est séparée, et \(F = G = \mathbb{R}\) si de plus tous les \(a_i\) sont positifs.

Lemme 1.2. Si \(0 \leq m \leq n\), alors \(G(a_0, \ldots, a_{2m}) \cap G(a_{2m}, \ldots, a_{2n}) \subseteq G(a_0, \ldots, a_{2n})\) pour toute suite \(a_0, \ldots, a_{2n}\).

Preuve. Si \(m = 0\) ou \(m = n\), c'est clair. Sinon, si \(t\) est dans les deux ensembles, alors

\[\frac{a_0 + a_{2n}t^{2n}}{2} + \sum_{i=1}^{2n-1} a_i t^i = \left(\frac{a_0 + a_{2m}t^{2m}}{2} + \sum_{i=1}^{2m-1} a_i t^i\right) + t^{2m}\left(\frac{a_{2m} + a_{2n}t^{2(n-m)}}{2} + \sum_{i=2m+1}^{2n-1} a_i t^{i-2m}\right)\]

est positif ou nul, donc \(t \in G(a_0, \ldots, a_{2n})\). \(\square\)

En particulier, \(G(a_0, \ldots, a_{2m}) \subseteq G(a_0, \ldots, a_{2n})\) si \(G(a_{2m}, \ldots, a_{2n}) = \mathbb{R}\).

Lemme 1.3. Si \(n\) est impair et si \(a_0, \ldots, a_{2n}\) est une suite séparée telle que \(a_i \geq C\) pour \(i \neq n\) et \((2n - 1)C + a_n \geq 0\) pour un certain \(C > 0\), alors \(G(a_0, \ldots, a_{2n}) = \mathbb{R}\).

Preuve. La suite étant séparée, \(t \in G\) pour tout \(t \leq 0\). Pour \(t > 0\), par AM-GM (\(Ct^i + Ct^{2n-i} \geq 2Ct^n\) et \(\frac{C + Ct^{2n}}{2} \geq Ct^n\)),

\[\frac{a_0 + a_{2n}t^{2n}}{2} + \sum_{i=1}^{2n-1} a_i t^i \geq \frac{C + Ct^{2n}}{2} + \sum_{i=1}^{n-1}\left(Ct^i + Ct^{2n-i}\right) + a_n t^n \geq \left((2n - 1)C + a_n\right)t^n \geq 0,\]

donc \(G = \mathbb{R}\). \(\square\)

Le livret écrit \(Ct^i + Ct^{2m-i} \geq 2Ct^n\) ; il faut lire \(Ct^{2n-i}\).

La stratégie de Tam. Elle procède par étapes, chacune visant un état intermédiaire ; le jeu peut s'arrêter avant, ce qui ne gêne pas Tam. Notons que \(0\) n'est jamais écrit, puisque les nombres initiaux sont non nuls.

État 1 : le tableau contient un nombre impair de réels, avec plus de positifs que de négatifs.

Stratégie. On suppose l'état 1 non encore atteint.

  • S'il y a un nombre pair de réels, tous négatifs, Tam choisit \(P\) arbitrairement.
  • S'il y a un nombre impair \(2n + 1\) de réels (donc plus de négatifs que de positifs), Tam choisit \(P(x) = \sum_{i=0}^{2n} a_i x^i\) de sorte que \(-a_0, \ldots, -a_{2n}\) soit séparée. Le lemme 1.1 donne \(P(r) < 0\) pour tout \(r \leq 0\).
  • S'il y a un nombre pair \(2n + 2\) de réels dont au moins un positif, Tam choisit \(P(x) = \sum_{i=0}^{2n+1} a_i x^i\) avec \(-a_0, \ldots, -a_{2n}\) séparée et \(a_{2n+1} > 0\). Le lemme 1.1 donne \(P(r) = a_{2n+1}r^{2n+1} + \sum_{i=0}^{2n} a_i r^i < 0\) pour tout \(r \leq 0\).

Précision ajoutée : dans le troisième cas, si au moins \(n + 2\) des \(2n + 2\) nombres sont positifs, on ne peut pas rendre \(-a_0, \ldots, -a_{2n}\) séparée, mais alors n'importe quel coup de Tim mène à l'état 1 ; sinon, il reste au plus \(n\) positifs parmi \(a_0, \ldots, a_{2n}\) et la séparation est possible.

Dans les deux derniers cas, Tim n'écrit que des nombres positifs. En répétant, le premier cas se produit au plus une fois, et Tam atteint l'état 1. \(\square\)

État 2 : les nombres du tableau peuvent être ordonnés en \(a_0, \ldots, a_{2n_0}, \ldots, a_{2n_1}, \ldots, a_{2n_\ell}\) de sorte que \(a_0, \ldots, a_{2n_0}\) soit une suite séparée de réels positifs et que \(a_{2n_{j-1}}, \ldots, a_{2n_j}\) vérifie les hypothèses du lemme 1.3 pour chaque \(1 \leq j \leq \ell\).

Stratégie. Si tous les nombres sont positifs, l'état 2 est atteint avec \(\ell = 0\). Sinon, soit \(C = \frac{A}{2B}\), où \(-B < 0\) est le plus petit nombre du tableau et \(A > 0\) est tel que les nombres du tableau peuvent être rangés en une suite \(A\)-séparée. Si Tam choisit \(P\) à chaque tour de sorte que seuls des nombres positifs soient ajoutés, et que des nombres supérieurs à \(C\) soient ajoutés une infinité de fois, alors le jeu finit par atteindre l'état 2 (précision ajoutée : chaque nombre négatif peut alors être placé au milieu d'un bloc de \(2n+1\) termes dont les \(2n\) autres sont \(\geq C\), avec \(n\) impair assez grand pour que \((2n-1)C\) dépasse sa valeur absolue).

  • Avec un nombre pair \(2n + 2\) de réels, Tam choisit \(P(x) = \sum_{i=0}^{2n+1} a_i x^i\) avec \(a_0, \ldots, a_{2n}\) séparée et \(a_{2n+1} < 0\). Le lemme 1.1 donne \(P(r) = a_{2n+1}r^{2n+1} + \sum_{i=0}^{2n} a_i r^i > 0\) pour tout \(r \leq 0\) : le nombre ajouté est positif.
  • Avec un nombre impair \(2n + 1\) de réels, Tam choisit \(P(x) = \sum_{i=0}^{2n} a_i x^i\) avec \(a_0, \ldots, a_{2n}\) séparée, \(a_0, \ldots, a_{2m}\) \(A\)-séparée et \(\geq -B\), et \(a_{2m}, \ldots, a_{2n} > 0\), pour un certain \(0 \leq m \leq n\). C'est possible au départ par construction, et cela le reste car seuls des nombres positifs sont ajoutés. Le lemme 1.1 donne \(t \in G(a_0, \ldots, a_{2m})\) pour tout \(t \leq C\) et \(G(a_{2m}, \ldots, a_{2n}) = \mathbb{R}\), donc par le lemme 1.2, \(t \in G(a_0, \ldots, a_{2n}) \subseteq F(a_0, \ldots, a_{2n})\) pour tout \(t \leq C\) : le nombre ajouté est supérieur à \(C\).

En répétant ces choix, Tam atteint l'état 2. \(\square\)

État 3 : le jeu est arrêté.

Stratégie. Dans l'état 2, avec l'ordre \(a_0, \ldots, a_{2n_0}, \ldots, a_{2n_\ell}\), les lemmes 1.1 et 1.3 donnent \(G(a_0, \ldots, a_{2n_0}) = \mathbb{R}\) et \(G(a_{2n_{j-1}}, \ldots, a_{2n_j}) = \mathbb{R}\) pour \(1 \leq j \leq \ell\). En appliquant plusieurs fois le lemme 1.2, \(G(a_0, \ldots, a_{2n_\ell}) = \mathbb{R}\). Comme \(a_0, a_{2n_\ell} > 0\), on a aussi \(F(a_0, \ldots, a_{2n_\ell}) = \mathbb{R}\), et Tam choisit \(P(x) = \sum_{i=0}^{2n_\ell} a_i x^i\), qui n'a pas de racine réelle. \(\square\)

Avec cette stratégie, Tam arrête le jeu quoi que fasse Tim : Tim ne peut pas garantir que le jeu dure indéfiniment. \(\blacksquare\)

Solution 2

On réalise autrement les étapes (1) et (2), sans suites séparées : on se contente de suites de coefficients alternées et l'on obtient de grands nombres positifs en choisissant un terme constant grand. Le cas où tous les nombres du tableau ont le même signe se traite comme dans la solution 1 ; on suppose désormais qu'il y a des nombres des deux signes.

Une suite \(b_0, \ldots, b_k\) de réels non nuls est alternée si \(b_0 > 0\), \(b_i \geq b_{i+1}\) pour \(i\) pair, \(b_i \leq b_{i+1}\) pour \(i\) impair (\(0 \leq i < k\)), et \((-1)^k b_k > 0\).

Lemme 2.1. Si \(b_0, \ldots, b_k\) est alternée et \(P(x) = \sum_{i=0}^{k} b_i x^i\), alors \(P(t) > 0\) pour tout \(t \leq 0\). En particulier, toutes les racines réelles de \(P\) sont positives.

Preuve. On montre plus fort : \(Q(x) = \frac{b_0}{2} + \sum_{i=1}^{k} b_i x^i\) vérifie \(Q(t) > 0\) pour tout \(t \leq 0\), par récurrence sur \(k\) ; les cas \(k = 0\) et \(k = 1\) sont clairs. Si \(b_1 < 0\), la suite \(-b_1, \ldots, -b_k\) est alternée, et pour \(t \leq 0\),

\[Q(t) = \frac{b_0 + b_1 t}{2} + t\left(\frac{b_1}{2} + \sum_{i=1}^{k-1} b_{i+1}t^i\right) > t\left(\frac{b_1}{2} + \sum_{i=1}^{k-1} b_{i+1}t^i\right) \geq 0,\]

la parenthèse étant l'opposé du « \(Q\) » associé à \(-b_1, \ldots, -b_k\), donc négative par hypothèse de récurrence. Si \(b_1 > 0\), alors \(b_0 \geq b_1\) et \(b_2 \geq b_1 > 0\), donc \(k \geq 2\) et \(b_2, \ldots, b_k\) est alternée ; pour \(t \leq 0\),

\[Q(t) = \frac{b_0 - b_1}{2} + \frac{b_2 - b_1}{2}t^2 + \frac{b_1}{2}(t + 1)^2 + t^2\left(\frac{b_2}{2} + \sum_{i=1}^{k-2} b_{i+2}t^i\right) > 0. \qquad \square\]

Précision ajoutée : dans le lemme 2.1, le livret écrit « \(Q(t) > 0\) pour tout \(r \leq 0\) » et une seconde inégalité stricte ; il faut lire \(t \leq 0\), et la seconde inégalité est large (égalité en \(t = 0\)).

Comme les nombres du tableau n'ont pas tous le même signe, on peut toujours les ranger en une suite alternée. Par le lemme 2.1, Tam force donc Tim à n'écrire que des nombres positifs : c'est l'étape (1).

Une suite \(b_0, \ldots, b_k\) de réels non nuls est dominée par son premier terme si \(|b_0| \geq |b_1|, \ldots, |b_k|\).

Lemme 2.2. Si \(b_0, \ldots, b_k\) est dominée par son premier terme et \(P(x) = \sum_{i=0}^{k} b_i x^i\), alors \(P(t) \neq 0\) pour \(|t| \leq \frac{1}{2}\) ; toutes les racines réelles de \(P\) sont de valeur absolue \(> \frac{1}{2}\).

Preuve. Par l'inégalité triangulaire, pour \(|t| \leq \frac{1}{2}\),

\[|P(t)| = \left|\sum_{i=0}^{k} b_i t^i\right| \geq |b_0| - \sum_{i=1}^{k} |b_i|\,|t|^i \geq |b_0| - \sum_{i=1}^{k} \frac{|b_0|}{2^i} = \frac{|b_0|}{2^k} > 0. \qquad \square\]

Quand le tableau contient un nombre pair de réels (de signes non tous égaux), Tam peut les ranger en \(a_0, \ldots, a_k\) de sorte que \(a_0, \ldots, a_k\) ou \(-a_0, \ldots, -a_k\) soit à la fois alternée et dominée par son premier terme (selon le signe du nombre de plus grande valeur absolue). Par les lemmes 2.1 et 2.2, Tam force Tim à écrire un nombre supérieur à \(\frac{1}{2}\) un tour sur deux : c'est l'étape (2). (La solution 1 réalise l'étape (2) quand le nombre de réels est impair, celle-ci quand il est pair.)

L'étape (3) se fait comme dans la solution 1, sans avoir besoin des suites séparées : dans la suite \(a_0, \ldots, a_{2n_0}, \ldots, a_{2n_\ell}\) de la solution 1, on peut imposer que les sous-suites \(a_0, \ldots, a_{2n_0}\) et \(a_{2n_{i-1}}, \ldots, a_{2n_i}\) soient alternées plutôt que séparées, et la preuve fonctionne de la même façon. \(\blacksquare\)

Remarques

Remarque 1 (nombres nuls). La proposition originale n'imposait pas que les nombres initiaux soient non nuls. Cela ne change pas grand-chose : Tam peut toujours mettre les \(0\) comme coefficients dominants de \(P\), de sorte qu'ils ne comptent pas. Le comité a jugé la formulation actuelle plus adaptée, cette complication n'apportant rien.

Remarque 2 (version entière). Le jeu peut se jouer avec des entiers non nuls (coefficients et racines). Cette variante est nettement plus facile et admet d'autres stratégies pour Tam :

  • Tam numérote les nombres initiaux \(b_0, \ldots, b_\ell\) et choisit à chaque tour \(P_k(x) = \sum_{i=0}^{k} b_i x^{k-i}\), puis appelle \(b_{k+1}\) la racine entière choisie par Tim ; ainsi \(P_{k+1}(x) = xP_k(x) + b_{k+1}\). De \(0 = P_{k+1}(b_{k+2}) = b_{k+2}P_k(b_{k+2}) + b_{k+1}\) on tire \(b_{k+2} \mid b_{k+1}\), donc \(|b_k|\) est constant à partir d'un rang. Comme \(P_k(b_{k+2})\) et \(P_{k+1}(b_{k+2})\) ne peuvent être nuls tous les deux, on obtient \(b_k + b_{k+1} = 0\) et \(b_k = b_{k+2}\) pour \(k\) grand ; puis \(0 = P_{k+1}(b_k) = b_k^2 P_{k-1}(b_k) + b_k^2 + b_{k+1} = b_k^2 + b_{k+1}\), d'où \(b_k^2 = -b_{k+1} = b_k\), donc \(b_k = 1\) pour tout \(k\) grand, ce qui contredit \(b_k + b_{k+1} = 0\).
  • Tam trie les nombres initiaux \(b_0, \ldots, b_k\) par valeur absolue croissante et choisit \(P(x) = \sum_{i=0}^{k} b_i x^i\). Pour \(|r| \geq 2\), l'inégalité triangulaire donne \(|P(r)| \geq |b_k|\left(|r|^k - \sum_{i=0}^{k-1} |r|^i\right) > 0\) : les seules racines entières possibles sont \(\pm 1\). Si Tim écrit \(b\) avec \(|b| = 1\), Tam choisit \(P_{k+1}(x) = xP(x) + b\) ; comme \(|b| \leq |b_0| \leq \cdots \leq |b_k|\), le même argument montre que ses racines entières sont \(\pm 1\). Si Tim écrit \(c\) avec \(|c| = 1\), alors modulo \(2\) : \(0 \equiv P_{k+1}(c) \equiv P_{k+1}(1) \equiv P(1) + 1 \equiv P(b) + 1 \equiv 1\), contradiction.