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é

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

\[x, \quad f(y) \quad \text{and} \quad f(y + f(x) - 1).\]

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).

Solution

Réponse : la fonction identité \(f(x) = x\) est l'unique 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

\[x > 2B \geq f(y) + f(y + f(x) - 1).\]

É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

\[f(t) > \frac{z - 1}{w} \cdot t + M ; \tag{1}\]

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

\[z + f(t - w) > f((t - w) + f(z) - 1) = f(t - w + w) = f(t).\]

Donc

\[f(t - w) \geq f(t) - (z - 1) > \frac{z - 1}{w}(t - w) + M,\]

ce qui contredit la minimalité de \(t\).

L'inégalité (1) est donc fausse pour tout \(t \geq 1\) ; on a prouvé à la place

\[f(t) \leq \frac{z - 1}{w} \cdot t + M. \tag{2}\]

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

\[\left(\frac{z - 1}{w}\right)^2 t + \left(\frac{z - 1}{w} + 1\right)M < t.\]

En appliquant deux fois (2), on obtient

\[f(f(t)) \leq \frac{z - 1}{w}f(t) + M \leq \frac{z - 1}{w}\left(\frac{z - 1}{w}t + M\right) + M < t,\]

ce qui contredit l'étape 2 et prouve l'étape 3.

Étape finale. D'après les étapes 2 et 3, on obtient

\[z = f(f(z)) \leq f(z) \leq z,\]

et \(f(z) = z\) pour tout entier \(z > 0\). \(\blacksquare\)