Shortlist 2012, A6¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Suites et récurrences · Principe extrémal · Principe des tiroirs
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 16 (page 16 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(f : \mathbb{N} \to \mathbb{N}\) be a function, and let \(f^m\) be \(f\) applied \(m\) times. Suppose that for every \(n \in \mathbb{N}\) there exists a \(k \in \mathbb{N}\) such that \(f^{2k}(n) = n + k\), and let \(k_n\) be the smallest such \(k\). Prove that the sequence \(k_1, k_2, \ldots\) is unbounded.
Indices : les idées clés
- L'orbite de \(1\) : sur \(S = \{1, f(1), f^2(1), \ldots\}\), infini, \(f\) est injective, et \(g(n) = f^{2k_n}(n) = n + k_n\) est injective par minimalité de \(k_n\).
- Chaînes : \(S\) est réunion disjointe des chaînes \(C_t = \{t, g(t), g^2(t), \ldots\}\), et sur une chaîne \(f^n(1) = t + \frac{n - n_t}{2}\) (suites).
- Tiroirs : avec un nombre fini de chaînes, les \(N + 1\) valeurs \(f^n(1)\) seraient toutes inférieures à \(t_r + \frac{N}{2}\) ; il y a donc une infinité de chaînes, et l'une des \(k + 1\) premières saute plus de \(k\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution).
Solution¶
Restreignons-nous à l'ensemble
\(S\) n'est pas borné, car pour tout \(n \in S\) il existe \(k > 0\) tel que \(f^{2k}(n) = n + k\) soit dans \(S\). Clairement, \(f\) envoie \(S\) dans lui-même ; de plus, \(f\) est injective sur \(S\). En effet, si \(f^i(1) = f^j(1)\) avec \(i \neq j\), les valeurs \(f^m(1)\) se répéteraient périodiquement à partir d'un certain rang, et \(S\) serait fini.
Définissons \(g : S \to S\) par \(g(n) = f^{2k_n}(n) = n + k_n\). Montrons que \(g\) est aussi injective. Supposons \(g(a) = g(b)\) avec \(a < b\). Alors \(a + k_a = f^{2k_a}(a) = f^{2k_b}(b) = b + k_b\) implique \(k_a > k_b\). Comme \(f\) est injective sur \(S\), on obtient
Cela contredit la minimalité de \(k_a\), puisque \(0 < k_a - k_b < k_a\).
Soit \(T\) l'ensemble des éléments de \(S\) qui ne sont pas de la forme \(g(n)\) avec \(n \in S\). On a \(1 \in T\) puisque \(g(n) > n\) pour \(n \in S\), donc \(T\) n'est pas vide. Pour tout \(t \in T\), notons \(C_t = \{t, g(t), g^2(t), \ldots\}\), la chaîne issue de \(t\). Deux chaînes distinctes sont disjointes, car \(g\) est injective. Tout \(n \in S \setminus T\) s'écrit \(n = g(n')\) avec \(n' < n\), \(n' \in S\). En répétant cette observation, on voit que \(n \in C_t\) pour un \(t \in T\) : \(S\) est la réunion disjointe des chaînes \(C_t\).
Si \(f^n(1)\) est dans la chaîne \(C_t\) issue de \(t = f^{n_t}(1)\), alors \(n = n_t + 2a_1 + \cdots + 2a_j\) avec
Donc
Montrons maintenant que \(T\) est infini, par l'absurde. Supposons qu'il n'y ait qu'un nombre fini de chaînes \(C_{t_1}, \ldots, C_{t_r}\), issues de \(t_1 < \cdots < t_r\). Fixons \(N\). Si \(f^n(1)\), avec \(1 \leq n \leq N\), est dans \(C_t\), alors \(f^n(1) = t + \frac{n - n_t}{2} \leq t_r + \frac{N}{2}\) par (1). Mais alors les \(N + 1\) entiers naturels distincts \(1, f(1), \ldots, f^N(1)\) sont tous inférieurs à \(t_r + \frac{N}{2}\), donc \(N + 1 \leq t_r + \frac{N}{2}\). C'est une contradiction pour \(N\) assez grand ; donc \(T\) est infini.
Pour conclure, prenons un \(k \in \mathbb{N}\) quelconque et considérons les \(k + 1\) chaînes issues des \(k + 1\) premiers éléments de \(T\). Soit \(t\) le plus grand de ces éléments. Chacune de ces chaînes contient un nombre au plus égal à \(t\), et au moins l'une d'elles ne contient aucun des nombres \(t + 1, \ldots, t + k\). Il existe donc dans cette chaîne un nombre \(n\) tel que \(g(n) - n > k\), c'est-à-dire \(k_n > k\). En conclusion, la suite \(k_1, k_2, \ldots\) n'est pas bornée. \(\blacksquare\)