Shortlist 2011, A4¶
Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Récurrence et constructions récursives · Principe extrémal
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 18 (page 19 du PDF)
Énoncé¶
Déterminer tous les couples \((f, g)\) de fonctions de l'ensemble des entiers strictement positifs dans lui-même qui vérifient
pour tout entier \(n\) strictement positif. Ici, \(f^k(n)\) désigne \(\underbrace{f(f(\ldots f}_{k}(n) \ldots))\).
Énoncé original (anglais)
Determine all pairs \((f, g)\) of functions from the set of positive integers to itself that satisfy
for every positive integer \(n\). Here, \(f^k(n)\) means \(\underbrace{f(f(\ldots f}_{k}(n) \ldots))\).
Indices : les idées clés
- Une inégalité suffit : la relation implique \(f\big(f^{g(n)}(n)\big) < f(n + 1)\) pour tout \(n\).
- Principe extrémal : la plus petite valeur \(y_1\) de \(f\) n'est atteinte qu'en \(1\) ; plus généralement, en notant \(y_1 < y_2 < \cdots\) les valeurs de \(f\), on montre que \(y_n\) n'est atteinte qu'en \(n\) et que \(y_n = n\).
- Récurrence : on obtient \(f(n) = n\), puis la relation devient \(g^n(n) + g(n + 1) = 2\), d'où \(g = 1\) (substitutions).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution et une remarque).
Réponse : la seule paire est \(f(n) = n\) et \(g(n) = 1\) pour tout \(n\).
Solution¶
La relation implique
ce qui suffira à déterminer \(f\).
Soient \(y_1 < y_2 < \cdots\) toutes les valeurs prises par \(f\) (cette suite peut être finie ou infinie). On va montrer que, pour tout \(n > 0\), la fonction \(f\) prend au moins \(n\) valeurs, et que l'on a (i)\(_n\) : \(f(x) = y_n\) si et seulement si \(x = n\), et (ii)\(_n\) : \(y_n = n\). La preuve suit le schéma
Pour commencer, considérons un \(x\) tel que \(f(x) = y_1\). Si \(x > 1\), alors (1) s'écrit \(f\big(f^{g(x-1)}(x - 1)\big) < y_1\), ce qui contredit la minimalité de \(y_1\). Donc \(f(x) = y_1\) équivaut à \(x = 1\), ce qui établit (i)\(_1\).
Supposons maintenant que, pour un certain \(n\), (i)\(_n\) soit établie, ainsi que toutes les affirmations précédentes de (2). Ces affirmations impliquent que, pour tout \(k \geq 1\) et tout \(a < n\), on a \(f^k(x) = a\) si et seulement si \(x = a\).
Chaque valeur \(y_i\) avec \(1 \leq i \leq n\) est prise en l'unique entier \(i\), donc \(y_{n+1}\) existe. Prenons un \(x\) quelconque tel que \(f(x) = y_{n+1}\) ; on a nécessairement \(x > n\). En appliquant (1) à \(x - 1\), on obtient \(f\big(f^{g(x-1)}(x - 1)\big) < y_{n+1}\), ce qui implique
Posons \(b = f^{g(x-1)}(x - 1)\). Si \(b < n\), on aurait \(x - 1 = b\), ce qui contredit \(x > n\). Donc \(b = n\), et par suite \(y_n = n\), ce qui prouve (ii)\(_n\). Ensuite, par (i)\(_n\), on a maintenant \(f(k) = n \iff k = n\) ; en supprimant toutes les itérations de \(f\) dans (3), on obtient \(x - 1 = b = n\), ce qui prouve (i)\(_{n+1}\).
Toutes les affirmations de (2) sont donc vraies, et \(f(n) = n\) pour tout \(n\). La relation entre \(f\) et \(g\) s'écrit alors \(n + g^n(n) = n + 1 - g(n + 1) + 1\), soit \(g^n(n) + g(n + 1) = 2\), d'où l'on tire immédiatement \(g(n) = 1\) pour tout \(n\). \(\blacksquare\)
Remarque¶
Plusieurs variantes de cette solution sont possibles. Par exemple, on peut d'abord prouver par récurrence que les \(n\) plus petites valeurs de \(f\) sont exactement \(f(1) < \cdots < f(n)\), puis procéder ainsi. On a certainement \(f(n) \geq n\) pour tout \(n\). S'il existe \(n\) tel que \(f(n) > n\), alors \(f(x) > x\) pour tout \(x \geq n\). On en déduit \(f^{g(n)+1}(n) > f^{g(n)}(n) > \cdots > f(n)\). Mais on a aussi \(f^{g(n)+1}(n) < f(n + 1)\). Une valeur de \(f\) se glisse ainsi entre \(f(n)\) et \(f(n + 1)\), ce qui est contradictoire.
Dans tous les cas, l'inégalité (1) joue un rôle essentiel.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2024 A4 ★★☆☆☆ : Quels ensembles de puissances de \(2\) peuvent être exactement l'ensemble des défauts d'additivité \(f(a + b) - f(a) - f(b)\) ?
- 2014 A4 ★★★☆☆ : Trouver les fonctions de \(\mathbb{Z}\) telles que \(f(f(m) + n) + f(m) = f(n) + f(3m) + 2014\).
- 2009 A3 ★★★☆☆ · OIM P5 : Trouver les fonctions telles que \(x\), \(f(y)\) et \(f(y + f(x) - 1)\) soient toujours les côtés d'un triangle.
- 2008 A3 ★★★☆☆ : Deux fonctions croissantes telles que \(f(g(g(x))) < g(f(x))\) : existent-elles sur \(\mathbb{N}\), puis sur un ensemble plus riche ?