Shortlist 2015, A6¶
Domaine : Algèbre · Difficulté : ★★★★★ · Proposé par : Canada
Concepts : Sommes, télescopage et transformation d'Abel · Polynômes : racines, relations de Viète, factorisation
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 20 (page 21 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(n\) be a fixed integer with \(n \geq 2\). We say that two polynomials \(P\) and \(Q\) with real coefficients are block-similar if for each \(i \in \{1, 2, \ldots, n\}\) the sequences
are permutations of each other.
(a) Prove that there exist distinct block-similar polynomials of degree \(n + 1\).
(b) Prove that there do not exist distinct block-similar polynomials of degree \(n\).
Indices : les idées clés
- Sommes, télescopage et transformation d'Abel (solution 1) : le polynôme \(\Sigma_F(m) = F(1) + \cdots + F(m)\) s'annule en \(0, k, \ldots, nk\) pour \(F = P - Q\) et \(F = P^2 - Q^2\) ; un polynôme dont les sommes partielles s'annulent ainsi s'écrit \(T(x)G(x) - T(x-1)G(x-1)\).
- Polynômes : racines, relations de Viète, factorisation : compter les racines face au degré, divisibilité et PGCD de polynômes scindés à racines simples, factorisation de \(P\) une fois toutes ses racines connues (solution 2).
- Valeurs intermédiaires : sur chaque bloc, \(P - Q\) prend une valeur \(\leq 0\) et une valeur \(\geq 0\), donc s'annule ; on en déduit une racine par bloc et l'on montre que \(P + Q\) est constant.
- Se ramener à \(Q = -P\) : une fois \(P + Q\) constant, il reste à voir que \(P\) et \(-P\) ne peuvent pas être semblables par blocs, en comparant les valeurs au milieu ou au bord du premier bloc.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et trois remarques).
Solution 1¶
On note \(k = 2015 = 2\ell + 1\).
Partie (a). Considérons les polynômes de degré \(n + 1\)
Comme \(Q(x) = P(x - 1)\) et \(P(0) = P(k) = \cdots = P(nk) = 0\), sur chaque bloc \(\{ik - k + 1, \ldots, ik\}\) les valeurs de \(Q\) sont \(P(ik - k) = 0, P(ik - k + 1), \ldots, P(ik - 1)\), et celles de \(P\) sont \(P(ik - k + 1), \ldots, P(ik - 1), P(ik) = 0\) : ce sont les mêmes à l'ordre près. Ces polynômes distincts sont donc semblables par blocs.
Partie (b). Pour tout polynôme \(F\) et tout entier \(m \geq 0\), posons \(\Sigma_F(m) = \sum_{i=1}^{m} F(i)\) ; en particulier \(\Sigma_F(0) = 0\). Pour tout entier \(d \geq 0\), la somme \(\sum_{i=1}^{m} i^d\) est un polynôme en \(m\) de degré \(d + 1\) ; on peut donc voir \(\Sigma_F\) comme un polynôme réel de degré \(\deg F + 1\) (avec \(\Sigma_F = 0\) si \(F = 0\)), et l'évaluer en tout réel.
Supposons par l'absurde qu'il existe deux polynômes distincts \(P\) et \(Q\) de degré \(n\) semblables par blocs. La somme des valeurs (ou des carrés des valeurs) sur chaque bloc est la même pour \(P\) et \(Q\), donc les polynômes \(\Sigma_{P-Q}\) et \(\Sigma_{P^2-Q^2}\) s'annulent en \(0, k, 2k, \ldots, nk\). On pose
Lemme. Soit \(F\) un polynôme non nul tel que \(0, k, 2k, \ldots, nk\) soient racines de \(\Sigma_F\). Alors \(\deg F \geq n\), et il existe un polynôme \(G\) de degré \(\deg F - n\) tel que \(F(x) = T(x)G(x) - T(x-1)G(x-1)\).
Preuve. Si \(\deg F < n\), alors \(\Sigma_F\) a au moins \(n + 1\) racines et un degré inférieur à \(n + 1\) ; donc \(\Sigma_F = 0\), puis \(F = 0\), ce qui est exclu. Ainsi \(\deg F \geq n\). L'hypothèse donne \(\Sigma_F(x) = T(x)G(x)\) pour un polynôme \(G\) de degré \(\deg \Sigma_F - (n+1) = \deg F - n\). Posons \(F_1(x) = T(x)G(x) - T(x-1)G(x-1)\). Pour tout entier \(m \geq 1\), par télescopage,
donc le polynôme \(\Sigma_{F - F_1} = \Sigma_F - \Sigma_{F_1}\) a une infinité de racines : il est nul, et \(F = F_1\). \(\square\)
On applique d'abord le lemme au polynôme non nul \(R_1 = P - Q\). Son degré est au plus \(n\), donc exactement \(n\), et \(G\) est une constante : \(R_1(x) = \alpha\big(T(x) - T(x-1)\big)\) avec \(\alpha \neq 0\).
Montrons ensuite que \(S = P + Q\) est constant. Sinon, \(R_2 = P^2 - Q^2 = R_1 S\) est non nul et vérifie l'hypothèse du lemme ; comme \(n < \deg R_1 + \deg S = \deg R_2 \leq 2n\), le lemme donne
Le polynôme \(R_1 = \alpha\big(T(x) - T(x-1)\big)\) divise
donc \(R_1(x) \mid T(x)\big(G(x) - G(x-1)\big)\). Or
car \(T(x)\) et \(T(x-1)\) sont produits de facteurs du premier degré à racines toutes distinctes. Donc \(R_1(x) \mid G(x) - G(x-1)\), ce qui est impossible : \(G(x) - G(x-1)\) est un polynôme non nul de degré \(< n = \deg R_1\).
Ainsi \(S\) est une constante \(\beta\). Les polynômes \((2P - \beta)/\alpha\) et \((2Q - \beta)/\alpha\) sont encore semblables par blocs et distincts ; en les substituant à \(P\) et \(Q\), on se ramène à \(P(x) = -Q(x) = T(x) - T(x-1)\). Montrons que c'est impossible.
Pour \(i = 1, \ldots, n\), les points \(ik - k + 1\) et \(ik - 1\) sont strictement entre deux racines consécutives de \(T\), donc \(T(ik - k + 1)\) et \(T(ik - 1)\) ont le même signe. Ainsi \(P(ik - k + 1) = T(ik - k + 1)\) et \(P(ik) = -T(ik - 1)\) sont de signes opposés, et \(P\) a une racine dans chacun des \(n\) segments \([ik - k + 1, ik]\) ; comme \(\deg P = n\), exactement une dans chacun.
La suite \(P(1), P(2), \ldots, P(k)\) change donc de signe exactement une fois. D'autre part, \(P\) et \(-P\) étant semblables par blocs, elle a autant de termes positifs que de termes négatifs. Comme \(k = 2\ell + 1\) est impair, le terme du milieu est nul : \(P(\ell + 1) = 0\), c'est-à-dire \(T(\ell + 1) = T(\ell)\). C'est faux, car
l'inégalité stricte venant de \(n \geq 2\). Contradiction. \(\blacksquare\)
Solution 2¶
On donne un autre argument pour la partie (b). Supposons qu'il existe deux polynômes distincts \(P\) et \(Q\) de degré \(n\) semblables par blocs. Posons \(R = P - Q\) et \(S = P + Q\) ; notons \(I_i\) le segment \([(i-1)k + 1, ik]\) et \(Z_i = \{(i-1)k + 1, \ldots, ik\}\) l'ensemble de ses points entiers.
Étape 1 : \(R\) a exactement une racine dans chaque \(I_i\), et ces racines sont simples. Fixons \(i\) et choisissons \(p_-, p_+ \in Z_i\) tels que \(P(p_-) = \min_{Z_i} P\) et \(P(p_+) = \max_{Z_i} P\). Comme les valeurs de \(Q\) sur \(Z_i\) sont celles de \(P\) permutées, \(R(p_-) = P(p_-) - Q(p_-) \leq 0\) et \(R(p_+) \geq 0\). Par continuité (valeurs intermédiaires), \(R\) a une racine entre \(p_-\) et \(p_+\), donc dans \(I_i\). Ainsi \(R\) a au moins une racine dans chacun des \(n\) segments disjoints \(I_i\) ; comme \(R\) est non nul de degré au plus \(n\), il en a exactement une dans chacun, et elles sont simples.
Étape 2 : \(S\) est constant.
Affirmation. Pour tout \(i\), la suite \(S\big((i-1)k + 1\big), S\big((i-1)k + 2\big), \ldots, S(ik)\) n'est pas strictement croissante.
Preuve. Par symétrie, on peut supposer \(P(ik) \leq Q(ik)\). Prenons \(p_-, p_+\) comme à l'étape 1. Si \(P(p_+) = P(p_-)\), \(P\) est constant sur \(Z_i\), donc tous les points de \(Z_i\) sont racines de \(R\), ce qui est exclu ; ainsi \(p_+ \neq p_-\). Si \(p_- > p_+\), alors \(S(p_-) = P(p_-) + Q(p_-) \leq Q(p_+) + P(p_+) = S(p_+)\) (car \(P(p_-) = \min_{Z_i} Q \leq Q(p_+)\) et \(Q(p_-) \leq \max_{Z_i} Q = P(p_+)\)), et l'affirmation est vraie.
Montrons que le cas \(p_- < p_+\) est impossible. Si \(P(p_+) > Q(p_+)\), alors \(R(p_-) \leq 0\), \(R(p_+) > 0\) et \(R(ik) \leq 0\), donc \(R\) a une racine dans \([p_-, p_+)\) et une dans \((p_+, ik]\), ce qui contredit l'étape 1. Reste le cas \(p_- < p_+\) et \(P(p_+) = Q(p_+)\) : \(p_+\) est alors l'unique racine de \(R\) dans \(I_i\). Si \(p_+ = ik\), les valeurs de \(R\) sur \(Z_i \setminus \{ik\}\) sont toutes non nulles et de même signe, ce qui est absurde car leur somme est nulle. Enfin, si \(p_- < p_+ < ik\), alors \(R(p_-)\) et \(R(ik)\) sont tous deux strictement négatifs, donc \(R\) a un nombre pair de racines (comptées avec multiplicité) dans \([p_-, ik]\), ce qui contredit encore l'étape 1. \(\square\)
De même, la suite des valeurs de \(S\) sur \(Z_i\) n'est pas strictement décroissante. Le polynôme \(\Delta S(x) = S(x) - S(x-1)\) prend donc sur \(Z_i \setminus \{(i-1)k + 1\}\) au moins une valeur \(\geq 0\) et au moins une valeur \(\leq 0\) : il a une racine dans \(I_i\). Ainsi \(\Delta S\) a au moins \(n\) racines alors que son degré est \(< n\) : il est identiquement nul, et \(S\) est une constante \(\beta\).
Étape 3. Les polynômes \(P - \beta/2\) et \(Q - \beta/2\) sont encore semblables par blocs et distincts ; on peut donc supposer \(P = -Q\). Alors \(R = 2P\), et \(P\) a exactement une racine dans chaque \(I_i\). D'autre part, \(P\) et \(-P\) prennent le même nombre de valeurs positives sur \(Z_i\), donc \(P\) a autant de valeurs positives que négatives sur \(Z_i\). Comme \(k\) est impair, \(Z_i\) contient exactement une racine de \(P\), et cette racine est au centre de \(Z_i\). On connaît ainsi les \(n\) racines de \(P\) :
Pour tout \(t \in Z_1 \setminus \{1\}\),
donc \(P(1) \neq -P(t)\) pour tout \(t \in Z_1\) (y compris \(t = 1\), car \(P(1) \neq 0\)). Ainsi \(P\) et \(-P\) ne sont pas semblables par blocs : contradiction. \(\blacksquare\)
Remarques¶
Remarque 1. La solution 1 utilise que \(k > 1\) est impair ; on peut adapter la fin pour tout \(k\) assez grand (pour \(k\) pair, on montre que la suite \(P(1), \ldots, P(k)\) a des nombres différents de termes positifs et négatifs). En revanche, l'énoncé devient faux avec \(k = 2\) : \(P(x) = T(x) - T(x-1)\) et \(Q(x) = T(x-1) - T(x)\) sont alors semblables par blocs, car \(P(2i-1) = -P(2i) = Q(2i) = -Q(2i-1) = T(2i-1)\) pour tout \(i\). Toute solution complète doit donc utiliser \(k > 2\). La condition \(n \geq 2\) est aussi essentielle : pour \(n = 1\), les polynômes \(x\) et \(k + 1 - x\) sont semblables par blocs. Enfin, le résultat reste vrai pour des polynômes de degré au plus \(n\).
Remarque 2 (fusionner les étapes 1 et 2). On veut montrer que \(S = 2P - R = 2Q + R\) est constant ; comme \(R\) et \(S\) sont de degré au plus \(n\), il suffit de montrer que \(R\) et \(\Delta S\) ont au total au moins \(2n\) racines. Affirmation : pour tout \(i\), ou bien \(R\) et \(\Delta S\) ont chacun une racine dans \(I_i\), ou bien \(R\) a au moins deux racines dans \(I_i\). En effet, soit \(r \in Z_i\) avec \(|R(r)| = \max_{Z_i} |R|\), et supposons \(R(r) > 0\). Soient \(p_-, q_+\) tels que \(P(p_-) = \min_{Z_i} P\) et \(Q(q_+) = \max_{Z_i} Q\). On a \(P(p_-) \leq Q(r) < P(r)\) et \(Q(q_+) \geq P(r) > Q(r)\), donc \(r \neq p_-, q_+\). Supposons \(p_- < r\) : \(R(p_-) \leq 0 < R(r)\) donne une racine de \(R\) dans \([p_-, r)\). Si \(q_+ > r\), de même \(R(q_+) \leq 0 < R(r)\) donne une seconde racine dans \((r, q_+]\). Si \(q_+ < r\), alors \(S(p_-) = 2P(p_-) - R(p_-) \leq 2Q(r) + R(r) = S(r)\) et \(S(q_+) = 2Q(q_+) + R(q_+) \geq 2P(r) - R(r) = S(r)\), donc la suite des valeurs de \(S\) sur \(Z_i\) n'est ni strictement croissante ni strictement décroissante, et \(\Delta S\) a une racine dans \(I_i\).
Remarque 3. Après avoir obtenu \(P(x) - Q(x) = \alpha\big(T(x) - T(x-1)\big)\) comme dans la solution 1, on peut aussi suivre la solution 2 ; connaître cette différence simplifie certaines étapes (par exemple, il est alors clair que \(P - Q\) a exactement une racine dans chaque \(I_i\)).