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])