Au cours d’un stage Hippocampe [1]
organisé par l’IREM d’Aix-Marseille, mes élèves
de spécialité maths de TS ont eu le privilège de travailler sous la direction de Pierre
Arnoux sur les fractals. Un des sujets de recherche a été le codage de la courbe du
dragon.

Les professeurs des élèves en stage ne sont pas censés participer au travail, mais
comment résister à chercher soi-même lorsqu’on se trouve devant un problème
intéressant ? Un des groupes a programmé à l’aide du logiciel SAGE le dessin de la
courbe. Sous mes yeux admiratifs, ils ont rapidement pu utiliser ce bel outil dont ils
ignoraient tout en arrivant et, avec l’appui de Vincent Delecroix, qui fut un mentor
remarquablement efficace, ils ont réalisé des dessins que l’on pourra admirer sur le site de l’IREM d’Aix-Marseille à l’adresse suivante :

http://sage.irem.univ-mrs.fr/hippocampe/fractals_23_01_2010.html

Quant à moi, la question qui m’a surtout passionnée est le codage de cette courbe sous forme d’une suite de mots.

La courbe du dragon est la courbe engendrée par la modélisation du pliage d’une bande de papier. Bruno Alaplantive a réalisé cette photo, qui remplace bien des discours :

On plie en 2, puis en 4, puis en 8, etc., et toujours dans le même sens une bande de
papier et l’on examine de profil la suite des plis obtenus, en les disposant tous à angle
droit. Voici les premières étapes de la courbe obtenue :

On s’intéressera ici à la forme de la courbe et non aux longueurs des segments qu’on prendra toutes identiques. On appelle ${C_n}$ la courbe obtenue après avoir plié n fois :
on a dessiné ici $C_1$, $C_2$ et $C_3$. Comment prévoir la suite et comment la coder ?

Une façon de la représenter est de la considérer comme une suite de vecteurs de
translations que l’on peut nommer par les points cardinaux : E, S, O, N pour Est,
Sud, Ouest, et Nord. Les termes de la suite apparaissent alors comme une suite de
mots $M_n$
, de longueur $2^n$
, écrits à l’aide des lettres E, S, O, N.

En reprenant les dessins ci-dessus, les quatre premiers sont : $M_0$
=E ; $M_1$
=ES ;
$M_2$
=ESOS ; $M_3$
= ESOSONOS

Pour trouver la suite, une solution s’obtient en réfléchissant au processus de
construction : on constate que chaque mot de la suite commence par le mot précédent.
C’est bien une propriété générale : quand on plie n fois, on plie d’abord une fois en
deux, puis on plie (n−1) fois. Lorsqu’on déplie, on déplie d’abord (n−1) fois, et
on obtient la courbe $C_{n-1}$
en double épaisseur de papier, puis le dernier « dépliage »
donne une duplication de cette courbe : une épaisseur de papier reproduit $C_{n-1}$
, l’autre
réalise une rotation de $\pi/2$ de cette courbe $C_{n-1}$
autour de son dernier point.

La première moitié du mot $M_{n-+1}$ est donc le mot $M_ n$
. La deuxième moitié demande
un peu de soin : il faut d’une part inverser l’ordre des lettres, (le début de la courbe
$C_{n-1}$ après rotation devient la fin de la courbe $C_{n}$
), et faire tourner nos points cardinaux
de $-\pi/2$ (il faut changer de sens les vecteurs après la rotation de $\pi/2$, pour continuer
à « avancer » sur la courbe.)

Nous appellerons s la substitution définie par : $\begin{Bmatrix} E\rightarrow S \\ N \rightarrow E \\ O \rightarrow N\\ S \rightarrow O \end{matrix}$ , et nous appellerons r la
fonction qui inverse l’ordre des lettres d’un mot.
En notant « . » l’opération de concaténation entre deux mots, on obtient :

$M_{n+1}=M_n . r . s (M_n)$

Écrire $M_4$ est alors un jeu d’enfant :

$ESOSONOS^{\ \underrightarrow{s}}\ SONONENO ^{\ \underrightarrow{r}}\ ONENONOS.$

Il ne reste plus qu’à réécrire $M_3$ devant ce résultat pour trouver $M_4$ qui s’écrit donc :

$M_4\ =\ ESOSONOSONENONOS.$

ce qui permet de dessiner $C_4$ :

Les élèves ont trouvé cette méthode de construction. Mais ils n’ont pas trouvé un
deuxième procédé que leur a indiqué Pierre Arnoux : on obtient la même suite de mots
en remplaçant simplement dans $M_n$
E par ES, S par OS, O par ON et N par EN !

Vérifions-le sur les premiers termes de la suite en partant de E : E donne ES, qui
donne ESOS, qui donne ESOSONOS, qui donne ESOSONOSONENONOS. Ce sont
bien les mots trouvés plus haut.

Mais comment prouver que les deux procédés construisent la même suite ? C’est ce
problème-là que j’ai cherché, et j’ai été ravie de trouver !

Appelons σ la substitution définie par $\begin{Bmatrix} E\rightarrow ES \\ S \rightarrow OS \\ O \rightarrow ON\\ N \rightarrow EN \end{matrix}$ .

Remarquons d’abord que les fonctions r, s et σ ont vis-à-vis de l’opération de
concaténation (concaténer les mots A et B, c’est simplement écrire B à la suite de A)
les propriétés suivantes :

Étant donnés deux mots A et B,

$ r (A\ .\ B)= r (B)\ .\ r (A) $$ s (A\ .\ B)= s (B)\ .\ s (A) $$ \sigma (A\ .\ B)= \sigma (B)\ .\ \sigma (A) $

Prouvons alors par récurrence que les deux procédés construisent la même suite de mots $(M_n)$ .

On l’a déjà vérifié pour les premiers termes, il reste à prouver que si les deux suites
sont identiques jusqu’à n, les deux procédés construisent le même mot $(M_{n+1})$ .

On suppose donc que $M_n = M_{n-1} .\ r \circ s ( M_{n-1})$

La fonction σ transforme alors $M_n$
en : $\sigma ( M_n )= \sigma ( M_{n-1}\ .\ r \circ s ( M_{n-1}))$ , par
hypothèse de récurrence. C’est aussi, par la propriété vue plus haut :

$\sigma ( M_n )= \sigma ( M_{n-1} )\ .\ \sigma (r \circ s ( M_{n-1}))$

Mais, par hypothèse, $\sigma ( M_{n-1}) = M_n$ Donc :

$\sigma ( M_n )= M_n \ .\ \sigma \circ r \circ s (M_{n-1})$

Alors que le premier procédé de fabrication transforme $M_n$
en :

$M_n \ .\ r \circ s ( M_n) = M_n \ .\ r \circ s (\sigma ( M_{n-1}))=M_n \ .\ r \circ s \circ \sigma ( M_{n-1}).$

On constate qu’il suffit alors, pour conclure, de prouver l’égalité : $\sigma \circ r \circ s=r \circ s \circ \sigma.$

Qu’en est-il pour les quatre lettres de départ ?

$O^{\ \underrightarrow{s}}\ N ^{\ \underrightarrow{r}}\ N^{\ \underrightarrow{\sigma}}\ EN \qquad et \qquad O^{\ \underrightarrow{\sigma}}\ ON ^{\ \underrightarrow{s}}\ NE^{\ \underrightarrow{r}}\ EN,$$N^{\ \underrightarrow{s}}\ E ^{\ \underrightarrow{r}}\ E^{\ \underrightarrow{\sigma}}\ ES \qquad et \qquad N^{\ \underrightarrow{\sigma}}\ EN ^{\ \underrightarrow{s}}\ SE^{\ \underrightarrow{r}}\ ES,$$E^{\ \underrightarrow{s}}\ S ^{\ \underrightarrow{r}}\ S^{\ \underrightarrow{\sigma}}\ OS \qquad et \qquad E^{\ \underrightarrow{\sigma}}\ ES ^{\ \underrightarrow{s}}\ SO^{\ \underrightarrow{r}}\ OS,$$S^{\ \underrightarrow{s}}\ O ^{\ \underrightarrow{r}}\ O^{\ \underrightarrow{\sigma}}\ ON \qquad et \qquad S^{\ \underrightarrow{\sigma}}\ OS ^{\ \underrightarrow{s}}\ NO^{\ \underrightarrow{r}}\ ON,$

Les images par les deux fonctions des quatre lettres de base sont bien identiques.

Il reste à prouver alors que si les fonctions donnent les mêmes images de deux mots
A et B, elles donnent aussi les mêmes images de leur concaténation $A\ .\ B$ : tout mot
étant construit par concaténations successives à partir des quatre lettres, cela prouvera
bien l’égalité des deux fonctions sur l’ensemble des mots.

Supposons donc acquis que :

$\sigma \circ r \circ s (A)=r \circ s \circ \sigma (A) \qquad et \qquad \sigma \circ r \circ s (B)=r \circ s \circ \sigma (B) $

Alors, en utilisant les propriétés vues plus haut de nos fonctions r, s et σ, on obtient :

$\begin{array}{lcl} \sigma \circ r \circ s (A \ .\ B) & = & \sigma \circ r ( s (A) \ . \ s(B)) \\ & = & \sigma(r \circ s (B) \ . \ r \circ s(A))\\ & = & \sigma \circ r \circ s (B) \ . \ \sigma \circ r \circ s(A))\\ & = & r \circ s \circ \sigma (B) \ .\ r \circ s \circ \sigma (A) \qquad (par \ hypothèse)\\ & = & r(s \circ \sigma (A) \ . \ s \circ \sigma (B)) \\ & = & r \circ s (\sigma(A) \ . \ \sigma (B))\\ & = & r \circ s \circ \sigma (A \ . \ B). \end{array}$

Ainsi, on a bien prouvé l’égalité $\sigma \circ r \circ s = r \circ s \circ \sigma $, et on a fini de démontrer que les
deux procédés construisent bien le même mot $M_{ n+1}$ à partir du mot $M_n$.

Ce que je trouve intéressant dans cette histoire, c’est qu’au départ, la solution du
problème me paraissait tout à fait hors de portée, et offrait peu de piste usuelle. Mais
un peu d’analyse de la situation, et la manipulation de composée de fonctions permet
finalement de le résoudre assez facilement !

Les stages Hippocampe peuvent être passionnants aussi pour les professeurs !

<redacteur|auteur=511>