Chocolat au lait ? Chocolat noir ? Les plus gourmands hésitent sûrement chaque jour entre plusieurs tablettes. Si l’on se limite à ces deux choix, il est bien difficile d’éviter les répétitions. Qu’entend-on par là ? Notons L pour un chocolat au lait et N pour un chocolat noir. Le gourmand versatile, qui ne veut pas répéter deux fois la même dégustation, ne peut pas commencer sa série d’expériences gustatives par LL ou NN. Commençons donc par LN. On ne peut pas poursuivre avec un chocolat noir (ce qui donnerait LNN, le N est répété). Poursuivons donc avec un chocolat au lait : LNL. Ici, l’amateur de chocolat est condamné à la répétition : LNLL (on a répété L) ou LNLN (et on a répété le motif LN). On dit que les carrés ne sont pas évitables.
Soit, mais alors qu’en est-il des cubes ? Peut-on écrire une suite de L et de N sans qu’il n’y apparaisse trois fois de suite le même motif, comme dans le mot « blablabla » ? La réponse est oui ! Et la construction de cette suite par récurrence est plus simple qu’il n’y paraît.
Du chocolat au binaire ----------------------
Le premier mathématicien à avoir croisé cette fameuse suite est Eugène Prouhet (1817–1867) en 1851, dans un problème d’arithmétique. Cette suite est tellement riche qu’elle a ensuite été redécouverte dans des domaines complètement différents, notamment par Axel Thue (1863–1922) en 1912, pour des questions de combinatoire des mots, puis Marston Morse (1892–1977), le père de la théorie de Morse en topologie, dans un problème de géométrie différentielle en 1921 ! D’où le nom de « mot (ou suite) de (Prouhet–)Thue–Morse », ou plus simplement de « mot de Morse ».
Quittons un instant nos friandes questions et notons plus communément 0 un chocolat au lait et 1 un chocolat noir. Les chiffres 0 et 1 doivent être ici considérés comme de simples caractères, et non des nombres. L’idée est de partir du mot m0 = 0 et d’appliquer, à chaque caractère, la petite transformation suivante : le morphisme σ\sigma défini par σ\sigma(0) = 01 et σ\sigma(1) = 10.