Aller au contenu

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

\[f^{g(n)+1}(n) + g^{f(n)}(n) = f(n + 1) - g(n + 1) + 1\]

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

\[f^{g(n)+1}(n) + g^{f(n)}(n) = f(n + 1) - g(n + 1) + 1\]

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

\[f\big(f^{g(n)}(n)\big) < f(n + 1) \quad \text{pour tout } n, \tag{1}\]

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

\[\text{(i)}_1, \text{(ii)}_1, \text{(i)}_2, \text{(ii)}_2, \ldots, \text{(i)}_n, \text{(ii)}_n, \ldots \tag{2}\]

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

\[f^{g(x-1)}(x - 1) \in \{1, \ldots, n\}. \tag{3}\]

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 ?