Shortlist 2022, A7¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Belarus
Concepts : Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 20 (page 22 du PDF)
Énoncé¶
Pour un entier \(n\) strictement positif, on note \(s(n)\) la somme des chiffres de \(n\). Soit \(P(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0\) un polynôme, où \(n \geq 2\) et où \(a_i\) est un entier strictement positif pour tout \(0 \leq i \leq n - 1\). Est-il possible que, pour tout entier \(k\) strictement positif, \(s(k)\) et \(s(P(k))\) aient la même parité ?
Énoncé original (anglais)
For a positive integer \(n\) we denote by \(s(n)\) the sum of the digits of \(n\). Let \(P(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0\) be a polynomial, where \(n \geq 2\) and \(a_i\) is a positive integer for all \(0 \leq i \leq n - 1\). Could it be the case that, for all positive integers \(k\), \(s(k)\) and \(s(P(k))\) have the same parity?
Indices : les idées clés
- Réponse : non. Pour tout tel polynôme, il existe \(k\) tel que \(s(k)\) et \(s(P(k))\) n'ont pas la même parité.
- Multiplier par une puissance de 10 ne change pas la somme des chiffres : on compare \(k = 10^{\alpha}X\) et \(k = 10^{\alpha-1}X\), qui ont la même somme des chiffres que \(X\).
- Séparer les termes en « blocs » sans retenue : en choisissant \(X\) assez grand, les termes \(a_i 10^{\alpha i} X^i\) s'additionnent chiffre à chiffre, sans retenue.
- Congruences : avec \(X \equiv 1 \pmod{100}\), \(X^n\) se termine par \(01\) ; une seule retenue (un \(9\) et un \(1\)) fait alors chuter la somme des chiffres de exactement \(9\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2022 (une solution).
Réponse : non. Pour tout polynôme de cette forme, il existe un entier \(k \geq 1\) tel que \(s(k)\) et \(s(P(k))\) sont de parités différentes.
Solution¶
Posons \(a_n = 1\) (coefficient de \(x^n\)).
Choix d'une grande puissance de 10. On choisit un entier \(t \geq 1\) tel que
Comme \(10^t\) dépasse la première quantité, l'intervalle
a une longueur \(\left(\frac{10^t}{a_{n-1}}\right)^{\frac{1}{n-1}}\left(10^{\frac{1}{n-1}} - 9^{\frac{1}{n-1}}\right) > 100\), donc contient au moins \(100\) entiers consécutifs.
Soit \(X\) un entier de \(I\) tel que \(X \equiv 1 \pmod{100}\). Comme \(X \in I\),
donc le premier chiffre (à gauche) de \(a_{n-1}X^{n-1}\) est un \(9\).
Ensuite, \(a_{n-1}(10 a_i)^{n-1} < 9 \cdot 10^t \leq a_{n-1}X^{n-1}\) (y compris pour \(i = n\), grâce à la deuxième quantité), donc \(10 a_i < X\) pour tout \(i\). On en déduit \(a_0 < a_1 X < \cdots < a_n X^n\), et même que le nombre de chiffres de cette suite est strictement croissant : si \(i < j\), \(a_i X^i\) a moins de chiffres que \(a_j X^j\).
Soit \(\alpha\) le nombre de chiffres de \(a_{n-1}X^{n-1}\), c'est-à-dire \(10^{\alpha-1} \leq a_{n-1}X^{n-1} < 10^{\alpha}\). Nous allons montrer que \(s(P(10^{\alpha}X))\) et \(s(P(10^{\alpha-1}X))\) sont de parités différentes. Cela suffit, car \(s(10^{\alpha}X) = s(10^{\alpha-1}X) = s(X)\) : l'un des deux entiers \(k = 10^{\alpha}X\) ou \(k = 10^{\alpha-1}X\) convient.
Calcul de \(s(P(10^{\alpha}X))\). On a \(P(10^{\alpha}X) = 10^{\alpha n}X^n + a_{n-1}10^{\alpha(n-1)}X^{n-1} + \cdots + a_0\). Comme
les termes \(a_i 10^{\alpha i} X^i\) « n'interagissent pas » quand on les additionne : il n'y a aucune retenue. Ainsi
Calcul de \(s(P(10^{\alpha-1}X))\). On a \(P(10^{\alpha-1}X) = 10^{(\alpha-1)n}X^n + a_{n-1}10^{(\alpha-1)(n-1)}X^{n-1} + \cdots + a_0\). D'abord, si \(i < n-1\), alors \(a_{n-1}X^{n-1}\) a plus de chiffres que \(a_i X^i\) et \(a_{n-1}X^{n-1} \geq 10 a_i X^i\). Il s'ensuit que
donc tous les termes \(10^{(\alpha-1)i} a_i X^i\), pour \(0 \leq i \leq n-1\), forment des « blocs » séparés, exactement comme dans le cas précédent.
Enfin, \(10^{(\alpha-1)n+1} > 10^{(\alpha-1)(n-1)} a_{n-1}X^{n-1} \geq 10^{(\alpha-1)n}\), donc \(10^{(\alpha-1)(n-1)} a_{n-1}X^{n-1}\) a exactement \((\alpha-1)n + 1\) chiffres, et son premier chiffre est \(9\). D'autre part, comme \(X \equiv 1 \pmod{100}\), on a \(X^n \equiv 1 \pmod{100}\) (congruences), donc \(10^{(\alpha-1)n}X^n\) se termine par exactement \((\alpha-1)n\) zéros, précédés de \(\ldots 01\). Quand on additionne, le \(9\) et le \(1\) (au même rang) deviennent \(0\) avec une retenue, le \(0\) du rang suivant devient \(1\), et rien d'autre n'est modifié. Par conséquent
Donc \(s(P(10^{\alpha}X))\) et \(s(P(10^{\alpha-1}X))\) sont de parités différentes, ce qui conclut. \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 N7 ★★★★☆ · OIM P3 : Les fonctions telles que \(f(a)\) divise \(b^a - f(b)^{f(a)}\) : quelle est la meilleure constante \(c\) avec \(f(n) \leq cn\) ?
- 2024 N6 ★★★★☆ : Pour quels \(n\) tout polynôme entier \(P\) admet-il un \(Q\) de degré \(2\) tel que \(Q(k)(P(k) + Q(k))\) ne soit jamais divisible par \(n\) ?
- 2023 N6 ★★★★☆ : Des suites où chaque pas obéit à l'une de deux récurrences linéaires : si \(m\) et \(m + 1\) y apparaissent, alors \(3 \mid m\) et \(m/3\) y apparaît aussi.
- 2022 N7 ★★★★☆ · OIM P3 : Il y a au plus une façon de disposer des premiers en cercle avec des produits voisins de la forme \(x^2 + x + k\).