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é

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).