Shortlist 2015, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Singapore
Concepts : Principe des tiroirs · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 73 (page 74 du PDF)
Énoncé¶
Let \(\mathbb{Z}_{>0}\) denote the set of positive integers. Consider a function \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\). For any \(m, n \in \mathbb{Z}_{>0}\) we write \(f^n(m) = \underbrace{f(f(\ldots f}_{n}(m)\ldots))\). Suppose that \(f\) has the following two properties:
(i) If \(m, n \in \mathbb{Z}_{>0}\), then \(\dfrac{f^n(m) - m}{n} \in \mathbb{Z}_{>0}\);
(ii) The set \(\mathbb{Z}_{>0} \setminus \{ f(n) \mid n \in \mathbb{Z}_{>0} \}\) is finite.
Prove that the sequence \(f(1) - 1,\, f(2) - 2,\, f(3) - 3,\, \ldots\) is periodic.
Indices : les idées clés
- Injectivité et « Tableau » : \(f\) est injective et \(f(m) > m\), donc chaque entier s'écrit de façon unique \(f^j(a_i)\), où \(a_1, \ldots, a_k\) sont les entiers non atteints par \(f\).
- Principe des tiroirs (version infinie) : une ligne « dense » du Tableau, puis un pas \(T_x\) commun à une infinité d'indices.
- Divisibilité : un entier divisible par \(y - j\) et de valeur absolue inférieure à \(y - j\) est nul ; cela force chaque ligne à être une progression arithmétique.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2015 (une solution et deux remarques).
Solution¶
On procède en trois étapes : d'abord, \(f\) est injective, ce qui donne une représentation commode de \(f\) ; ensuite (l'essentiel du travail), pour tout \(n\), la suite \(n, f(n), f^2(n), \ldots\) est une progression arithmétique ; enfin, on conclut.
Étape 1. Montrons que \(f\) est injective. Soient \(m, k\) avec \(f(m) = f(k)\). Par (i), pour tout entier \(n \geq 1\),
est une différence de deux entiers, donc un entier. Pour \(n = |k - m| + 1\), cela impose \(k = m\).
D'après (ii), il existe un nombre fini d'entiers \(a_1, \ldots, a_k\) tels que \(\mathbb{Z}_{>0}\) soit la réunion disjointe de \(\{a_1, \ldots, a_k\}\) et de \(\{f(n) \mid n \in \mathbb{Z}_{>0}\}\). Avec \(n = 1\) dans (i), on obtient \(f(m) > m\) pour tout \(m\).
Tout entier \(n \geq 1\) s'écrit de façon unique \(n = f^j(a_i)\) avec \(j \geq 0\) et \(i \in \{1, \ldots, k\}\). L'unicité vient de l'injectivité de \(f\). L'existence se prouve par récurrence sur \(n\) : si \(n \in \{a_1, \ldots, a_k\}\), on prend \(j = 0\) ; sinon il existe \(n' < n\) avec \(f(n') = n\), auquel on applique l'hypothèse de récurrence. Ainsi chaque entier positif apparaît exactement une fois dans le « Tableau » suivant :
Étape 2. Montrons que chaque ligne du Tableau est une progression arithmétique. Supposons au contraire que le nombre \(t\) de lignes qui en sont vérifie \(0 \leq t < k\). Quitte à permuter les lignes, les \(t\) premières sont des progressions arithmétiques, de pas \(T_1, \ldots, T_t\). L'idée est de trouver une autre ligne « pas trop clairsemée » asymptotiquement, puis de montrer qu'elle est aussi une progression arithmétique.
Posons \(T = \operatorname{lcm}(T_1, \ldots, T_t)\) et \(A = \max\{a_1, \ldots, a_t\}\) si \(t > 0\) ; \(T = 1\) et \(A = 0\) si \(t = 0\). Pour tout entier \(n \geq A\), l'intervalle \(\Delta_n = [n + 1, n + T]\) contient exactement \(T / T_i\) éléments de la \(i\)-ème ligne (\(1 \leq i \leq t\)). Donc le nombre d'éléments des \(k - t\) dernières lignes contenus dans \(\Delta_n\) ne dépend pas de \(n \geq A\). Il ne peut pas être nul, car ces lignes contiennent une infinité de nombres. Donc chaque \(\Delta_n\) (\(n \geq A\)) contient au moins un élément de ces lignes.
Par suite, pour tout entier \(d \geq 1\), l'intervalle \(\left[A + 1, A + (d+1)(k-t)T\right]\) contient au moins \((d+1)(k-t)\) éléments des \(k - t\) dernières lignes ; par le principe des tiroirs, il existe un indice \(x\) avec \(t + 1 \leq x \leq k\) (pouvant dépendre de \(d\)) tel que cet intervalle contienne au moins \(d + 1\) éléments de la ligne \(x\). On a alors
Comme il n'y a qu'un nombre fini de choix pour \(x\), il existe un indice \(x \geq t + 1\) tel que l'ensemble
soit infini. C'est la « ligne dense » annoncée.
D'après (i), pour tout \(d \in X\), le nombre
est un entier positif au plus égal à
Il n'y a donc qu'un nombre fini de valeurs possibles pour \(\beta_d\), et il existe un nombre \(T_x\) tel que l'ensemble
soit infini. On a \(f^d(a_x) = a_x + d \cdot T_x\) pour tout \(d \in Y\).
Montrons que la ligne \(x\) est une progression arithmétique, ce qui contredira l'hypothèse. Fixons un entier \(j \geq 1\). Comme \(Y\) est infini, on peut choisir \(y \in Y\) tel que \(y - j > \left| f^j(a_x) - (a_x + jT_x) \right|\). Les deux nombres
sont divisibles par \(y - j\) (le premier par (i)). Leur différence, \(f^j(a_x) - (a_x + jT_x)\), est donc divisible par \(y - j\) ; sa valeur absolue étant inférieure à \(y - j\), elle est nulle : \(f^j(a_x) = a_x + jT_x\). Ainsi toutes les lignes du Tableau sont des progressions arithmétiques.
Étape 3. Notons \(T_i\) le pas de la \(i\)-ème ligne et \(T = \operatorname{lcm}(T_1, \ldots, T_k)\). Montrons que \(f(n) - n = f(n + T) - (n + T)\) pour tout \(n\). Soit \(n\) un entier, situé dans la ligne \(i\). Alors \(f^j(n) = n + jT_i\) pour tout \(j\), et
La suite \(f(n) - n\) est donc périodique de période \(T\). \(\blacksquare\)
Remarques¶
Remarque 1. Une fois trouvée la ligne dense \(x\), on peut aussi conclure autrement : on montre qu'il existe un entier \(T_x^*\) tel que l'ensemble \(Y^* = \{ j \in \mathbb{Z}_{>0} \mid f^{j+1}(a_x) - f^j(a_x) = T_x^* \}\) soit infini, puis on conclut par un argument de divisibilité analogue.
Remarque 2. Réciproquement, toute façon de remplir le Tableau avec un nombre fini de progressions arithmétiques, de sorte que chaque entier positif apparaisse exactement une fois, donne une fonction \(f\) vérifiant les deux conditions. Par exemple, avec les lignes
on obtient \(f(n) = n + 2\) si \(n\) est pair et \(f(n) = n + 4\) si \(n\) est impair. Cet exemple montre que \(n \mapsto f(n) - n\) n'est pas forcément constante.