Aller au contenu

Shortlist 2007, A2

Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : Bulgaria

Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 10 (page 11 du PDF)

Énoncé

On considère les fonctions \(f : \mathbb{N} \to \mathbb{N}\) qui vérifient la condition

\[f(m + n) \geq f(m) + f(f(n)) - 1 \tag{1}\]

pour tous \(m, n \in \mathbb{N}\). Trouver toutes les valeurs possibles de \(f(2007)\).

(\(\mathbb{N}\) désigne l'ensemble des entiers strictement positifs.)

Énoncé original (anglais)

Consider those functions \(f : \mathbb{N} \to \mathbb{N}\) which satisfy the condition

\[f(m + n) \geq f(m) + f(f(n)) - 1 \tag{1}\]

for all \(m, n \in \mathbb{N}\). Find all possible values of \(f(2007)\).

(\(\mathbb{N}\) denotes the set of all positive integers.)

Indices : les idées clés
  • Monotonie : (1) avec \(m > n\) donne \(f(m) \geq f(n) + f(f(m - n)) - 1 \geq f(n)\) (substitutions).
  • Écart maximal : si \(f(n) > n\), alors \(f(f(n) - n) \leq 1\), donc \(f(n) - n\) est borné ; avec \(c = \max(f(n) - n)\) atteint en \(k\), \(f(2k) \geq 2(k + c) - 1\) force \(c \leq 1\), d'où \(f(2007) \leq 2008\).
  • Exemples : \(f_j(n) = \max\{1, n + j - 2007\}\) pour \(j \leq 2007\), et \(f_{2008}(n) = n\) ou \(n + 1\) selon que \(2007 \nmid n\) ou \(2007 \mid n\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution et une remarque).

Réponse : \(1, 2, \ldots, 2008\).

Solution

Supposons qu'une fonction \(f : \mathbb{N} \to \mathbb{N}\) vérifie (1). Pour des entiers strictement positifs quelconques \(m > n\), (1) donne

\[f(m) = f(n + (m - n)) \geq f(n) + f(f(m - n)) - 1 \geq f(n),\]

donc \(f\) est croissante (au sens large).

La fonction \(f \equiv 1\) est évidemment solution. Pour trouver d'autres solutions, supposons \(f \not\equiv 1\) et prenons le plus petit \(a \in \mathbb{N}\) tel que \(f(a) > 1\). Alors \(f(b) \geq f(a) > 1\) pour tout entier \(b \geq a\).

Supposons que \(f(n) > n\) pour un certain \(n \in \mathbb{N}\). On a alors

\[f(f(n)) = f\big((f(n) - n) + n\big) \geq f(f(n) - n) + f(f(n)) - 1,\]

donc \(f(f(n) - n) \leq 1\) et par conséquent \(f(n) - n < a\). Il existe donc une valeur maximale de l'expression \(f(n) - n\) ; notons-la \(c\), et soit \(f(k) - k = c \geq 1\). En utilisant la monotonie avec (1), on obtient

\[2k + c \geq f(2k) = f(k + k) \geq f(k) + f(f(k)) - 1 \geq f(k) + f(k) - 1 = 2(k + c) - 1 = 2k + (2c - 1),\]

donc \(c \leq 1\) et \(f(n) \leq n + 1\) pour tout \(n \in \mathbb{N}\). En particulier, \(f(2007) \leq 2008\).

Donnons maintenant une famille d'exemples montrant que toutes les valeurs de \(1\) à \(2008\) peuvent être atteintes. Soient

\[f_j(n) = \max\{1, n + j - 2007\} \quad \text{pour } j = 1, 2, \ldots, 2007 ; \qquad f_{2008}(n) = \begin{cases} n, & 2007 \nmid n, \\ n + 1, & 2007 \mid n. \end{cases}\]

Montrons que ces fonctions vérifient la condition (1) ; évidemment \(f_j(2007) = j\).

Pour vérifier la condition (1) pour la fonction \(f_j\) (\(j \leq 2007\)), remarquons d'abord que \(f_j\) est croissante et que \(f_j(n) \leq n\), donc \(f_j(f_j(n)) \leq f_j(n) \leq n\) pour tout \(n \in \mathbb{N}\). Si \(f_j(m) = 1\), l'inégalité (1) est claire puisque \(f_j(m + n) \geq f_j(n) \geq f_j(f_j(n)) = f_j(m) + f_j(f_j(n)) - 1\). Sinon,

\[f_j(m) + f_j(f_j(n)) - 1 \leq (m + j - 2007) + n = (m + n) + j - 2007 = f_j(m + n).\]

Dans le cas \(j = 2008\), on a clairement \(n + 1 \geq f_{2008}(n) \geq n\) pour tout \(n \in \mathbb{N}\) ; de plus, on a aussi \(n + 1 \geq f_{2008}(f_{2008}(n))\). C'est trivial si \(f_{2008}(n) = n\) ; sinon, \(f_{2008}(n) = n + 1\), ce qui implique \(2007 \nmid n + 1\), et donc \(n + 1 = f_{2008}(n + 1) = f_{2008}(f_{2008}(n))\).

Donc, si \(2007 \mid m + n\), alors

\[f_{2008}(m + n) = m + n + 1 = (m + 1) + (n + 1) - 1 \geq f_{2008}(m) + f_{2008}(f_{2008}(n)) - 1.\]

Sinon, \(2007 \nmid m + n\), donc \(2007 \nmid m\) ou \(2007 \nmid n\). Dans le premier cas, on a \(f_{2008}(m) = m\), et dans le second \(f_{2008}(f_{2008}(n)) = f_{2008}(n) = n\), ce qui donne

\[f_{2008}(m) + f_{2008}(f_{2008}(n)) - 1 \leq (m + n + 1) - 1 = f_{2008}(m + n). \qquad \blacksquare\]

Remarque

Les exemples ci-dessus ne sont pas uniques. Les valeurs \(1, 2, \ldots, 2008\) peuvent être atteintes de plusieurs façons. Voici deux autres constructions pour \(j \leq 2007\), sans preuve :

\[g_j(n) = \begin{cases} 1, & n < 2007, \\ j, & n = 2007, \\ n, & n > 2007 ; \end{cases} \qquad h_j(n) = \max\left\{1, \left\lfloor \frac{jn}{2007} \right\rfloor\right\}.\]

L'exemple pour \(j = 2008\) peut aussi se généraliser. En particulier, en choisissant un diviseur \(d > 1\) de \(2007\), on peut poser

\[f_{2008,d}(n) = \begin{cases} n, & d \nmid n, \\ n + 1, & d \mid n. \end{cases}\]

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.
  • 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 ?