Shortlist 2016, N1¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Polynômes à coefficients entiers
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 71 (page 74 du PDF)
Énoncé¶
For any positive integer \(k\), denote the sum of digits of \(k\) in its decimal representation by \(S(k)\). Find all polynomials \(P(x)\) with integer coefficients such that for any positive integer \(n \geq 2016\), the integer \(P(n)\) is positive and
Indices : les idées clés
- Sous-additivité de la somme des chiffres (solution 1) : \(S(m + n) \leq S(m) + S(n)\), avec égalité si et seulement s'il n'y a aucune retenue.
- Choisir des \(n\) bien adaptés : \(n = 10^k - 1\) (beaucoup de \(9\)) ou \(n = 9 \times 10^k\) (un seul chiffre non nul) ; \(S(P(n))\) croît au plus comme \(k\), alors que \(P(S(n))\) est un polynôme en \(k\) ou une constante.
- Polynômes à coefficients entiers (solution 2) : pour \(n = 9 \times 10^k\) avec \(k\) grand, l'écriture décimale de \(P(n)\) est formée des blocs \(a_i \times 9^i\) séparés par des zéros, ce qui force \(S(a_i \times 9^i) = a_i \times 9^i\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (deux solutions).
Réponse. \(P(x) = c\) avec \(c\) entier, \(1 \leq c \leq 9\) ; ou \(P(x) = x\).
Solution 1¶
On distingue trois cas selon le degré de \(P\). Notons (1) la relation \(S(P(n)) = P(S(n))\).
Cas 1 : \(P\) constant. Si \(P(x) = c\) avec \(c\) entier, (1) devient \(S(c) = c\), ce qui a lieu si et seulement si \(1 \leq c \leq 9\).
Cas 2 : \(\deg P = 1\). On utilise l'observation suivante : pour tous entiers \(m, n > 0\),
avec égalité si et seulement s'il n'y a pas de retenue dans l'addition \(m + n\).
Posons \(P(x) = ax + b\) avec \(a, b\) entiers, \(a \neq 0\). Comme \(P(n) > 0\) pour \(n\) grand, \(a \geq 1\). La condition (1) s'écrit \(S(an + b) = aS(n) + b\) pour tout \(n \geq 2016\). Avec \(n = 2025\) et \(n = 2020\),
D'autre part, (2) donne
Donc \(5a \leq S(5a)\). Comme \(a \geq 1\) et \(S(m) < m\) dès que \(m \geq 10\), cela n'est possible que pour \(a = 1\). Alors (1) devient \(S(n + b) = S(n) + b\) pour tout \(n \geq 2016\), d'où
Si \(b > 0\), choisissons \(n\) tel que \(n + 1 + b = 10^k\) avec \(k\) assez grand. Tous les chiffres de \(n + b\) valent \(9\), donc le membre de gauche de (3) vaut \(1 - 9k\). Comme \(n\) est un entier positif inférieur à \(10^k - 1\), on a \(S(n) < 9k\), donc \(S(n) \leq 9k - 1\), et le membre de droite de (3) est au moins \(1 - (9k - 1) = 2 - 9k\) : contradiction.
Le cas \(b < 0\) se traite de même en choisissant \(n + 1\) égal à une grande puissance de \(10\). On conclut que \(P(x) = x\), qui vérifie évidemment (1).
Précision ajoutée pour \(b < 0\) : avec \(n + 1 = 10^k\), le membre de droite de (3) vaut \(1 - 9k\), tandis que \(n + b < 10^k - 1\) n'a pas que des \(9\), donc \(S(n + b) \leq 9k - 1\) et le membre de gauche vaut au moins \(S(n+1+b) - (9k - 1) \geq 2 - 9k\).
Cas 3 : \(\deg P \geq 2\). Soit \(a_d n^d\) le terme dominant de \(P\), avec \(a_d \neq 0\) ; clairement \(a_d > 0\). Prenons \(n = 10^k - 1\) dans (1) : on obtient \(S(P(n)) = P(9k)\). Or \(P(n)\) est de l'ordre de \(n^d\), donc a \(O(k)\) chiffres, et \(S(P(n))\) croît au plus comme une constante fois \(k\). En revanche, \(P(9k)\) croît comme \(k^d\). Comme \(d \geq 2\), les deux membres ne peuvent pas être égaux pour \(k\) assez grand.
Conclusion. Les solutions sont \(P(x) = c\) avec \(1 \leq c \leq 9\) entier, et \(P(x) = x\). \(\blacksquare\)
Solution 2¶
Écrivons \(P(x) = a_d x^d + a_{d-1}x^{d-1} + \cdots + a_0\). Clairement \(a_d > 0\). Il existe un entier \(m \geq 1\) tel que \(|a_i| < 10^m\) pour tout \(0 \leq i \leq d\). Prenons \(n = 9 \times 10^k\) dans (1), avec \(k\) entier assez grand.
S'il existe un indice \(0 \leq i \leq d - 1\) tel que \(a_i < 0\), alors tous les chiffres de \(P(n)\) dans les positions de \(10^{ik + m + 1}\) à \(10^{(i+1)k - 1}\) sont des \(9\) (à cause des retenues négatives). Donc \(S(P(n)) \geq 9(k - m - 1)\). D'autre part, \(P(S(n)) = P(9)\) est une constante fixe. La relation (1) ne peut donc pas être vraie pour \(k\) grand. Ainsi \(a_i \geq 0\) pour tout \(0 \leq i \leq d - 1\).
Par conséquent, l'entier \(P(n)\) s'obtient en écrivant à la suite les entiers positifs ou nuls \(a_d \times 9^d, a_{d-1} \times 9^{d-1}, \ldots, a_0\), séparés par des zéros. Cela donne
Avec (1), on obtient
Comme \(S(m) \leq m\) pour tout entier \(m > 0\), avec égalité si et seulement si \(1 \leq m \leq 9\), chaque terme non nul \(a_i \times 9^i\) doit être un entier compris entre \(1\) et \(9\). (Le livret écrit « chaque \(a_i \times 9^i\) » ; il faut lire « chaque terme non nul », certains \(a_i\) pouvant être nuls.) Comme \(9^i \geq 81 > 9\) pour \(i \geq 2\), on a \(a_i = 0\) pour \(i \geq 2\), donc \(d \leq 1\). On a aussi \(a_1 \leq 1\) et \(a_0 \leq 9\).
Si \(a_1 = 1\) et \(1 \leq a_0 \leq 9\), prenons \(n = 10^k + (10 - a_0)\) avec \(k\) grand dans (1). On obtient une contradiction, car
Le polynôme nul est exclu puisque \(P(n)\) doit être positif pour \(n\) grand. Les candidats restants sont \(P(x) = x\) et \(P(x) = a_0\) avec \(1 \leq a_0 \leq 9\) ; tous vérifient (1), et ce sont donc les seules solutions. \(\blacksquare\)