Shortlist 2015, A2¶
Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : Croatia
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 10 (page 11 du PDF)
Énoncé¶
Determine all functions \(f : \mathbb{Z} \to \mathbb{Z}\) with the property that
holds for all \(x, y \in \mathbb{Z}\).
Indices : les idées clés
- Substitutions bien choisies : trouver un \(z\) avec \(f(z) = -1\), puis l'injecter pour obtenir \(f(x+1) = f(f(x))\).
- Différences consécutives (solution 1) : montrer que \(f(x+1) - f(x)\) est constant, donc que \(f\) est affine.
- Injectivité ou périodicité (solution 2) : si \(f\) n'est pas injective, elle est périodique à partir d'un rang, donc bornée, et l'on étudie son minimum et son maximum.
- Ensemble stable par différence (solution 3) : un tel sous-ensemble de \(\mathbb{Z}\) est l'ensemble des multiples d'un entier \(k\) (division euclidienne).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (trois solutions et une remarque).
Réponse. Il y a exactement deux fonctions : la fonction constante \(x \mapsto -1\) et la fonction successeur \(x \mapsto x + 1\).
Solution 1¶
On vérifie immédiatement que les deux fonctions de la réponse conviennent. Soit maintenant \(f\) une solution de
Une valeur \(-1\). Avec \(x = 0\) et \(y = f(0)\), (1) donne \(f\big(-f(f(0))\big) = -1\) : le nombre \(z = -f\big(f(0)\big)\) vérifie \(f(z) = -1\). En substituant \(y = z\) dans (1), on obtient
et (1) se simplifie en
\(f\) est affine. Étudions \(f(x+1) - f(x)\). En appliquant (3) avec \(y = x\), puis (2) :
Or (3) appliqué à \((x - 1, x)\) donne \(f\big(x - 1 - f(x)\big) = f(x) - f(x) - 1 = -1\). Donc
Une récurrence immédiate dans les deux sens donne \(f(x) = Ax + B\) pour tout \(x \in \mathbb{Z}\), avec \(B = f(0)\). En reportant dans (2) :
Avec \(x = 0\) et \(x = 1\), on obtient \(A + B = AB + B\) et \(A^2 = A\). La seconde équation donne \(A = 0\) ou \(A = 1\).
- Si \(A = 1\), la première donne \(B = 1\) : \(f\) est la fonction successeur.
- Si \(A = 0\), \(f\) est constante, et (1) impose que sa valeur soit \(-1\). \(\blacksquare\)
Solution 2¶
On établit (2) et (3) comme dans la solution 1.
Cas injectif. Si \(f\) est injective, (2) donne \(f(x) = x + 1\) : c'est la fonction successeur.
Cas non injectif. Supposons qu'il existe des entiers \(a > b\) avec \(f(a) = f(b)\). Par récurrence, en utilisant (2) (\(f(a+1) = f(f(a)) = f(f(b)) = f(b+1)\), etc.), on a \(f(a + n) = f(b + n)\) pour tout entier \(n \geq 0\). La suite \(\gamma_n = f(b + n)\) est donc périodique, en particulier bornée, et les nombres
existent.
Choisissons un entier \(y\) tel que \(f(y) = \varphi\), puis un entier \(x \geq a\) tel que \(f\big(x - f(y)\big) = \varphi\) (possible car la suite périodique \((\gamma_n)\) prend la valeur \(\varphi\) pour des indices arbitrairement grands). Par définition de \(\varphi\) et d'après (3),
d'où \(\varphi \geq -1\). Le même raisonnement appliqué à \(\psi\) donne \(\psi \leq -1\). Comme \(\varphi \leq \psi\), on a \(\varphi = \psi = -1\) : autrement dit \(f(t) = -1\) pour tout entier \(t \geq a\).
Enfin, pour un entier \(y\) quelconque, choisissons \(x\) assez grand pour que \(x + 1 \geq a\) et \(x - f(y) \geq a\). D'après (3) et ce qui précède,
Donc \(f\) est la fonction constante égale à \(-1\). \(\blacksquare\)
Solution 3¶
Posons \(d = f(0)\) et notons \(f^3(y) = f\big(f(f(y))\big)\). En substituant \(x = f(y)\) dans (1), on obtient
En remplaçant \(x\) par \(f(x)\) dans (1), on obtient \(f\big(f(x) - f(y)\big) = f^3(x) - f(y) - 1\), ce qui, grâce à (4), devient
L'ensemble \(E\). Considérons
Soient \(a, b \in E\) ; choisissons \(x, y\) avec \(f(x) = a + d\) et \(f(y) = b + d\). Alors (5) donne \(f(a - b) = (a - b) + d\), ce qui montre que \(a - b \in E\). Ainsi
De plus \(0 \in E\) (car \(f(0) = d\)). Si \(E = \{0\}\), \(f\) est constante et (1) montre que sa valeur est \(-1\).
Supposons désormais que \(E\) contient un élément non nul. Alors (6) entraîne que \(E\) est l'ensemble des multiples d'un entier \(k > 0\), à savoir \(k = \min\{|x| : x \in E, x \neq 0\}\) (on le vérifie par un argument de division euclidienne). Ainsi
D'après (5) et (7), \(f(kt) = kt + d\) pour tout \(t \in \mathbb{Z}\), en particulier \(f(k) = k + d\). En comparant les substitutions \(y = 0\) et \(y = k\) dans (1) (qui ont le même membre \(f(f(x))\)), on obtient
Autrement dit, sur chaque classe de résidus modulo \(k\), \(f\) est affine de pente \(1\).
D'après (7), l'ensemble des valeurs de \(f\) est une telle classe de résidus. Il existe donc une constante \(c\) telle que \(f\big(f(x)\big) = f(x) + c\) pour tout \(x\), et (1) se simplifie en
D'autre part, en lisant (1) modulo \(k\) grâce à (7), on obtient \(d \equiv d - d - 1\), c'est-à-dire \(d \equiv -1 \pmod{k}\). Donc, toujours par (7), \(f\) prend la valeur \(-1\).
En appliquant (9) à un \(y\) tel que \(f(y) = -1\), on obtient \(f(x+1) = f(x) + c\) : \(f\) est affine de pente \(c\). Alors (8) impose \(c = 1\), donc il existe une constante \(d'\) avec \(f(x) = x + d'\) pour tout \(x\). Avec \(x = 0\), on a \(d' = d\), et enfin (4) donne \(y + 3d = y + 2d + 1\), soit \(d = 1\) : \(f\) est la fonction successeur. \(\blacksquare\)
Remarques¶
Remarque 1. Une fois (2) et (3) obtenues, il y a d'autres façons de les combiner pour obtenir la linéarité de \(f\). Par exemple, en utilisant (2) trois fois de suite puis (3) avec \(x = f(y)\) :
pour tout \(y \in \mathbb{Z}\). Ainsi \(f\) est affine séparément sur les entiers pairs et sur les entiers impairs, avec la même pente ; on conclut par une étude de cas directe. La solution 2 présente une autre façon d'exploiter (2) et (3), et la solution 3 montre qu'on peut aussi partir tout autrement, sans ces équations.