Dans tout le problème, {n} désigne un entier naturel non nul. On note {E_n=\{1,2,\ldots,n\}} l’ensemble des {n} premiers entiers naturels non nuls. Dans certaines questions, on sera peut-être amené à donner une valeur particulière à {n}.
On note {\mathcal F_n} l’ensemble de toutes les applications de {E_n} dans lui-même. Pour désigner un élément {f} de {\mathcal F_n}, on utilisera le tableau : {\begin{pmatrix}1&2&\cdots&n-1&n\\[4pt]f(1)&f(2)&\cdots&f(n-1)&f(n)\end{pmatrix}}Par exemple, {\begin{pmatrix}1&2&3&4&5\\[4pt]3&3&1&3&5\end{pmatrix}} désigne l’application de {E_5} dans lui-même définie par {f(1)=3}, {f(2)=3}, {f(3)=1}, {f(4)=3} et {f(5)=5}.
Pour tout {f\in \mathcal F_n}, on définit les puissances itérées par : {f^0=\operatorname{Id},\quad f^{k+1}=f\circ f^k\quad(k\in\mathbb N)}Ainsi {f^1=f}, {f^2=f\circ f}, {f^3=f\circ f\circ f}, etc. Il est clair qu’avec cette définition : {f^m\circ f^p=f^p\circ f^m=f^{m+p}\quad(m,p\in\mathbb N)}
Première partie : étude de trois exemples
Dans cette partie, et dans cette partie seulement, on fixe {n=10}. On définit les trois applications suivantes :
2. Calculer (directement sous la forme de tableaux {2\times10}, et sans justifications intermédiaires) les applications {f^k}, avec {2\leq k\leq8}. On constatera notamment que {f^8=f^2}.
3. Montrer que {f^{k+6}=f^k} pour tout entier {k\geq2} (autrement dit la suite des puissances itérées de {f} est périodique de période {6} à partir de {f^2}) et que l’ensemble {\{f^k:k\in\mathbb N\}} se réduit aux huit applications, toutes distinctes, {\{\operatorname{Id},f,f^2,f^3,f^4,f^5,f^6,f^7\}}.
On exprimera cette situation en disant que {f} est de délai {2} et de période {6}.
On va généraliser les observations tirées des trois exemples précédents. Dans cette partie, {n} est fixé dans {\mathbb N^*}, et {f} est un élément donné de {\mathcal F_n}.
1. Préciser le nombre d’éléments de {\mathcal F_n}, c’est-à-dire d’applications de {E_n} dans lui-même.
2. (b) En déduire qu’il existe un plus petit entier {d\geq0} et, pour ce {d}, un plus petit entier {p\geq1} tels que {f^{d+p}=f^d}, et que la suite {(f^k)_{k\geq0}} est périodique de période {p} à partir de {k=d}.
On exprime cette situation en disant que {f} est de délai {d} et de période {p}.
2. (c) Montrer que les applications {\operatorname{Id},f,\ldots,f^d,f^{d+1},\ldots,f^{d+p-1}}, c’est-à-dire les {d+p} premières puissances de {f}, sont distinctes deux à deux.
2. (d) Montrer finalement que l’ensemble {\{f^k:k\in\mathbb N\}} de toutes les puissances de {f} se réduit à l’ensemble {\{\operatorname{Id},f,\ldots,f^{d+p-1}\}} de ses {d+p} premières puissances.
Pour tout entier naturel {k}, on note {\operatorname{Im}(f^k)=f^k(E_n)=\{f^k(x):x\in E_n\}}. Cet ensemble est formé des images des éléments de {E_n} par {f^k}. Du fait que {f^0=\operatorname{Id}}, on a {\operatorname{Im}(f^0)=E_n}.
4. (a) Étudier la suite des {\operatorname{Im}(f^k)} quand, uniquement dans cette question, {n=10} et {f} est l’une des trois applications étudiées dans la première partie.
On se contentera ici d’observations, en remarquant que dans chaque cas les ensembles {\operatorname{Im}(f^k)} sont « emboîtés » avant de se stabiliser. On notera en particulier que l’indice {k} à partir duquel cette suite est constante est à chaque fois le délai de {f}.
4. (b) Montrer que pour tous entiers naturels {j,k}, on a {j\leq k\Rightarrow\operatorname{Im}(f^j)\supset\operatorname{Im}(f^k)}. Ce résultat signifie que la suite des images est décroissante pour l’inclusion.
4. (c) Soit {k\geq d}. Montrer que {\operatorname{Im}(f^d)=\operatorname{Im}(f^k)}. Indication : utiliser la question précédente et une égalité {f^{d+qp}=f^d}, où {q} est convenablement choisi.
Ce résultat signifie que la suite des images est stationnaire à partir, au plus tard, du rang {d}, délai de {f}.
Dans cette question, on suppose {d\geq1}, donc {f} non bijective. Depuis 4. (b), on connaît les inclusions : {E_n=\operatorname{Im}(f^0)\supset\operatorname{Im}(f)\supset\cdots\supset\operatorname{Im}(f^d)}On veut prouver qu’elles sont toutes strictes. On raisonne par l’absurde en supposant qu’il existe {k\in\{0,\ldots,d-1\}} tel que {\operatorname{Im}(f^k)=\operatorname{Im}(f^{k+1})}.
On désigne par {\varphi} la restriction de {f} à {\operatorname{Im}(f^k)}.
5. (a) Montrer que {\varphi} est une application de {\operatorname{Im}(f^k)} dans lui-même et que {\varphi\circ f^k=f^{k+1}}.
5. (d) Par un argument analogue à ceux de 3., montrer qu’il existe {m\in\mathbb N^*} tel que {\varphi^m=\operatorname{Id}}. En déduire {f^{k+m}=f^k}, puis une contradiction.