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
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
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
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
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
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
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,
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
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
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 :
L'exemple pour \(j = 2008\) peut aussi se généraliser. En particulier, en choisissant un diviseur \(d > 1\) de \(2007\), on peut poser
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 ?