Shortlist 2023, A6¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Malaysia
Concepts : Principe extrémal · Polynômes : racines, relations de Viète, factorisation · Principe des tiroirs · Polynômes à coefficients entiers · Descente infinie et Vieta jumping
Solution officielle : Shortlist officielle 2023 (avec solutions), p. 23 (page 25 du PDF)
Problème 3 de l'OIM 2023
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2023, où il était le problème 3 (jour 1).
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(k \geq 2\) be an integer. Determine all sequences of positive integers \(a_1, a_2, \ldots\) for which there exists a monic polynomial \(P\) of degree \(k\) with non-negative integer coefficients such that
for every integer \(n \geq 1\).
Indices : les idées clés
- Monotonie de \(P\) : à coefficients positifs, \(P\) est strictement croissant sur \(\mathbb{R}_+^*\), donc comparer \(P(a_n)\) et \(P(a_{n+1})\) revient à comparer \(a_n\) et \(a_{n+1}\), ou encore \(a_{n+1}\) et \(a_{n+k+1}\).
- Principe extrémal et descente infinie : pas de suite strictement décroissante d'entiers positifs (solutions 1 et 2) ; l'écart minimal \(d\) se propage (solution 1).
- Comparer les coefficients de \(x^{k-1}\) : pour \(a_n\) grand, la somme des écarts \(a_{n+i} - a_n\) est forcée d'être le coefficient \(b\) de \(x^{k-1}\) dans \(P\).
- Polynômes : racines : deux polynômes qui coïncident en une infinité de points sont égaux.
- Principe des tiroirs et polynômes à coefficients entiers (solution 2) : un même \(k\)-uplet se répète une infinité de fois, et \(a_n + b_j\) divise \(\prod_l (b_i + b_l - b_j)\), nombre fixe, donc nul.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (deux solutions et deux remarques).
Réponse. Les suites cherchées sont exactement les progressions arithmétiques d'entiers strictement positifs de raison \(d \geq 0\) ; le polynôme correspondant est \(P(x) = (x + d)(x + 2d) \cdots (x + kd)\).
Remarques communes (implicites dans les deux solutions). Si \((a_n)\) est arithmétique de raison \(d \geq 0\), elle convient avec \(P(x) = (x+d) \cdots (x+kd)\), car \(a_{n+i} = a_n + id\). Réciproquement, soit \((a_n)\) une suite qui convient ; montrons qu'elle est arithmétique croissante au sens large. Comme \(P\) est à coefficients entiers positifs ou nuls, il est strictement croissant sur les réels positifs : pour \(x, y\) entiers positifs, \(P(x) < P(y) \iff x < y\). Si \((a_n)\) est stationnaire, alors \(P(x) = x^k\) : sinon \(P(c) > c^k\) pour tout \(c > 0\), et \(P(a_n) = a_{n+1} \cdots a_{n+k}\) serait faux pour un \(n\) tel que \(a_n = \cdots = a_{n+k}\). Par une récurrence descendante (\(P(a_n) = c^k\) force \(a_n = c\)), la suite est alors constante. On peut donc supposer que \((a_n)\) n'est pas stationnaire.
Solution 1¶
On suppose \((a_n)\) non stationnaire.
Étape 1 : la suite est strictement croissante. En comparant
et grâce à la monotonie de \(P\), on obtient
Affirmation 1. \(a_n \leq a_{n+1}\) pour tout \(n \geq 1\).
Preuve. Supposons au contraire que \(a_{n(0)-1} > a_{n(0)}\) pour un certain \(n(0) \geq 2\). Construisons une suite infinie d'indices \(n(0) < n(1) < \cdots\) telle que
Alors \(a_{n(0)} > a_{n(1)} > a_{n(2)} > \cdots\) serait une suite infinie strictement décroissante d'entiers strictement positifs, ce qui est absurde (principe extrémal / descente infinie).
Construction par récurrence : \(n(i)\) étant choisi, soit \(n(i+1)\) le plus petit indice \(> n(i)\) tel que \(a_{n(i)} > a_{n(i+1)}\). Il existe et vérifie \(n(i) + 1 \leq n(i+1) \leq n(i) + k\), car \(a_{n(i)} > a_{n(i)+k}\) d'après (2) (appliqué au rang \(n(i) - 1\)). Il reste à vérifier \(a_{n(i+1)-1} > a_{n(i+1)}\). C'est immédiat si \(n(i+1) = n(i) + 1\). Si \(n(i+1) \geq n(i) + 2\), la minimalité de \(n(i+1)\) donne \(a_{n(i+1)-1} \geq a_{n(i)}\), donc \(a_{n(i+1)-1} \geq a_{n(i)} > a_{n(i+1)}\). \(\square\)
Supposons maintenant \(a_n = a_{n+1}\) pour un \(n \geq 1\). Par (3), \(a_{n+1} = a_{n+k+1}\), et comme la suite est croissante au sens large, \(a_n = a_{n+1} = \cdots = a_{n+k+1}\). En répétant l'argument avec \(a_{n+k} = a_{n+k+1}\), on voit que la suite est stationnaire, contrairement à l'hypothèse. Donc \(a_n < a_{n+1}\) pour tout \(n \geq 1\).
Étape 2 : la suite est arithmétique. On fait apparaître les écarts :
Notons \(b\) le coefficient de \(x^{k-1}\) dans \(P\). Montrons que pour \(n\) assez grand, \((a_{n+1} - a_n) + \cdots + (a_{n+k} - a_n) = b\).
Affirmation 2. Il existe un seuil \(A\) tel que :
- si \((c_1, \ldots, c_k)\) sont des entiers strictement positifs avec \(c_1 + \cdots + c_k > b\), alors \(P(x) < (x + c_1) \cdots (x + c_k)\) pour tout \(x \geq A\) ;
- si \((c_1, \ldots, c_k)\) sont des entiers strictement positifs avec \(c_1 + \cdots + c_k < b\), alors \(P(x) > (x + c_1) \cdots (x + c_k)\) pour tout \(x \geq A\).
Preuve. Il suffit de traiter chaque partie séparément puis de prendre le maximum des deux seuils. Partie 1 : pour un \(k\)-uplet donné, un tel seuil existe car
a un coefficient dominant négatif, donc est négatif pour \(x\) assez grand. Soit \(A\) un seuil commun à tous les \(k\)-uplets de somme exactement \(b + 1\) (il y en a un nombre fini). Pour tout \(k\)-uplet \(c'\) de somme \(> b\), il existe un \(k\)-uplet \(c\) de somme \(b + 1\) avec \(c'_i \geq c_i\) pour tout \(i\), et l'inégalité pour \(c'\) découle de celle pour \(c\). Partie 2 : même méthode, ou simplement parce qu'il n'y a qu'un nombre fini de tels \(k\)-uplets. \(\square\)
Prenons \(A\) comme dans l'affirmation 2 et \(N\) tel que \(a_n \geq A\) pour \(n \geq N\) (la suite est strictement croissante). Pour \(n \geq N\), les \(c_i = a_{n+i} - a_n\) sont des entiers strictement positifs et \(P(a_n) = \prod (a_n + c_i)\), donc ni l'une ni l'autre inégalité stricte n'est possible :
En retranchant cette égalité de celle au rang \(n + 1\), on obtient, pour tout \(n \geq N\),
On conclut par le principe extrémal. Soit \(d = \min\{a_{n+1} - a_n \mid n \geq N\}\), atteint en un indice \(n \geq N\). Comme
et que chaque terme vaut au moins \(d\), le minimum \(d\) est aussi atteint en \(n+1, \ldots, n+k\), puis, de proche en proche, en tout \(n' \geq n\). L'égalité \(P(x) = (x + d)(x + 2d) \cdots (x + kd)\) est alors vraie pour une infinité de valeurs de \(x\) (tous les \(a_{n'}\), \(n' \geq n\)) : c'est donc une égalité de polynômes. Enfin, une récurrence descendante (avec l'injectivité de \(P\) : \(P(a_{m-1}) = a_m(a_m + d) \cdots (a_m + (k-1)d) = P(a_m - d)\)) montre que \(a_{m+1} - a_m = d\) pour tout \(m \geq 1\). \(\blacksquare\)
Solution 2¶
On suppose \((a_n)\) non stationnaire. On démontre d'abord une variante de l'affirmation 1.
Affirmation 3. Il existe une infinité d'indices \(n \geq 1\) tels que \(a_n \leq \min\{a_{n+1}, \ldots, a_{n+k}\}\).
Preuve. Sinon, pour tout \(n\) assez grand, il existe \(1 \leq l \leq k\) avec \(a_n > a_{n+l}\). On en déduit une suite infinie strictement décroissante d'entiers strictement positifs \(a_n > a_{n+l_1} > a_{n+l_2} > \cdots\), ce qui est absurde. \(\square\)
Cas \(P(x) = x^k\). Pour tout \(n\) tel que \(a_n \leq \min\{a_{n+1}, \ldots, a_{n+k}\}\), l'égalité \(a_{n+1} \cdots a_{n+k} = a_n^k\) impose \(a_n = a_{n+1} = \cdots = a_{n+k}\). Avec l'affirmation 3, la suite serait stationnaire : contradiction. Désormais, \(P(x) > x^k\) pour tout \(x > 0\).
Affirmation 4. Pour tout \(M > 0\), il existe \(N\) tel que \(a_n > M\) pour tout \(n > N\).
Preuve. Supposons qu'il existe \(M > 0\) avec \(a_n \leq M\) pour une infinité de \(n\). Pour chaque \(i\) tel que \(a_i \leq M\), considérons le \(k\)-uplet \((a_{i+1}, \ldots, a_{i+k})\) : chacun de ses termes est majoré par \(P(a_i) \leq P(M)\). Il y a au plus \(P(M)^k\) tels \(k\)-uplets, donc par le principe des tiroirs il existe \(i < j\) avec \((a_{i+1}, \ldots, a_{i+k}) = (a_{j+1}, \ldots, a_{j+k})\). Comme chaque terme est déterminé par les \(k\) précédents (injectivité de \(P\)), \(a_{i+k+1} = a_{j+k+1}\), puis \(a_{i+l} = a_{j+l}\) pour tout \(l \geq 0\) : la suite est ultimement périodique, de période \(p = j - i\).
Soit \(K\) tel que \(a_n = a_{n+p}\) pour tout \(n \geq K\). En multipliant les inégalités \(a_n^k < P(a_n) = a_{n+1} \cdots a_{n+k}\) pour \(K \leq n \leq K + p - 1\), on obtient
la dernière égalité venant de la périodicité (chaque produit intérieur porte sur \(p\) indices consécutifs \(\geq K\)). C'est une contradiction. \(\square\)
Écrivons \(P(x) = x^k + b x^{k-1} + Q(x)\) avec \(\deg Q \leq k - 2\) (et \(Q\) à coefficients positifs ou nuls), et prenons \(M\) tel que \(x > M\) entraîne \(x^{k-1} > Q(x)\).
Affirmation 5. Il existe des entiers positifs ou nuls \(b_1, \ldots, b_k\) tels que \(P(x) = (x + b_1) \cdots (x + b_k)\) et que, pour une infinité de \(n \geq 1\), on ait \(a_{n+i} = a_n + b_i\) pour tout \(1 \leq i \leq k\).
Preuve. D'après les affirmations 3 et 4, il y a une infinité d'indices \(n\), dits bons, tels que \(a_n > M\) et \(a_n \leq \min\{a_{n+1}, \ldots, a_{n+k}\}\). Si \(n\) est bon, alors \(\max\{a_{n+1}, \ldots, a_{n+k}\} \leq a_n + b\). En effet, si \(a_{n+i} \geq a_n + b + 1\), comme les autres facteurs sont \(\geq a_n\) et que \(a_n^{k-1} > Q(a_n)\),
contradiction. Ainsi, pour chaque bon \(n\), on peut écrire \(a_{n+i} = a_n + b_i\) (\(1 \leq i \leq k\)) avec \(0 \leq b_i \leq b\) (les \(b_i\) dépendant a priori de \(n\)). Par le principe des tiroirs, un même \(k\)-uplet \((b_1, \ldots, b_k)\) apparaît pour une infinité de bons \(n\). L'égalité \(P(a_n) = (a_n + b_1) \cdots (a_n + b_k)\) est alors vraie pour une infinité de bons \(n\), et les \(a_n\) correspondants ne sont pas bornés (affirmation 4) : donc \(P(x) = (x + b_1) \cdots (x + b_k)\) identiquement (polynômes égaux en une infinité de points). \(\square\)
Affirmation 6. \(b_i = i b_1\) pour tout \(1 \leq i \leq k\).
Preuve. Appelons excellent un indice \(n\) tel que \(a_{n+i} = a_n + b_i\) pour tout \(1 \leq i \leq k\) ; il y en a une infinité.
Montrons d'abord que pour tous \(1 \leq i < j \leq k\), il existe \(1 \leq l \leq k\) avec \(b_j = b_i + b_l\). Pour \(n\) excellent, \(a_n + b_j = a_{n+j}\) figure parmi les facteurs de \(P(a_{n+i}) = a_{n+i+1} \cdots a_{n+i+k}\) (car \(1 \leq j - i \leq k\)), donc divise \(P(a_{n+i}) = \prod_{l=1}^{k} (a_n + b_i + b_l)\). Comme \(a_n + b_i + b_l \equiv b_i + b_l - b_j \pmod{a_n + b_j}\) (polynômes à coefficients entiers), \(a_n + b_j\) divise l'entier fixe \(\prod_{l=1}^{k} (b_i + b_l - b_j)\). Or \(a_n + b_j\) n'est pas borné quand \(n\) parcourt les indices excellents, donc ce produit est nul : il existe \(l\) avec \(b_j = b_i + b_l\). En particulier \(b_j \geq b_i\) : le \(k\)-uplet est croissant au sens large.
Cas \(b_1 = 0\). Soit \(n\) excellent ; alors \(a_n = a_{n+1}\). De plus,
d'où \(a_n = a_{n+1} = a_{n+k+1}\), qui divise \(P(a_{n+i}) = \prod_{l=1}^{k} (a_n + b_i + b_l)\) pour chaque \(1 \leq i \leq k\). Donc \(a_n\) divise \(\prod_{l=1}^{k} (b_i + b_l)\) ; par le même raisonnement, \(b_i + b_l = 0\) pour un certain \(l\), et comme \(b_i, b_l \geq 0\), on obtient \(b_i = 0\) pour tout \(i\). Précision ajoutée : on aurait alors \(P(x) = x^k\), cas déjà exclu ; ce cas est donc impossible.
Cas \(b_1 \geq 1\). Pour \(1 \leq i < j \leq k\), \(b_j - b_i = b_l \geq b_1 \geq 1\), donc \((b_1, \ldots, b_k)\) est strictement croissant. Chacun des \(k - 1\) éléments \(b_2 < b_3 < \cdots < b_k\) s'écrit \(b_1 + b_l\), et ne peut valoir \(b_1 + b_k\) ; ils coïncident donc exactement avec \(b_1 + b_1 < \cdots < b_1 + b_{k-1}\). Ainsi \(b_{i+1} = b_1 + b_i\), et \(b_i = i b_1\) pour tout \(i\). \(\square\)
Conclusion. L'affirmation 6 donne \(P(x) = (x + d)(x + 2d) \cdots (x + kd)\) avec \(d = b_1 \geq 1\), et une infinité d'indices \(n\) avec \(a_{n+i} = a_n + id\) pour \(1 \leq i \leq k\). Par récurrence descendante, \(P(a_{n-1}) = a_n \cdots a_{n+k-1} = P(a_n - d)\) donne \(a_{n-1} = a_n - d\), et ainsi de suite : \(a_1, \ldots, a_n\) est une progression arithmétique de raison \(d\). Comme \(n\) peut être pris arbitrairement grand, toute la suite est arithmétique. \(\blacksquare\)
Remarques¶
Remarque 1. Une solution typique établit d'abord une propriété de croissance (lorsque la suite n'est pas constante), puis en déduit des informations sur les écarts \(a_{n+i} - a_n\) (\(1 \leq i \leq k\)) et/ou sur \(P\). La solution 1 prouve une croissance stricte, \(a_n < a_{n+1}\), ce qui simplifie la suite ; la solution 2 (affirmations 3 et 4) n'obtient que des propriétés plus faibles, ce qui demande ensuite des arguments plus astucieux.
Remarque 2. Il serait intéressant de traiter le cas où \(P\) peut avoir des coefficients entiers négatifs, ou celui où \((a_n)\) est seulement une suite d'entiers. Une progression arithmétique décroissante devient possible, mais ce n'est pas la seule possibilité : il existe des exemples bornés comme \(1, -1, 1, -1, \ldots\) avec \(P(x) = -x^2\), ou \(0, 1, -1, 0, 1, -1, \ldots\) avec \(P(x) = x^2 - 1\). Si \(P\) n'est plus supposé unitaire, la situation est encore moins claire : par exemple, \(1, 2, 4, 8, \ldots\) convient pour \(P(x) = 8x^2\).