La Suite de Conway
Introduction
La suite de Conway, aussi appelée look-and-say, est une suite de nombres qui paraît ludique mais cache en réalité une grande richesse mathématique. On part d’un simple chiffre « 1 », et à chaque étape, on lit la suite précédente en décrivant ses blocs de chiffres identiques. Très vite, les termes deviennent longs, étranges, et pourtant obéissent à des règles précises.
Problématique : quelles sont les régularités cachées derrière cette suite apparemment chaotique, et comment peut-on les démontrer ?
I. Définition et premiers invariants
1. Construction de la suite de Conway (look-and-say)
On définit une suite de mots [math]u_n[/math] comme suit :
- Graine : [math]u_0 = 1[/math].
- Règle de passage : pour obtenir [math]u_{n+1}[/math] à partir de [math]u_n[/math], on décrit [math]u_n[/math] en lisant les chiffres par blocs consécutifs identiques.
Exemple :
- [math]u_0 = 1[/math] → « un 1 » → [math]u_1 = 11[/math].
- [math]u_1 = 11[/math] → « deux 1 » → [math]u_2 = 21[/math].
- [math]u_2 = 21[/math] → « un 2, un 1 » → [math]u_3 = 1211[/math].
- [math]u_3 = 1211[/math] → « un 1, un 2, deux 1 » → [math]u_4 = 111221[/math].
- [math]u_4 = 111221[/math] → « trois 1, deux 2, un 1 » → [math]u_5 = 312211[/math].
On obtient donc la suite :
1 \to 11 \to 21 \to 1211 \to 111221 \to 312211 \to 13112221 \to 1113213211 \to \dots
2. Invariants de base à prouver
a. Pas de “xxxx” (quatre chiffres identiques de suite).
Si [math]u_n[/math] contenait « xxxx », alors dans [math]u_{n+1}[/math] on devrait écrire « quatre x ».
Mais cela impliquerait deux blocs consécutifs décrivant le même chiffre, ce qui est impossible : sinon ils auraient fusionné en un seul bloc dans [math]u_n[/math].
Donc «xxxx» n’apparaît jamais.
b. Conséquence : pas de chiffre [math]\ge 4[/math].
Puisqu’on ne peut pas avoir 4 fois le même chiffre, les comptes restent toujours [math]1,2[/math] ou [math]3[/math]. Avec la graine [math]u_0=1[/math], on en déduit que l’alphabet de toute la suite est réduit à [math]{1,2,3}[/math].
c. Parité des longueurs.
Si [math]L_n = |u_n|[/math], alors [math]L_0=1[/math] est impair, et pour tout [math]n\ge 1[/math], [math]L_n[/math] est pair (car [math]u_{n+1}[/math] est toujours construit en paires «compte, chiffre»).
II. Motifs remarquables
1. Les terminaisons alternent : [math]\ldots 221[/math] puis [math]\ldots 211[/math]
Énoncé. Pour tout [math]k\ge 2[/math] (on vérifie sur les premiers termes),
- [math]u_{2k}[/math] se termine par [math]\ldots 221[/math],
- [math]u_{2k+1}[/math] se termine par [math]\ldots 211[/math].
Vérification sur les premiers mots.
u_4=111221\ (\text{finit par }221),\quad u_5=312211\ (\text{finit par }211),\quad u_6=13112221\ (\text{finit par }221).Preuve (récurrence locale sur la « queue »).
- Si [math]u_n[/math] se termine par [math]\ldots 221[/math], cela signifie que ses deux derniers blocs sont «[math]x2[/math]» (x 2) puis « [math]11[/math] » (un 1). Donc [math]u_{n+1}[/math] se termine par [math]\ldots 211[/math].
- Si au contraire [math]u_n[/math] se termine par [math]\ldots 211[/math], ses deux derniers blocs sont « [math]x2[/math] » (x 2) puis « [math]11[/math] » (deux 1). Donc [math]u_{n+1}[/math] se termine par [math]\ldots x221[/math], dont les trois derniers chiffres sont [math]221[/math].
2. Motifs de début : un cycle [math]1113 \to 3113 \to 1321[/math] (dès [math]u_7[/math])
Observation de départ.
À partir de [math]u_7[/math], on constate :
u_7=\underline{1113},213211,\quad
u_8=\underline{3113},1211131221,\quad
u_9=\underline{1321},1311123113112211.On voit donc les préfixes successifs : [math]1113,\ 3113,\ 1321[/math]. On va montrer que ce cycle se propage : si [math]u_n[/math] commence par l’un d’eux, alors [math]u_{n+1}[/math] commence par le suivant du cycle.
Règle locale (rappel). Pour chaque bloc « [math]x^k[/math] » (le chiffre [math]x\in{1,2,3}[/math] répété [math]k\in{1,2,3}[/math] fois), la contribution dans [math]u_{n+1}[/math] est [math]kx[/math]. On concatène ces sorties bloc par bloc.
Étape 1 : [math]\boxed{1113 \ \Rightarrow\ 3113}[/math]
Supposons que [math]u_n[/math] commence par [math]\underline{1113},\cdots[/math].
Alors ses premiers blocs sont :
- [math]111[/math] (trois « 1 ») → donne [math]31[/math],
- puis [math]3[/math] (un « 3 ») → donne [math]x3[/math]. En réalité, il n’y a pas d’autres 3 derrière car sinon on aurait non pas 1113 mais 1123 ou 1133 par exemple (par fusion). En concaténant, le début de [math]u_{n+1}[/math] est [math]31,13 = \underline{3113},\cdots[/math]. Donc [math]1113 \mapsto 3113[/math] en tête.
Étape 2 : [math]\boxed{3113 \ \Rightarrow\ 1321}[/math]
Supposons maintenant que [math]u_n[/math] commence par [math]\underline{3113},\cdots[/math]. Les premiers blocs sont :
- [math]3[/math] (un « 3 ») → [math]13[/math],
- [math]11[/math] (deux « 1 ») → [math]21[/math],
- [math]3[/math] (un « 3 ») → [math]13[/math] (cf. argument précédent). Ainsi, le début de [math]u_{n+1}[/math] est [math]13,21,13 = \underline{1321}13\cdots[/math]. Donc [math]3113 \mapsto 1321[/math] en tête.
Étape 3 : [math]\boxed{1321 \ \Rightarrow\ 1113}[/math]
Supposons que [math]u_n[/math] commence par [math]\underline{1321},\cdots[/math]. Les premiers blocs sont quatre singletons :
- [math]1 \to 11,\quad 3 \to 13,\quad 2 \to 12,\quad 1 \to 11.[/math] Donc le début de [math]u_{n+1}[/math] est [math]11,13,12,11 = \underline{1113},1211\cdots[/math]. Donc [math]1321 \mapsto 1113[/math] en tête.
Conclusion : un cycle de préfixes à partir de [math]u_7[/math]
On a montré les trois implications locales sur les premiers blocs :
1113 \ \Rightarrow\ 3113 \ \Rightarrow\ 1321 \ \Rightarrow\ 1113 \ \Rightarrow\ \cdots
III. Longueurs et croissance globale
1. Croissance de la longueur [math]L_n[/math]
On note [math]L_n[/math] la longueur (nombre de chiffres) du terme [math]u_n[/math].
- Observation expérimentale : [math]L_0=1, L_1=2, L_2=2, L_3=4, L_4=6, L_5=6, L_6=8, L_7=10 \ldots[/math]. On voit que, dès [math]u_5[/math], la suite des longueurs devient strictement croissante.
- Idée de démonstration :
Chaque terme [math]u_n[/math] est composé de blocs (singletons, doublets, triplets).- Un doublet engendre souvent un doublet → effet neutre sur la croissance.
- Un triplet se transforme en un bloc « 3x » suivi d’un singleton (ex. « 111 » → « 31 ») → il diminue de 1 la longueur.
- Un singleton au contraire se transforme en plus de blocs : il augmente de 1 la longueur.
Or, on peut montrer qu’il y a toujours plus de singletons que de triplets, et que chaque triplet est compensé par au moins un singleton supplémentaire (démonstration non triviale, mais qu’on peut montrer avec le programme de Terminale je pense).
Conclusion : à partir de [math]n\ge 5[/math], on a forcément un gain net de blocs d’une étape à l’autre. Donc [math]L_{n+1} > L_n[/math].
2. Curiosités et résultats plus poussés (sans preuve)
- Constante de Conway :
On peut démontrer (Conway, années 80) que le rapport [math]\tfrac{L_{n+1}}{L_n}[/math] tend vers une constante limite
[math]\lambda \approx 1,303577\ldots[/math], appelée constante de Conway. Elle est racine d’un polynôme de degré 71 (résultat très avancé, bien au-delà du niveau Terminale). - Théorème cosmologique de Conway :
À long terme, toute suite de type « look-and-say » (en base 10) se décompose en motifs élémentaires en nombre fini : 94 motifs distincts. Conway les a surnommés les « éléments » de la suite, en clin d’œil au tableau périodique des éléments chimiques. Chaque motif joue le rôle d’un « composant atomique », et un terme de la suite est comme une molécule formée de ces éléments.
C’est une belle illustration de la rencontre entre arithmétique, combinatoire, et même une sorte d’«analogie cosmologique» inventée par Conway.
Conclusion
La suite de Conway illustre parfaitement comment une règle très simple peut engendrer des structures complexes mais organisées. Derrière l’apparente «explosion» des termes, on découvre des invariants (pas de chiffres supérieurs à 3), des motifs réguliers (fins en 221 ou 211), et une croissance stricte des longueurs.
On espère que ce sujet vous aidera, et que vous saurez l’exploiter au mieux pour briller à votre épreuve !
