Shortlist 2009, A3¶
Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : France
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 15 (page 17 du PDF)
Problème 5 de l'OIM 2009
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2009, où il était le problème 5 (jour 2).
Énoncé¶
Déterminer toutes les fonctions \(f\) de l'ensemble des entiers strictement positifs dans lui-même telles que, pour tous \(x\) et \(y\), il existe un triangle non aplati de côtés de longueurs
Énoncé original (anglais)
Determine all functions \(f\) from the set of positive integers into the set of positive integers such that for all \(x\) and \(y\) there exists a non degenerated triangle with sides of lengths
Indices : les idées clés
- \(f(1) = 1\) : sinon \(f\) serait \(m\)-périodique, donc bornée, ce que contredit un très grand côté \(x\).
- Involution : \(x = z\), \(y = 1\) donne \(f(f(z)) = z\).
- \(f(z) \leq z\) : sinon une majoration linéaire \(f(t) \leq \frac{z - 1}{w}t + M\), obtenue avec le plus petit contre-exemple, appliquée deux fois contredit \(f(f(t)) = t\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2009 (une solution).
Réponse : la fonction identité \(f(x) = x\) est l'unique solution.
Solution¶
Si \(f(x) = x\) pour tout entier \(x > 0\), les trois longueurs sont \(x\), \(y = f(y)\) et \(z = f(y + f(x) - 1) = x + y - 1\). Comme \(x \geq 1\), \(y \geq 1\), on a \(z \geq \max\{x, y\} > \lvert x - y \rvert\) et \(z < x + y\). Il s'ensuit qu'un triangle de ces longueurs existe et n'est pas dégénéré. Prouvons en plusieurs étapes qu'il n'y a pas d'autre solution.
Étape 1. Montrons que \(f(1) = 1\). Si l'on avait \(f(1) = 1 + m > 1\), on obtiendrait \(f(y) = f(y + m)\) pour tout \(y\) en considérant le triangle de côtés \(1\), \(f(y)\) et \(f(y + m)\). Donc \(f\) serait \(m\)-périodique et par conséquent bornée. Soit \(B\) un majorant, \(f(x) \leq B\). En choisissant \(x > 2B\), on obtient la contradiction
Étape 2. Pour tout entier \(z > 0\), on a \(f(f(z)) = z\). En prenant \(x = z\) et \(y = 1\), cela découle immédiatement de l'étape 1.
Étape 3. Pour tout entier \(z \geq 1\), on a \(f(z) \leq z\). Montrons que le contraire mène à une contradiction. Supposons \(w + 1 = f(z) > z\) pour un certain \(z\). D'après l'étape 1, on sait que \(w \geq z \geq 2\). Soit \(M = \max\{f(1), f(2), \ldots, f(w)\}\) la plus grande valeur de \(f\) sur les \(w\) premiers entiers. Montrons d'abord qu'il n'existe aucun entier \(t > 0\) tel que
sinon, considérons le plus petit tel \(t\). Par définition de \(M\), on a \(t > w\). En prenant \(x = z\) et \(y = t - w\), l'inégalité triangulaire donne
Donc
ce qui contredit la minimalité de \(t\).
L'inégalité (1) est donc fausse pour tout \(t \geq 1\) ; on a prouvé à la place
Avec (2), terminons la preuve de l'étape 3. Comme \(z \leq w\), on a \(\frac{z - 1}{w} < 1\), et l'on peut choisir un entier \(t\) assez grand pour que
En appliquant deux fois (2), on obtient
ce qui contredit l'étape 2 et prouve l'étape 3.
Étape finale. D'après les étapes 2 et 3, on obtient
et \(f(z) = z\) pour tout entier \(z > 0\). \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 A4 ★★☆☆☆ : Une fonction non bornée, additive dès que \(f(m + n)\) est un record, est affine sur une progression arithmétique.
- 2011 A4 ★★★☆☆ : Trouver les couples de fonctions des entiers vérifiant une équation où chacune est itérée un nombre de fois donné par l'autre.
- 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 ?
- 2007 A2 ★★★☆☆ : Sous la condition \(f(m + n) \geq f(m) + f(f(n)) - 1\), quelles valeurs peut prendre \(f(2007)\) ?