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é¶
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).
Solution¶
Réponse : la seule paire est \(f(n) = n\) et \(g(n) = 1\) pour tout \(n\).
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.