Shortlist 2010, A6¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Germany
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal
Solution officielle : Shortlist officielle 2010 (avec solutions), p. 14 (page 15 du PDF)
Énoncé¶
Suppose that \(f\) and \(g\) are two functions defined on the set of positive integers and taking positive integer values. Suppose also that the equations \(f(g(n)) = f(n) + 1\) and \(g(f(n)) = g(n) + 1\) hold for all positive integers. Prove that \(f(n) = g(n)\) for all positive integer \(n\).
Indices : les idées clés
- Images : \(f(g^k(x)) = f(x) + k\), donc \(f\) prend toutes les valeurs à partir de sa plus petite valeur \(a\) ; de même \(g\) à partir de \(b\).
- Classes : \(f(x) = f(y) \iff g(x) = g(y)\) ; on étudie les classes \([x]\) de cette relation et l'on montre \(a = b\).
- Itérations : \(f^{d+1}(n_f) = g^{d+1}(n_f) = a + d\), ou bien (solution 2) \(f(x) = g(x) = x + 1\) pour \(x \geq a\), puis \(f(n) + 1 = f(g(n)) = g(n) + 1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (deux solutions et une remarque).
Solution 1¶
Dans toute la solution, \(\mathbb{N}\) désigne l'ensemble des entiers strictement positifs. Pour toute fonction \(h : \mathbb{N} \to \mathbb{N}\) et tout entier \(k > 0\), on pose \(h^k(x) = \underbrace{h(h(\ldots h(x) \ldots))}_{k}\) (en particulier \(h^0(x) = x\)).
Remarquons que \(f(g^k(x)) = f(g^{k-1}(x)) + 1 = \cdots = f(x) + k\) pour tout entier \(k > 0\), et de même \(g(f^k(x)) = g(x) + k\). Soient \(a\) et \(b\) les plus petites valeurs prises par \(f\) et \(g\) respectivement ; disons \(f(n_f) = a\), \(g(n_g) = b\). Alors \(f(g^k(n_f)) = a + k\) et \(g(f^k(n_g)) = b + k\), donc \(f\) prend toutes les valeurs de l'ensemble \(N_f = \{a, a + 1, \ldots\}\), et \(g\) toutes celles de \(N_g = \{b, b + 1, \ldots\}\).
Ensuite, \(f(x) = f(y)\) implique \(g(x) = g(f(x)) - 1 = g(f(y)) - 1 = g(y)\) ; la réciproque est évidemment vraie aussi. On dit que \(x\) et \(y\) sont semblables (et l'on note \(x \sim y\)) si \(f(x) = f(y)\) (de façon équivalente, \(g(x) = g(y)\)). Pour tout \(x \in \mathbb{N}\), on pose \([x] = \{y \in \mathbb{N} : x \sim y\}\) ; évidemment \(y_1 \sim y_2\) pour tous \(y_1, y_2 \in [x]\), donc \([x] = [y]\) dès que \(y \in [x]\).
Étudions maintenant la structure des ensembles \([x]\).
Affirmation 1. Supposons \(f(x) \sim f(y)\) ; alors \(x \sim y\), c'est-à-dire \(f(x) = f(y)\). Par conséquent, chaque classe \([x]\) contient au plus un élément de \(N_f\), et au plus un élément de \(N_g\).
Preuve. Si \(f(x) \sim f(y)\), alors \(g(x) = g(f(x)) - 1 = g(f(y)) - 1 = g(y)\), donc \(x \sim y\). La seconde affirmation en découle, vu les ensembles de valeurs de \(f\) et de \(g\). \(\square\)
Précisons ensuite quelles classes ne contiennent pas de grands éléments.
Affirmation 2. Pour tout \(x \in \mathbb{N}\), on a \([x] \subseteq \{1, 2, \ldots, b - 1\}\) si et seulement si \(f(x) = a\). De même, \([x] \subseteq \{1, 2, \ldots, a - 1\}\) si et seulement si \(g(x) = b\).
Preuve. Montrons que \([x] \not\subseteq \{1, 2, \ldots, b - 1\} \iff f(x) > a\) ; la preuve de la seconde affirmation est analogue.
Remarquons que \(f(x) > a\) implique qu'il existe un \(y\) tel que \(f(y) = f(x) - 1\), donc \(f(g(y)) = f(y) + 1 = f(x)\), et ainsi \(x \sim g(y) \geq b\). Réciproquement, si \(b \leq c \sim x\), alors \(c = g(y)\) pour un certain \(y \in \mathbb{N}\), ce qui donne à son tour \(f(x) = f(g(y)) = f(y) + 1 \geq a + 1\), donc \(f(x) > a\). \(\square\)
L'affirmation 2 implique qu'il existe exactement une classe contenue dans \(\{1, \ldots, a - 1\}\) (à savoir la classe \([n_g]\)), ainsi qu'exactement une classe contenue dans \(\{1, \ldots, b - 1\}\) (la classe \([n_f]\)). Supposons un instant que \(a \leq b\) ; alors \([n_g]\) est aussi contenue dans \(\{1, \ldots, b - 1\}\), donc elle coïncide avec \([n_f]\). On obtient ainsi
Affirmation 3. \(a = b\).
Preuve. D'après l'affirmation 2, \([a] \neq [n_f]\), donc \([a]\) doit contenir un élément \(a' \geq b\), de nouveau d'après l'affirmation 2. Si \(a \neq a'\), alors \([a]\) contient deux éléments \(\geq a\), ce qui est impossible d'après l'affirmation 1. Donc \(a = a' \geq b\). De même, \(b \geq a\). \(\square\)
Nous pouvons maintenant prouver l'énoncé. Établissons d'abord le résultat suivant.
Affirmation 4. Pour tout entier \(d \geq 0\), \(f^{d+1}(n_f) = g^{d+1}(n_f) = a + d\).
Preuve. Récurrence sur \(d\). Pour \(d = 0\), l'énoncé découle de (1) et de l'affirmation 3. Ensuite, pour \(d \geq 1\), l'hypothèse de récurrence donne \(f^{d+1}(n_f) = f(f^d(n_f)) = f(g^d(n_f)) = f(n_f) + d = a + d\). L'égalité \(g^{d+1}(n_f) = a + d\) est analogue. (Le livret écrit « pour \(d > 1\) » ; il faut lire \(d \geq 1\).) \(\square\)
Enfin, pour tout \(x \in \mathbb{N}\), on a \(f(x) = a + d\) pour un certain \(d \geq 0\), donc \(f(x) = f(g^d(n_f))\) et par conséquent \(x \sim g^d(n_f)\). Il s'ensuit que \(g(x) = g(g^d(n_f)) = g^{d+1}(n_f) = a + d = f(x)\) d'après l'affirmation 4. \(\blacksquare\)
Solution 2¶
On part des mêmes observations, en introduisant la relation \(\sim\) et en prouvant l'affirmation 1 de la solution précédente.
Remarquons que \(f(a) > a\), sinon on aurait \(f(a) = a\) et donc \(g(a) = g(f(a)) = g(a) + 1\), ce qui est faux.
Affirmation 2'. \(a = b\).
Preuve. On peut supposer \(a \leq b\). Comme \(f(a) \geq a + 1\), il existe un \(x \in \mathbb{N}\) tel que \(f(a) = f(x) + 1\), ce qui équivaut à \(f(a) = f(g(x))\) et \(a \sim g(x)\). Comme \(g(x) \geq b \geq a\), l'affirmation 1 donne \(a = g(x) \geq b\), ce qui, avec \(a \leq b\), prouve l'affirmation. \(\square\)
La même méthode permet maintenant de trouver les valeurs \(f(a)\) et \(g(a)\).
Affirmation 3'. \(f(a) = g(a) = a + 1\).
Preuve. Supposons le contraire ; alors \(f(a) \geq a + 2\), donc il existe \(x, y \in \mathbb{N}\) tels que \(f(x) = f(a) - 2\) et \(f(y) = g(x)\) (puisque \(g(x) \geq a = b\)). On obtient alors \(f(a) = f(x) + 2 = f(g^2(x))\), donc \(a \sim g^2(x) \geq a\), et l'affirmation 1 donne \(a = g^2(x) = g(f(y)) = 1 + g(y) \geq 1 + a\) ; c'est impossible. L'égalité \(g(a) = a + 1\) est analogue. \(\square\)
Nous sommes prêts à prouver l'énoncé. Prouvons-le d'abord pour \(n \geq a\).
Affirmation 4'. Pour tout entier \(x \geq a\), on a \(f(x) = g(x) = x + 1\).
Preuve. Récurrence sur \(x\). Le cas de base \(x = a\) est l'affirmation 3', et l'hérédité découle de \(f(x + 1) = f(g(x)) = f(x) + 1 = (x + 1) + 1\) et du calcul analogue pour \(g(x + 1)\). \(\square\)
Enfin, pour un \(n \in \mathbb{N}\) quelconque, on a \(g(n) \geq a\), donc l'affirmation 4' donne \(f(n) + 1 = f(g(n)) = g(n) + 1\), d'où \(f(n) = g(n)\). \(\blacksquare\)
Remarque¶
Il n'est maintenant pas difficile de décrire toutes les fonctions \(f : \mathbb{N} \to \mathbb{N}\) vérifiant \(f(f(n)) = f(n) + 1\). Pour chacune de ces fonctions, il existe un \(n_0 \in \mathbb{N}\) tel que \(f(n) = n + 1\) pour tout \(n \geq n_0\), tandis que, pour chaque \(n < n_0\), \(f(n)\) est un nombre arbitraire supérieur ou égal à \(n_0\) (ces nombres peuvent être différents pour différents \(n < n_0\)).