Shortlist 2013, A5¶

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

Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Double comptage · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 16 (page 16 du PDF)

Énoncé¶

Let $\mathbb{Z}_{\geq 0}$ be the set of all nonnegative integers. Find all the functions $f : \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}$ satisfying the relation

\[f(f(f(n))) = f(n + 1) + 1 \tag{$\ast$}\]

for all $n \in \mathbb{Z}_{\geq 0}$.

Indices : les idées clés

Substitutions : $f^4(n) + 1 = f^4(n + 1)$, donc $f^4(n) = n + c$ ; $f$ est injective et $f(n + c) = f(n) + c$.
Images emboîtées (solution 1) : les ensembles $S_i = R_{i-1} \setminus R_i$ (où $R_i$ est l'image de $f^i$) ont tous le même cardinal $k$, et un comptage donne $3k \leq k + 2$, donc $k = 1$.
Double comptage modulo $c$ (solution 2) : avec $\delta(n) = f(n) - n$ et $S = \sum_{n=0}^{c-1} \delta(n)$, on a $c^2 = 4S$ et $c^2 = 2S + 2c$, donc $c = 4$ ; il reste à fixer $f$ sur $\{0, 1, 2, 3\}$ (congruences).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions).

Solution 1¶

Réponse. Il y a deux solutions : $f(n) = n + 1$ pour tout $n \in \mathbb{Z}_{\geq 0}$, et

\[f(n) = \begin{cases} n + 1, & n \equiv 0 \pmod 4 \text{ ou } n \equiv 2 \pmod 4, \\ n + 5, & n \equiv 1 \pmod 4, \\ n - 3, & n \equiv 3 \pmod 4 \end{cases} \quad \text{pour tout } n \in \mathbb{Z}_{\geq 0}. \tag{1}\]

Dans toutes les solutions, $h^k(x)$ désigne la $k$-ème itérée de la fonction $h$ ; ainsi $h^0$ est l'identité et $h^k(x) = h(\ldots h(x) \ldots)$ ($k$ fois) pour $k \geq 1$.

Pour commencer, $(\ast)$ donne

\[f^4(n) = f(f^3(n)) = f\big(f(n + 1) + 1\big) \quad \text{et} \quad f^4(n + 1) = f^3(f(n + 1)) = f\big(f(n + 1) + 1\big) + 1,\]

donc

\[f^4(n) + 1 = f^4(n + 1). \tag{2}\]

I. Notons $R_i$ l'image de $f^i$ ; on a $R_0 = \mathbb{Z}_{\geq 0}$ puisque $f^0$ est l'identité. Évidemment, $R_0 \supseteq R_1 \supseteq \cdots$. D'après (2), si $a \in R_4$, alors $a + 1 \in R_4$. Donc $\mathbb{Z}_{\geq 0} \setminus R_4$, et a fortiori $\mathbb{Z}_{\geq 0} \setminus R_1$, est fini. En particulier, $R_1$ n'est pas borné.

Supposons $f(m) = f(n)$ pour des $m$ et $n$ distincts. Alors $(\ast)$ donne $f(m + 1) = f(n + 1)$ ; par une récurrence facile, $f(m + c) = f(n + c)$ pour tout $c \geq 0$. La fonction $f(k)$ serait donc périodique, de période $\lvert m - n \rvert$, pour $k \geq m$, et $R_1$ serait borné, ce qui est faux. Donc $f$ est injective.

II. Notons maintenant $S_i = R_{i-1} \setminus R_i$ ; ces ensembles sont finis pour $i \leq 4$. Par injectivité, $n \in S_i \iff f(n) \in S_{i+1}$. Toujours par injectivité, $f$ réalise une bijection entre $S_i$ et $S_{i+1}$, donc $\lvert S_1 \rvert = \lvert S_2 \rvert = \cdots$ ; notons $k$ ce cardinal commun. Si $0 \in R_3$, alors $0 = f(f(f(n)))$ pour un certain $n$, et $(\ast)$ donne $f(n + 1) = -1$, ce qui est impossible. Donc $0 \in R_0 \setminus R_3 = S_1 \cup S_2 \cup S_3$, et $k \geq 1$.

Décrivons ensuite les éléments $b$ de $R_0 \setminus R_3 = S_1 \cup S_2 \cup S_3$. Chacun d'eux vérifie au moins l'une des trois conditions (i) $b = 0$, (ii) $b = f(0) + 1$, (iii) $b - 1 \in S_1$. Sinon, $b - 1 \in \mathbb{Z}_{\geq 0}$ et il existe $n > 0$ tel que $f(n) = b - 1$ ; mais alors $f^3(n - 1) = f(n) + 1 = b$, donc $b \in R_3$.

Cela donne

\[3k = \lvert S_1 \cup S_2 \cup S_3 \rvert \leq 1 + 1 + \lvert S_1 \rvert = k + 2,\]

soit $k \leq 1$. Donc $k = 1$, et l'inégalité ci-dessus est une égalité. Ainsi $S_1 = \{a\}$, $S_2 = \{f(a)\}$ et $S_3 = \{f^2(a)\}$ pour un $a \in \mathbb{Z}_{\geq 0}$, et chacune des trois options (i), (ii), (iii) est réalisée exactement une fois, ce qui signifie que

\[\{a, f(a), f^2(a)\} = \{0, a + 1, f(0) + 1\}. \tag{3}\]

III. D'après (3), $a + 1 \in \{f(a), f^2(a)\}$ (le cas $a + 1 = a$ est impossible). Si $a + 1 = f^2(a)$, alors $f(a + 1) = f^3(a) = f(a + 1) + 1$, ce qui est absurde. Donc

\[f(a) = a + 1. \tag{4}\]

Ensuite, toujours d'après (3), $0 \in \{a, f^2(a)\}$. Considérons ces deux cas séparément.

Cas 1 : $a = 0$. Alors $f(0) = f(a) = a + 1 = 1$. De plus, (3) donne $f(1) = f^2(a) = f(0) + 1 = 2$. Montrons que $f(n) = n + 1$ par récurrence sur $n$ ; les cas $n \leq 1$ sont établis. Si $n \geq 2$, l'hypothèse de récurrence donne

\[n + 1 = f(n - 1) + 1 = f^3(n - 2) = f^2(n - 1) = f(n),\]

ce qui établit l'hérédité. On obtient la première des deux réponses ; on vérifie directement qu'elle satisfait $(\ast)$.

Cas 2 : $f^2(a) = 0$. Alors (3) donne $a = f(0) + 1$. Par (4), $f(a + 1) = f^2(a) = 0$, puis $f(0) = f^3(a) = f(a + 1) + 1 = 1$, donc $a = f(0) + 1 = 2$ et $f(2) = 3$ par (4). En résumé,

\[f(0) = 1, \qquad f(2) = 3, \qquad f(3) = 0.\]

Montrons par récurrence sur $m$ que (1) est vraie pour tous les $n = 4k, 4k + 2, 4k + 3$ avec $k \leq m$, et pour tous les $n = 4k + 1$ avec $k < m$. Le cas $m = 0$ est établi ci-dessus. Pour l'hérédité, supposons $m \geq 1$. Par $(\ast)$, $f^3(4m - 3) = f(4m - 2) + 1 = 4m$. Ensuite, par (2),

\[f(4m) = f^4(4m - 3) = f^4(4m - 4) + 1 = f^3(4m - 3) + 1 = 4m + 1.\]

Puis, avec l'hypothèse de récurrence et $(\ast)$, on obtient successivement

\[\begin{aligned} f(4m - 3) &= f^3(4m - 1) = f(4m) + 1 = 4m + 2, \\ f(4m + 2) &= f^3(4m - 4) = f(4m - 3) + 1 = 4m + 3, \\ f(4m + 3) &= f^3(4m - 3) = f(4m - 2) + 1 = 4m, \end{aligned}\]

ce qui achève l'hérédité.

Enfin, on vérifie directement que la fonction construite convient :

\[f^3(4k) = 4k + 7 = f(4k + 1) + 1, \qquad f^3(4k + 1) = 4k + 4 = f(4k + 2) + 1,\]

\[f^3(4k + 2) = 4k + 1 = f(4k + 3) + 1, \qquad f^3(4k + 3) = 4k + 6 = f(4k + 4) + 1. \qquad \blacksquare\]

Solution 2¶

I. Introduisons la fonction $g(n) = f(n) + 1$. En substituant $f(n)$ à $n$ dans $(\ast)$, on obtient

\[f^4(n) = f\big(f(n) + 1\big) + 1, \quad \text{soit} \quad f^4(n) = g^2(n). \tag{5}\]

En appliquant $f$ aux deux membres de $(\ast)$ et en utilisant (5),

\[f^4(n) + 1 = f\big(f(n + 1) + 1\big) + 1 = f^4(n + 1). \tag{6}\]

Donc, si $g^2(0) = f^4(0) = c$, une récurrence facile sur $n$ montre que

\[g^2(n) = f^4(n) = n + c, \qquad n \in \mathbb{Z}_{\geq 0}. \tag{7}\]

Cette relation montre que $f$ et $g$ sont injectives : si par exemple $f(m) = f(n)$, alors $m + c = f^4(m) = f^4(n) = n + c$. Ensuite, comme $g(n) \geq 1$ pour tout $n$, on a $c = g^2(0) \geq 1$. Donc, par (7) à nouveau, $f(n) \neq n$ et $g(n) \neq n$ pour tout $n \in \mathbb{Z}_{\geq 0}$.

II. En appliquant $f$ et $g$ à (7), on obtient

\[f(n + c) = f^5(n) = f^4(f(n)) = f(n) + c \quad \text{et} \quad g(n + c) = g^3(n) = g(n) + c. \tag{8}\]

En particulier, si $m \equiv n \pmod c$, alors $f(m) \equiv f(n) \pmod c$. Réciproquement, si $f(m) \equiv f(n) \pmod c$, alors $m + c = f^4(m) \equiv f^4(n) = n + c \pmod c$. Ainsi

\[m \equiv n \pmod c \iff f(m) \equiv f(n) \pmod c \iff g(m) \equiv g(n) \pmod c. \tag{9}\]

Introduisons la fonction $\delta(n) = f(n) - n = g(n) - n - 1$, et posons

\[S = \sum_{n=0}^{c-1} \delta(n).\]

Par (8), pour tout système complet de résidus $n_1, \ldots, n_c$ modulo $c$, on a aussi $S = \sum_{i=1}^{c} \delta(n_i)$. Par (9), $\{f^k(n) : n = 0, \ldots, c - 1\}$ et $\{g^k(n) : n = 0, \ldots, c - 1\}$ sont des systèmes complets de résidus modulo $c$ pour tout $k$. On a donc, par double comptage,

\[c^2 = \sum_{n=0}^{c-1} \big(f^4(n) - n\big) = \sum_{k=0}^{3} \sum_{n=0}^{c-1} \big(f^{k+1}(n) - f^k(n)\big) = \sum_{k=0}^{3} \sum_{n=0}^{c-1} \delta(f^k(n)) = 4S\]

et de même

\[c^2 = \sum_{n=0}^{c-1} \big(g^2(n) - n\big) = \sum_{k=0}^{1} \sum_{n=0}^{c-1} \big(g^{k+1}(n) - g^k(n)\big) = \sum_{k=0}^{1} \sum_{n=0}^{c-1} \big(\delta(g^k(n)) + 1\big) = 2S + 2c.\]

Donc $c^2 = 4S = 2 \cdot 2S = 2(c^2 - 2c)$, soit $c^2 = 4c$. Comme $c \neq 0$, on obtient $c = 4$. D'après (8), il suffit donc de déterminer les valeurs de $f$ en $0, 1, 2, 3$.

III. Posons $d = g(0) \geq 1$. Alors $g(d) = g^2(0) = 0 + c = 4$. Si $d \geq 4$, on aurait $g(d - 4) = g(d) - 4 = 0$, ce qui est impossible. Donc $d \in \{1, 2, 3\}$. Si $d = 1$, alors $f(0) = g(0) - 1 = 0$, ce qui est impossible puisque $f(n) \neq n$ pour tout $n$. Si $d = 3$, alors $g(3) = g^2(0) = 4$, donc $f(3) = 3$, ce qui est aussi impossible. Donc $g(0) = 2$, et $g(2) = g^2(0) = 4$.

Ensuite, si $g(1) = 1 + 4k$ pour un entier $k$, alors $5 = g^2(1) = g(1 + 4k) = g(1) + 4k = 1 + 8k$, ce qui est impossible. Comme $\{g(n) : n = 0, 1, 2, 3\}$ est un système complet de résidus modulo $4$, on obtient $g(1) = 3 + 4k$, donc $g(3) = g^2(1) - 4k = 5 - 4k$, d'où $k = 0$ ou $k = 1$. On obtient donc soit

\[f(0) = 1, \; f(1) = 2, \; f(2) = 3, \; f(3) = 4, \qquad \text{soit} \qquad f(0) = 1, \; f(1) = 6, \; f(2) = 3, \; f(3) = 0,\]

ce qui donne les deux fonctions de la réponse.

Enfin, on vérifie que ces deux fonctions conviennent, comme dans la solution 1 ; grâce à (8), il suffit de le vérifier pour $n = 0, 1, 2, 3$. $\blacksquare$