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é¶

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

\[b_{k+1} = 2a_{k+1} = 2a_k \lfloor a_k \rfloor = b_k \left\lfloor \frac{b_k}{2} \right\rfloor.\]

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

\[b_{k+1} = b_k \left\lfloor \frac{b_k}{2} \right\rfloor = \frac{b_k(b_k - 1)}{2}. \tag{1}\]

Par conséquent,

\[b_{k+1} - 3 = \frac{b_k(b_k - 1)}{2} - 3 = \frac{(b_k - 3)(b_k + 2)}{2} \quad \text{pour tout } k \geq 0. \tag{2}\]

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

\[3 \equiv b_{k+1} = (2^m d_k + 3)(2^{m-1} d_k + 1) \equiv 3 \cdot 2^{m-1} d_k + 3 \pmod{2^m},\]

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