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é

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}\]