Aller au contenu

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é

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

\[10^t > \max\left\{ \frac{100^{n-1} a_{n-1}}{\left(10^{\frac{1}{n-1}} - 9^{\frac{1}{n-1}}\right)^{n-1}},\ \frac{a_{n-1}}{9} 10^{n-1},\ \frac{a_{n-1}}{9}(10 a_{n-1})^{n-1},\ \ldots,\ \frac{a_{n-1}}{9}(10 a_0)^{n-1} \right\}.\]

Comme \(10^t\) dépasse la première quantité, l'intervalle

\[I = \left[ \left(\frac{9}{a_{n-1}} 10^t\right)^{\frac{1}{n-1}},\ \left(\frac{1}{a_{n-1}} 10^{t+1}\right)^{\frac{1}{n-1}} \right[\]

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\),

\[9 \cdot 10^t \leq a_{n-1} X^{n-1} < 10^{t+1},\]

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

\[10^{\alpha(i+1)} > 10^{\alpha i} a_{n-1}X^{n-1} > 10^{\alpha i} a_i X^i,\]

les termes \(a_i 10^{\alpha i} X^i\) « n'interagissent pas » quand on les additionne : il n'y a aucune retenue. Ainsi

\[s(P(10^{\alpha}X)) = s(X^n) + s(a_{n-1}X^{n-1}) + \cdots + s(a_0).\]

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

\[10^{(\alpha-1)(i+1)+1} > 10^{(\alpha-1)i} a_{n-1}X^{n-1} \geq 10^{(\alpha-1)i+1} a_i X^i,\]

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

\[s(P(10^{\alpha-1}X)) = s(X^n) + s(a_{n-1}X^{n-1}) + \cdots + s(a_0) - 9 = s(P(10^{\alpha}X)) - 9.\]

Donc \(s(P(10^{\alpha}X))\) et \(s(P(10^{\alpha-1}X))\) sont de parités différentes, ce qui conclut. \(\blacksquare\)