Shortlist 2017, A3

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

Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe des tiroirs

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

Énoncé

Let \(S\) be a finite set, and let \(\mathcal{A}\) be the set of all functions from \(S\) to \(S\). Let \(f\) be an element of \(\mathcal{A}\), and let \(T = f(S)\) be the image of \(S\) under \(f\). Suppose that \(f \circ g \circ f \neq g \circ f \circ g\) for every \(g\) in \(\mathcal{A}\) with \(g \neq f\). Show that \(f(T) = T\).

Indices : les idées clés

• Choisir \(g\) parmi les itérées de \(f\) : avec \(g = f^n\), l'égalité \(f \circ g \circ f = g \circ f \circ g\) devient \(f^{n+2} = f^{2n+1}\), et l'hypothèse force alors \(f^n = f\).
• Suite décroissante d'ensembles finis : les images \(f^m(S)\) décroissent et se stabilisent sur un ensemble \(S_\infty\) sur lequel \(f\) est une permutation.
• Une permutation d'un ensemble fini a une puissance égale à l'identité : \(f^r = \mathrm{id}\) sur \(S_\infty\) (par exemple \(r = |S_\infty|!\)), d'où la périodicité des itérées \(f^m\) pour \(m\) grand.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2017 (une solution).

Solution

Pour \(n \geq 1\), notons \(f^n = f \circ f \circ \cdots \circ f\) (\(n\) fois) la \(n\)-ième itérée de \(f\). Par hypothèse, si \(g \in \mathcal A\) vérifie \(f \circ g \circ f = g \circ f \circ g\), alors \(g = f\). L'idée naturelle est de prendre \(g = f^n\) pour un certain \(n\), afin d'obtenir \(f^n = f\), ce qui résout le problème :

Affirmation. S'il existe \(n \geq 3\) tel que \(f^{n+2} = f^{2n+1}\), alors la restriction \(f : T \to T\) de \(f\) à \(T\) est une bijection.

Preuve. Par hypothèse,

\[f^{n+2} = f^{2n+1} \iff f \circ f^n \circ f = f^n \circ f \circ f^n \implies f^n = f.\]

Comme \(n - 2 \geq 1\), l'image de \(f^{n-2}\) est contenue dans \(T = f(S)\), donc \(f^{n-2}\) se restreint en une fonction \(f^{n-2} : T \to T\). C'est l'inverse de \(f : T \to T\). En effet, pour \(t \in T\), disons \(t = f(s)\) avec \(s \in S\), on a

\[t = f(s) = f^n(s) = f^{n-2}\big(f(t)\big) = f\big(f^{n-2}(t)\big), \quad \text{c'est-à-dire} \quad f^{n-2} \circ f = f \circ f^{n-2} = \mathrm{id} \text{ sur } T.\]

Ainsi la restriction \(f : T \to T\) est bijective, d'inverse \(f^{n-2} : T \to T\). En particulier \(f(T) = T\). \(\square\)

Il reste à montrer qu'un tel \(n\) existe. Posons \(S_m = f^m(S)\) (l'image de \(f^m\)). Clairement l'image de \(f^{m+1}\) est contenue dans celle de \(f^m\) : on a une suite décroissante de parties de \(S\)

\[S \supseteq S_1 \supseteq S_2 \supseteq S_3 \supseteq S_4 \supseteq \cdots,\]

qui doit se stabiliser puisque \(S\) est fini : il existe \(k \geq 1\) tel que

\[S_k = S_{k+1} = S_{k+2} = S_{k+3} = \cdots =: S_\infty.\]

Donc \(f\) se restreint en une fonction surjective \(f : S_\infty \to S_\infty\), qui est aussi bijective puisque \(S_\infty \subseteq S\) est fini. Ainsi \(f : S_\infty \to S_\infty\) est une permutation de l'ensemble fini \(S_\infty\) ; il existe donc un entier \(r \geq 1\) tel que \(f^r = \mathrm{id}\) sur \(S_\infty\) (on peut prendre par exemple \(r = |S_\infty|!\)). Autrement dit (puisque \(f^m(s) \in S_\infty\) pour \(m \geq k\)),

\[f^{m+r} = f^m \text{ sur } S \quad \text{pour tout } m \geq k. \tag{*}\]

Clairement, \((*)\) entraîne aussi \(f^{m + tr} = f^m\) pour tous entiers \(t \geq 1\) et \(m \geq k\). Pour trouver \(n\) comme dans l'affirmation, il suffit donc de choisir \(m\) et \(t\) de sorte qu'il existe \(n \geq 3\) avec

\[\begin{cases} 2n + 1 = m + tr \\ n + 2 = m \end{cases} \iff \begin{cases} m = 3 + tr \\ n = m - 2. \end{cases}\]

On peut le faire en choisissant \(m\) assez grand avec \(m \equiv 3 \pmod r\). Par exemple, on peut prendre \(n = 2kr + 1\), de sorte que

\[f^{n+2} = f^{2kr+3} = f^{4kr+3} = f^{2n+1},\]

l'égalité du milieu découlant de \((*)\) puisque \(2kr + 3 \geq k\). \(\blacksquare\)