Shortlist 2008, A3¶
Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal
Solution officielle : Shortlist officielle 2008 (avec solutions), p. 11 (page 12 du PDF)
Énoncé¶
Let \(S \subseteq \mathbb{R}\) be a set of real numbers. We say that a pair \((f, g)\) of functions from \(S\) into \(S\) is a Spanish Couple on \(S\), if they satisfy the following conditions:
(i) Both functions are strictly increasing, i.e. \(f(x) < f(y)\) and \(g(x) < g(y)\) for all \(x, y \in S\) with \(x < y\);
(ii) The inequality \(f(g(g(x))) < g(f(x))\) holds for all \(x \in S\).
Decide whether there exists a Spanish Couple
(a) on the set \(S = \mathbb{N}\) of positive integers;
(b) on the set \(S = \{a - 1/b : a, b \in \mathbb{N}\}\).
Indices : les idées clés
- Itérées : sur \(\mathbb{N}\), une récurrence donne \(g^k(x) \leq f(x)\) pour tout \(k\), grâce à \(g(g_{k+1}(x)) = g_k(g_2(x)) \leq f(g_2(x)) < g(f(x))\).
- Suite bornée : si \(x_0 < g(x_0)\), la suite \(x_k = g^k(x_0)\) est strictement croissante et majorée par \(f(x_0)\), ce qui est impossible dans \(\mathbb{N}\) (bon ordre).
- Exemple pour (b) : \(f(a - 1/b) = a + 1 - 1/b\) et \(g(a - 1/b) = a - 1/(b + 3^a)\) ; les composées se comparent via \(2 \cdot 3^a < 3^{a+1}\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution et une remarque).
Solution¶
Réponse : non pour la partie (a), oui pour la partie (b).
(a) Dans toute la solution, on utilise la notation \(g_k(x) = \underbrace{g(g(\ldots g(x) \ldots))}_{k}\), y compris \(g_0(x) = x\).
Supposons qu'il existe un couple espagnol \((f, g)\) sur l'ensemble \(\mathbb{N}\). D'après la propriété (i), on a \(f(x) \geq x\) et \(g(x) \geq x\) pour tout \(x \in \mathbb{N}\).
Montrons que \(g_k(x) \leq f(x)\) pour tout \(k \geq 0\) et tout entier \(x > 0\). La preuve se fait par récurrence sur \(k\). On a déjà le cas de base \(k = 0\) puisque \(x \leq f(x)\). Pour passer de \(k\) à \(k + 1\), on applique l'hypothèse de récurrence à \(g_2(x)\) au lieu de \(x\), puis on applique (ii) :
Comme \(g\) est croissante, il s'ensuit que \(g_{k+1}(x) < f(x)\). L'affirmation est prouvée.
Si \(g(x) = x\) pour tout \(x \in \mathbb{N}\), alors \(f(g(g(x))) = f(x) = g(f(x))\), ce qui contredit (ii). On peut donc choisir un \(x_0 \in S\) tel que \(x_0 < g(x_0)\). Considérons la suite \(x_0, x_1, \ldots\), où \(x_k = g_k(x_0)\). Cette suite est croissante. En effet, \(x_0 < g(x_0) = x_1\), et \(x_k < x_{k+1}\) implique \(x_{k+1} = g(x_k) < g(x_{k+1}) = x_{k+2}\).
On obtient donc une suite strictement croissante \(x_0 < x_1 < \cdots\) d'entiers strictement positifs, qui est par ailleurs majorée, à savoir par \(f(x_0)\). C'est impossible dans l'ensemble \(\mathbb{N}\) des entiers strictement positifs ; il n'existe donc pas de couple espagnol sur \(\mathbb{N}\).
(b) Voici un couple espagnol sur l'ensemble \(S = \{a - 1/b : a, b \in \mathbb{N}\}\). Posons
Ces fonctions sont évidemment croissantes. La condition (ii) est vérifiée, puisque
Remarque¶
Un autre exemple de couple espagnol est \(f(a - 1/b) = 3a - 1/b\), \(g(a - 1/b) = a - 1/(a + b)\). Plus généralement, en posant \(f(a - 1/b) = h(a) - 1/b\), \(g(a - 1/b) = a - 1/G(a, b)\) avec \(h\) croissante et \(G\) croissante en chacune des deux variables, on obtient que \(f \circ g \circ g < g \circ f\) est vrai si \(G(a, G(a, b)) < G(h(a), b)\). Une recherche parmi les seules fonctions linéaires \(h(a) = Ca\), \(G(a, b) = Aa + Bb\) montre que tous entiers \(A > 0\), \(C > 2\) et \(B = 1\) donnent un couple espagnol (dans l'exemple ci-dessus, \(A = 1\), \(C = 3\)). L'exemple du proposant correspond à \(h(a) = a + 1\), \(G(a, b) = 3^a + b\).