Shortlist 2014, A4¶
Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : Netherlands
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2014 (avec solutions), p. 14 (page 15 du PDF)
Énoncé¶
Determine all functions \(f : \mathbb{Z} \to \mathbb{Z}\) satisfying
for all integers \(m\) and \(n\).
Indices : les idées clés
- Substitutions : avec \(g(m) = f(3m) - f(m) + 2014\), l'équation devient \(f(f(m) + n) = g(m) + f(n)\), puis, par récurrence dans les deux sens, \(f(t f(m) + n) = t g(m) + f(n)\).
- Proportionnalité : en comparant deux choix de \((m, n, t)\), on obtient \(g = \alpha f\) pour une constante \(\alpha \neq 0\), d'où \(f(3^k m) - \beta = (1 + \alpha)^k (f(m) - \beta)\).
- Euler-Fermat : \(f\) prend une valeur \(d\) non divisible par \(3\) (car \(3 \nmid 2014\)), et l'on choisit \(k\) avec \(d \mid 3^k - 1\) ; les deux expressions de \(f(3^k m)\) forcent \(f\) à être affine.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et deux remarques).
Réponse : la seule solution est \(n \mapsto 2n + 1007\).
Solution¶
Soit \(f\) une solution, et notons (1) l'équation de l'énoncé. Posons \(C = 1007\) et définissons \(g : \mathbb{Z} \to \mathbb{Z}\) par \(g(m) = f(3m) - f(m) + 2C\) pour tout \(m\) ; en particulier \(g(0) = 2C\). L'équation (1) se réécrit
pour tous \(m, n \in \mathbb{Z}\). Par récurrence dans les deux sens, on en déduit
pour tous \(m, n, t \in \mathbb{Z}\). Appliquons-le, pour \(r \in \mathbb{Z}\) quelconque, aux triplets \((m, n, t) = \big(r, 0, f(0)\big)\) et \(\big(0, 0, f(r)\big)\) :
Si \(f(0)\) était nul, alors \(g(0) = 2C > 0\) imposerait que \(f\) soit identiquement nulle, ce qui contredit (1). Donc \(f(0) \neq 0\), et l'égalité précédente donne \(g(r) = \alpha f(r)\), où \(\alpha = \frac{g(0)}{f(0)}\) est une constante non nulle.
La définition de \(g\) donne alors \(f(3m) = (1 + \alpha) f(m) - 2C\), c'est-à-dire
pour tout \(m\), où \(\beta = \frac{2C}{\alpha}\). Par récurrence sur \(k\),
pour tout entier \(k \geq 0\) et tout \(m\).
Comme \(3 \nmid 2014\), l'équation (1) montre que \(f\) prend au moins une valeur \(d = f(a)\) non divisible par \(3\). Par (2), \(f(n + td) = f(n) + t g(a) = f(n) + \alpha t f(a)\), c'est-à-dire
pour tous \(n, t \in \mathbb{Z}\).
Fixons un entier \(k > 0\) tel que \(d \mid 3^k - 1\), ce qui est possible car \(\operatorname{pgcd}(3, d) = 1\) : par le théorème d'Euler-Fermat, on peut prendre \(k = \varphi(\lvert d \rvert)\). Pour tout \(m\), (5) donne alors
ce qui, avec (4), donne \(\big((1 + \alpha)^k - 1\big)\big(f(m) - \beta\big) = \alpha (3^k - 1) m\). Comme \(\alpha \neq 0\), le membre de droite est non nul pour \(m \neq 0\), donc le premier facteur du membre de gauche est non nul. Ainsi
Donc \(f\) est affine : \(f(m) = Am + \beta\) pour tout \(m\), avec une constante \(A \in \mathbb{Q}\). En reportant dans (1), on obtient \((A^2 - 2A) m + (A\beta - 2C) = 0\) pour tout \(m\), ce qui équivaut à
La première équation donne \(A \in \{0, 2\}\), et comme \(C \neq 0\), la seconde impose
Donc \(f\) est la fonction annoncée, et comme les valeurs (7) vérifient bien (6), cette fonction convient. \(\blacksquare\)
Remarques¶
Remarque 1. On peut voir que \(\alpha = 2\). Une version plus terre à terre de la solution commence par prouver directement ce fait, en substituant des valeurs particulières dans (1), par exemple ainsi.
Posons \(D = f(0)\). Avec \(m = 0\) dans (1), on obtient
pour tout \(n\). En particulier, pour \(n = 0, D, 2D\) : \(f(D) = 2C + D\), \(f(2D) = f(D) + 2C = 4C + D\) et \(f(3D) = f(2D) + 2C = 6C + D\). En substituant \(m = D\) et \(n = r - D\) dans (1), puis en appliquant (8) avec \(n = r - D\), on trouve
c'est-à-dire \(f(r + 2C) = f(r) + 4C\). Par récurrence dans les deux sens,
pour tous \(n, t \in \mathbb{Z}\).
Lemme. Si deux entiers \(a\) et \(b\) vérifient \(f(n + a) = f(n) + b\) pour tout \(n\), alors \(b = 2a\).
Preuve. Par récurrence dans les deux sens, \(f(n + ta) = f(n) + tb\) pour tous \(n, t\). En prenant \((n, t) = (0, 2C)\) dans cette égalité, et \((n, t) = (0, a)\) dans (9), on obtient \(f(2aC) - f(0) = 2bC = 4aC\), et comme \(C \neq 0\), le lemme suit. \(\square\)
Par (1), pour tout \(m\), les nombres \(a = f(m)\) et \(b = f(3m) - f(m) + 2C\) ont la propriété du lemme, donc
Avec (3), cela montre bien que \(\alpha = 2\). On peut alors terminer comme ci-dessus, mais en connaissant \(\alpha = 2\), on obtient directement \(f(m) = 2m + C\) sans passer par toutes les fonctions affines. Il reste à vérifier que cette fonction vérifie (1).
Remarque 2. On peut se demander ce qui se passe si l'on remplace \(2014\) par un entier \(B\) quelconque.
Si \(B\) est impair, il n'y a pas de solution, comme on le voit avec les mêmes idées que ci-dessus.
Si \(B \neq 0\) est pair, la seule solution est \(n \mapsto 2n + \frac{B}{2}\). Dans le cas \(3 \nmid B\), c'est essentiellement ce qui a été prouvé ; dans le cas général, il faut une idée de plus. En écrivant \(B = 3^\nu k\) avec \(3 \nmid k\), on obtient de la même manière \(f(n) = 2n + \frac{B}{2}\) pour tous les \(n\) divisibles par \(3^\nu\), puis la formule \(f(3n) = 3f(n) - B\) permet de traiter les autres cas.
Enfin, pour \(B = 0\), il y a d'autres solutions que \(n \mapsto 2n\). On peut montrer que toutes ces autres solutions sont périodiques ; pour ne citer qu'un exemple, pour tous entiers pairs \(r\) et \(s\), la fonction
a aussi la propriété voulue.