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)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
É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\).