Aller au contenu

Shortlist 2020, A5

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

Concepts : Polynômes : racines, relations de Viète, factorisation

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 21 (page 23 du PDF)

Énoncé

Une magicienne veut réaliser le tour suivant. Elle annonce au public un entier \(n\) strictement positif et \(2n\) nombres réels \(x_1 < \cdots < x_{2n}\). Un spectateur choisit alors secrètement un polynôme \(P(x)\) de degré \(n\) à coefficients réels, calcule les \(2n\) valeurs \(P(x_1), \ldots, P(x_{2n})\) et les écrit au tableau dans l'ordre croissant (au sens large). La magicienne annonce ensuite au public le polynôme secret.

La magicienne peut-elle trouver une stratégie pour réaliser ce tour ?

Énoncé original (anglais)

A magician intends to perform the following trick. She announces a positive integer \(n\), along with \(2n\) real numbers \(x_1 < \cdots < x_{2n}\), to the audience. A member of the audience then secretly chooses a polynomial \(P(x)\) of degree \(n\) with real coefficients, computes the \(2n\) values \(P(x_1), \ldots, P(x_{2n})\), and writes down these \(2n\) values on the blackboard in non-decreasing order. After that the magician announces the secret polynomial to the audience.

Can the magician find a strategy to perform such a trick?

Indices : les idées clés
  • Construire deux polynômes indiscernables : il suffit de trouver \(P \neq Q\) de degré \(n\) qui produisent la même liste triée de valeurs.
  • Algèbre linéaire : \(n\) équations linéaires homogènes à \(n + 1\) inconnues (les coefficients) ont une solution non nulle.
  • Racines d'un polynôme : par le théorème des valeurs intermédiaires, \(P\) a une racine dans chaque \([x_{2i-1}, x_{2i}]\), donc \(n\) racines, et il est exactement de degré \(n\).
  • Symétrie \(Q = -P\) : si \(P(x_{2i-1}) = -P(x_{2i})\), alors \(P\) et \(-P\) donnent les mêmes valeurs, permutées.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2020 (une solution et une remarque).

Réponse : non, la magicienne ne peut pas réussir son tour.

Solution

Soient \(x_1 < x_2 < \cdots < x_{2n}\) les réels choisis par la magicienne. Nous allons construire deux polynômes distincts \(P(x)\) et \(Q(x)\), tous deux de degré \(n\), pour lesquels le spectateur écrira la même suite au tableau. La magicienne ne pourra donc pas distinguer \(P\) de \(Q\).

Affirmation. Il existe un polynôme \(P(x)\) de degré \(n\) tel que \(P(x_{2i-1}) + P(x_{2i}) = 0\) pour \(i = 1, 2, \ldots, n\).

Preuve. On cherche un polynôme \(a_nx^n + \cdots + a_1x + a_0\) dont les coefficients vérifient le système

\[\left\{\begin{aligned} &(x_1^n + x_2^n)a_n + (x_1^{n-1} + x_2^{n-1})a_{n-1} + \cdots + 2a_0 = 0 \\ &(x_3^n + x_4^n)a_n + (x_3^{n-1} + x_4^{n-1})a_{n-1} + \cdots + 2a_0 = 0 \\ &\qquad \cdots \\ &(x_{2n-1}^n + x_{2n}^n)a_n + (x_{2n-1}^{n-1} + x_{2n}^{n-1})a_{n-1} + \cdots + 2a_0 = 0 \end{aligned}\right.\]

On utilise le fait classique qu'un système linéaire homogène de \(n\) équations à \(n + 1\) inconnues admet une solution non nulle (cela se prouve par récurrence sur \(n\), en éliminant les variables). On obtient ainsi un polynôme non nul \(P(x)\), de degré au plus \(n\), tel que \(P(x_{2i-1}) + P(x_{2i}) = 0\) pour tout \(i = 1, 2, \ldots, n\). Alors \(P(x_{2i-1})\) et \(P(x_{2i})\) sont de signes opposés (ou nuls), donc, par le théorème des valeurs intermédiaires, \(P\) a une racine sur chaque segment \([x_{2i-1}, x_{2i}]\) : cela fait \(n\) racines distinctes (les segments sont disjoints). Comme \(P\) est non nul et de degré au plus \(n\), on obtient \(\deg P = n\). \(\square\)

Prenons un polynôme \(P(x)\) donné par l'affirmation, et posons \(Q(x) = -P(x)\). D'après les propriétés de \(P\),

\[P(x_{2i-1}) = Q(x_{2i}) \quad \text{et} \quad Q(x_{2i-1}) = P(x_{2i}) \qquad \text{pour tout } i = 1, 2, \ldots, n.\]

Ainsi les deux listes de valeurs sont les mêmes à l'ordre près, et une fois rangées dans l'ordre croissant elles coïncident. Enfin \(P \neq -P = Q\) et \(\deg Q = \deg P = n\). La magicienne ne peut donc pas trouver de stratégie. \(\blacksquare\)

Remarques

Remarque 1. On peut montrer que, pour tout entier \(n \geq 1\), la magicienne peut choisir \(2n + 1\) réels distincts de façon à réussir le tour. Mieux : elle peut le réussir avec presque tous les \((2n + 1)\)-uplets de réels (en un sens convenable).

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2025 A5 ★★★☆☆ : Pour quels \(n\) le polynôme \(x^n + y^n + z^n - x^{n-2}yz - xy^{n-2}z - xyz^{n-2}\) se factorise-t-il ?
  • 2022 A5 ★★★☆☆ : Pour quels \(n\) les différences de \(n\) réels peuvent-elles être exactement les puissances \(r, r^2, \ldots\) d'un même nombre ?
  • 2019 A5 ★★★☆☆ : Pour des réels distincts, la somme sur \(i\) des produits \(\prod_{j \neq i} (1 - x_i x_j)/(x_i - x_j)\) vaut \(0\) ou \(1\) selon la parité de \(n\).
  • 2006 A6 ★★★☆☆ · OIM P3 : Trouver la meilleure constante \(M\) pour majorer \(|ab(a^2 - b^2) + bc(b^2 - c^2) + ca(c^2 - a^2)|\) par \(M(a^2 + b^2 + c^2)^2\).