Shortlist 2015, N1¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : Luxembourg
Concepts : Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler · Descente infinie et Vieta jumping
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 65 (page 66 du PDF)
Énoncé¶
Déterminer tous les entiers \(M\) strictement positifs pour lesquels la suite \(a_0, a_1, a_2, \ldots\) définie par \(a_0 = \frac{2M+1}{2}\) et \(a_{k+1} = a_k \lfloor a_k \rfloor\) pour \(k = 0, 1, 2, \ldots\) contient au moins un terme entier.
Énoncé original (anglais)
Determine all positive integers \(M\) for which the sequence \(a_0, a_1, a_2, \ldots\), defined by \(a_0 = \frac{2M+1}{2}\) and \(a_{k+1} = a_k \lfloor a_k \rfloor\) for \(k = 0, 1, 2, \ldots\), contains at least one integer term.
Indices : les idées clés
- Se débarrasser des demis : \(b_k = 2a_k\) est un entier, et la suite n'a aucun terme entier si et seulement si tous les \(b_k\) sont impairs.
- Point fixe \(3\) : la récurrence \(b_{k+1} = \frac{b_k(b_k - 1)}{2}\) fixe \(3\), et \(b_{k+1} - 3 = \frac{(b_k - 3)(b_k + 2)}{2}\).
- Valuation 2-adique (solution 1) : la valuation de \(b_k - 3\) diminue de \(1\) à chaque pas, ce qui est impossible indéfiniment (descente infinie).
- Congruences (solution 2) : \(b_k \equiv 3 \pmod{2^m}\) pour tout \(m\), par récurrence sur \(m\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et une remarque).
Réponse. Tous les entiers \(M \geq 2\).
Solution 1¶
Posons \(b_k = 2a_k\) pour tout \(k \geq 0\). Alors
Comme \(b_0 = 2M + 1\) est un entier, tous les \(b_k\) sont des entiers.
Supposons que la suite \((a_k)\) ne contienne aucun terme entier. Alors tous les \(b_k\) sont impairs, et
Par conséquent,
Supposons \(b_0 - 3 > 0\). Alors (2) donne \(b_k - 3 > 0\) pour tout \(k \geq 0\). Pour chaque \(k\), notons \(c_k\) l'exposant de la plus grande puissance de \(2\) divisant \(b_k - 3\) (la valuation 2-adique de \(b_k - 3\)). Comme \(b_k - 3\) est pair, \(c_k \geq 1\) pour tout \(k\). Or \(b_k + 2\) est impair, donc (2) donne \(c_{k+1} = c_k - 1\). La suite \((c_k)\) d'entiers strictement positifs serait strictement décroissante : contradiction. Donc \(b_0 - 3 \leq 0\), c'est-à-dire \(M = 1\).
Pour \(M = 1\), on vérifie que la suite est constante : \(a_k = \frac{3}{2}\) pour tout \(k\) (car \(\frac{3}{2} \cdot \lfloor \frac{3}{2} \rfloor = \frac{3}{2}\)), donc elle ne contient aucun entier. La réponse est donc : tous les \(M \geq 2\). \(\blacksquare\)
Solution 2¶
Voici une autre façon de prouver \(M = 1\) une fois l'équation (1) obtenue. Montrons que \(b_k \equiv 3 \pmod{2^m}\) pour tout \(k \geq 0\) et tout \(m \geq 1\). Cela donnera \(b_k = 3\) pour tout \(k\), donc \(M = 1\).
Raisonnons par récurrence sur \(m\). Pour \(m = 1\), \(b_k \equiv 3 \pmod 2\) pour tout \(k\) car \(b_k\) est impair. Supposons \(b_k \equiv 3 \pmod{2^m}\) pour tout \(k \geq 0\), et écrivons \(b_k = 2^m d_k + 3\) avec \(d_k\) entier. D'après (1),
donc \(d_k\) est pair. Ainsi \(b_k \equiv 3 \pmod{2^{m+1}}\) pour tout \(k\), ce qui achève la récurrence. \(\blacksquare\)
Remarques¶
Remarque 1. Le nombre \(3\), qui joue un rôle central dans les deux solutions, est important parce que c'est un point fixe non trivial de la relation de récurrence vérifiée par \(b_k\).
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 N3 ★★☆☆☆ · OIM P4 : Chaque terme est la somme des trois plus grands diviseurs stricts du précédent : avec quelles valeurs la suite peut-elle partir ?
- 2024 N3 ★★☆☆☆ : Trouver les suites d'entiers dont toutes les moyennes arithmétiques et géométriques sur des blocs consécutifs sont entières.
- 2015 N3 ★★☆☆☆ : Si tous les \((m + k)/(n + k)\) sont entiers, leur produit moins \(1\) a un facteur premier impair.
- 2019 N5 ★★★☆☆ : Si \(b\) est \(a\)-bon mais pas \(b + 2\), pour une condition de divisibilité de coefficients binomiaux, alors \(b + 1\) est premier.