Deux (deux?) minutes pour la suite de Conway
C'est un sujet que j'ai déjà abordé au moins deux fois sur le blog, mais j'adore cette suite ! Voici donc la suite de Conway, en vidéo !
Transcription augmentée :
En 1992, Bernard Werber publie "le jour des fourmis", deuxième épisode de sa célèbre trilogie des fourmis. Dans ce roman, il met en scène l’énigme suivante : complétez la suite 1, 11, 21, 1211…
En fait, cette suite a été inventée et étudiée 10 ans plus tôt par le génial John Conway et regorge de surprises mathématiques insoupçonnées.
Ça tombe bien, j’ai deux minutes pour en parler.
Donnons tout de même la clé de l’énigme : comment est-on sensé compléter la suite 1, 11, 21, 1211 ? Eh bien, dans cette suite, chaque terme s’obtient en regardant puis en lisant à voix haute le terme précédent, en débutant par le terme 1. En regardant ce premier terme, on voit donc une fois le chiffre 1, ce qui se lit donc “un 1”. Maintenant, en regardant le nombre 11, on voit deux fois le chiffre 1. On lit donc “deux 1”. On continue de la même façon en lisant “un 2" puis "un 1”. Pour compléter cette suite, il faut donc dire “un 1, un 2 et deux 1”.
Pour générer la suite, il suffit de la regarder et de la lire, c’est pourquoi Conway l’a baptisé la suite “Look and say”. Cette suite entretient des liens très métaphoriques avec les éléments chimiques et leur désintégration naturelle, si bien qu’elle porte aussi le nom de “suite audioactive”.
On pourrait s’arrêter à cette simple devinette, mais ça serait passer à côté de ce qui fait tout son charme mathématique. Tiens, par exemple, peut-on trouver le chiffre 3 dans la suite ?
Eh bien, oui, et il ne suffit pas d’aller chercher plus loin, puisque le chiffre 3 apparaît pour la première fois lors du 6eme terme, puis ne disparaît plus jamais après.
Et le chiffre 4, alors, peut-il apparaître ? Là, il faut réfléchir un peu plus. Pour apparaitre, il faudrait que le terme précédent possède 4 chiffres identiques consécutifs, comme 1111, 2222 ou 3333.
Mais pour que la chaîne 1111 apparaisse, il faudrait que la ligne précédente soit 11. Sauf que 11 ne se lit pas 1111, mais 21. Bref, la chaîne 1111 ne peut pas apparaître !
[Petit apparté : pour démontrer complètement, il faut également penser à l’enventualité où 1111 apparaîtrait sous la forme (x1) (11) (1y). Mais on peut facilement voir que c’est aussi impossible.]
On peut faire le même raisonnement pour 2222 et 3333, ce qui explique que le chiffre 4 ne peut pas apparaître naturellement dans la suite. C’est ce que Conway appelle le “théorème du jour 1”, qui permet de dire que quatre chiffres consécutifs ne peuvent pas apparaître dans la suite, et que l’on est donc restreint à utiliser les chiffres 1, 2 et 3.
Bien sûr, on peut toujours s’arranger pour faire apparaître un peu ce que l’on veut dans la suite, il suffit pour cela de changer la graine de la suite, c’est à dire, son terme initial. Si je pars de la graine 42, je vais forcément trimballer ce chiffre 4 tout au long de la suite. Mais malgré la possibilité de choisir la graine que l’on veut, 4 chiffres identiques n’apparaîtront jamais consécutivement. Jamais !
Mais les motifs 1111, 2222 ou 3333 ne sont pas les seuls motifs qui n’apparaissent jamais. On peut aussi citer le motif 333 ou 313… John Conway a catégorisé ces motifs impossible sous le nom de théorème du jour 1 et théorème du jour 2. Mais ce qui est encore plus intéressant que les motifs qui n'apparaissent pas, ce sont les motifs qui apparaissent effectivement. Le théorème qui régit ces motifs possibles porte le nom de théorème du jour 24, ou un peu moins prosaiquement, le théorème cosmologique !
Pour comprendre ça, reprenons la suite de graine 1. A partir de la septième étape, on obtient 11 13 21 32 11. Ce qui est intéressant, c’est que à partir de cet instant, la suite va se scinder en deux parties indépendantes, entre le chiffre 2 et le chiffre 1. Si on ne s’intéresse qu’à la partie de gauche, on peut voir que le dernier chiffre sera toujours le chiffre 2. Du côté de la partie droite, la suite commence par 13. A l’étape suivante, elle commencera donc par 1113, puis 3113, puis retombe à nouveau sur quelque chose qui commencera par 13. La boucle est bouclée, et le chiffre 2 n’apparaîtra donc jamais au début de cette suite de droite, empêchant toute possibilité de raccorder les deux parties. Bref : à partir de cette septième étape, la suite de Conway se scinde en deux sous-parties indépendantes. En poussant un peu plus loin les investigations, on peut voir que quelques étapes plus tard, c’est en 3 sous parties que la partie de gauche se scinde, et ainsi de suite.
Mais ce phénomène ne fonctionne pas seulement pour la suite débutant par 1, mais pour n’importe quelle graine. En partant de 2, la scission apparaîtra à partir de la 7e étape. En partant de la graine 3, il faut attendre seulement 6 étapes.
On peut alors regarder les différentes sous-parties qui peuvent se former après chaque scission. En observant attentivement, on peut s’apercevoir que ce sont toujours les mêmes motifs qui apparaissent et qui s’enchaînent.
Ces motifs se dénombrent, et on peut montrer qu’il en existe exactement 94 ; et c’est d’ailleurs parce qu’il y en a 94 que Conway a appelé chaque motif par le nom d’un des 94 éléments chimiques naturels. C’est ainsi que le motif 32 11 2 est appelé Cobalt, ou que le motif 11 12 est baptisé Potassium. Certains éléments sont cependant un peu plus complexes que d’autres…
Le tableau périodique des 94 éléments audioactifs de Conway (clic doit / ouvrir dans un nouvel onglet, pour voir en encore plus grand !)
[Petit apparté : comment ont été associé chaque élément à chaque séquence ?
En analysant les différentes séquences indécomposable de la suite comme 22 ou 13, Conway s'est aperçu qu'il y en avait 94. Du coup, il a simplement associé de manière arbitraire chaque séquence à chaque élément chimique.
En fait, ce n'est pas fait de manière totalement arbitraire : le tableau est construit de telle façon que dans la décomposition de chaque atome, on retrouve l'atome qui lui précède. Ainsi, l'atome n°92 (U) devient le n°91 (Pa), qui devient le n°90 (Th), et ainsi de suite. Le n° 86 (Rn) se décompose en deux atomes différents. Il a été décidé que l'un d'entre eux serait le n°85.
Notons quand même que Wikipédia indique seulement 92 éléments dans le tableau de Conway. Il y en a pourtant 94, qui comprennent 92 éléments communs, auxquels s'ajoutent deux éléments transuraniens, seuls élément qui contiennent d'autres chiffres que 1, 2 ou 3. Du coup, ces deux derniers éléments n'apparaissent que lorsque la graine contient un 4, un 5 ou autres.]
Ainsi, si on reprend la suite de graine 1, on peut voir qu’au moment de sa scission à la septième étape, la suite devient un alliage de Hafnium (11 13 2) et d’Etain (1 32 11). A l’étape suivante, le Hafnium se désintègre en Lutécium (31 13 12) tandis que l’étain devient de l’Indium (11 13 12 21). A l’étape suivante, on obtient un alliage Ytterbium - Cadmium, puis un alliage Thulium - Argent, et enfin, un impressionnant composé Erbium - Calcium - Cobalt - Palladium. Après 37 étapes, chaque élément du tableau périodique de Conway est apparu au moins une fois dans la suite, et après seulement 44 étapes, la chaîne est composé de quasiment 31 000 éléments, où chaque élément commun apparaît au moins une fois.
A noter tout de même que, avant d’atteindre sa septième étape, la graine passe par une phase où les termes de la suite ne sont composés d’aucun élément du tableau périodique : ces éléments que sont 1, 11, 21 ou 1211 sont appelés des éléments exotiques, et il en existe une infinité, puisqu’ils dépendent du choix de la graine initiale. Heureusement, quelle que soit la complexité de la graine initiale choisie, ces éléments exotiques sont toujours condamnés à la disparition, au profit d’un assemblage des 94 éléments naturels.
C’est cette propriété que Conway appellera le “théorème cosmologique” :
quelle que soit la graine que l’on choisit au départ, elle finira tôt ou tard par être composée uniquement d’éléments naturels qui n’interagisse pas les uns avec les autres. Exceptée bien sûr cette inutile suite débutant par 22.
Il semble même que l’on peut prouver qu’il faut au maximum 24 étapes avant qu’une graine se soit complètement transformé en un alliage d’éléments naturels, et 44 étapes supplémentaires avant que chaque élément commun n’apparaisse quelque part dans l’alliage.
Une conséquence du théorème cosmologique est l’existence d’une constante d’expansion : à chaque étape, le nombre de chiffres est, en moyenne, multiplié par 1.3(03577)…. Ce nombre correspond à l’unique racine d’un polynôme de degré 71. C’est peut-être un détail pour vous, mais l’existence d’un problème où la solution est la racine d’un polynôme de degré 71, pour les mathématiciens, ça veut dire beaucoup.
Le théorème cosmologique a été prouvé pour la première fois en 1987 par John Conway. Malheureusement, sa démonstration manuscrite a été perdue. Heureusement, Mike Guy, qui travaillait avec lui, l’a lui aussi démontré, prouvant au passage que toute graine devient un alliage d’éléments naturels en moins de 24 étapes. Malheureusement, cette démonstration manuscrite a elle aussi été perdue. La malédiction sera levée par Ekhad et Zeilberger, qui prouvent une bonne fois pour toute le théorème cosmologique en 1997.
Mais le type de démonstration utilisé pour ce théorème a longtemps fait débat dans la communauté mathématique, puisqu’une énorme partie de la démonstration passe par l’énumération exhaustive de tout un tas de suites. Une telle énumération serait particulièrement laborieuse à faire à la main, si bien que cette partie du travail a été confiée à un ordinateur.
Pour beaucoup de mathématiciens, laisser un ordinateur faire une démonstration mathématique peut être considéré comme une hérésie. C’est d’ailleurs pour cela que Thomas Hales, après avoir démontré la conjecture de Kepler en 1998 à l’aide de l’outil informatique a passé 16 ans supplémentaires à démontrer formellement que sa preuve est bien correcte.
On ne compte plus aujourd’hui les théorèmes qui s’appuient sur l’ordinateur, comme le théorème des 4 couleurs, la solution optimale d’un Rubik’s cube ou la non existence de plan projectif fini d’ordre 10. Aujourd’hui, ces démonstrations à forte teneur informatique font l’objet d’un consensus, et sont davantage acceptées. Surtout quand, à côté de ça, des démonstrations comme celle de la classification des groupes finis pèse plusieurs milliers de pages, et demande des années pour être complètement validée.
Bref : le théorème cosmologique explique finalement que dans un univers régit uniquement par la suite audioactive, n’importe quelle graine finit par engendrer la création de l’Univers tout entier. Ça a quand même plus de gueule qu’une théorie des Bogdanov !
Testez la suite de Conway avec la graine de votre choix (attention : l'algorithme ne fonctionne pas de manière optimale avec des chiffres supérieurs à 4, et n'est pas à l'abri de bugs pour cause de programmation faite à la va-vite).
Sources
Oscar Martin, Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA, dont l'introduction est très complète
Henry Bottomley, Seven complete sequences for the Conway Look and Say elements
Nathaniel Johnston, A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial
John Conway, Weird and wonderful chemistry of audioactive decay