La suite S de Kolakoski: 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, ... est un exemple de suite "qui se lit elle-même". Elle est constituée de chaînes de 1 et de chaînes de 2 en alternance, et la longueur de la prochaine chaîne est toujours le prochain nombre de la suite:

Le premier terme est 1, donc la première chaîne a longueur 1. La chaîne suivante est constituée de 2, et sa longueur est le deuxième terme, soit 2. Ainsi les trois premiers termes sont 1, 2, 2. Donc la troisième chaîne, constituée de 1, a aussi longueur 2: Les cinq premier termes sont 1, 2, 2, 1, 1. On a donc ensuite deux chaîne de longueur 1, et la suite devient 1, 2, 2, 1, 1, 2, 1. Et ainsi de suite.

Problème de novembre:

Solution au problème MP27

Ce mois-ce, Pierre Bornsztein (de France) et Juan Mir Pieras (d'Espagne) nous ont répondu. Nous reproduisons ici la solution de Bornsztein.

Par l'absurde : Supposons que ce nombre, noté S, soit rationnel.

Alors son développement décimal est périodique, tout au moins à partir d'un certain rang. Parmi toutes les périodes possibles (c.à.d. les séquences de chiffres consécutifs qui se répétent identiquement à elles-mêmes), on en considère une de longueur minimale, et que l'on note A.

Par construction, l'écriture décimale de S est construite par des "blocs" successifs de chiffres "1" et de chiffres "2", alternativement, et chacun de ces blocs ne contient pas plus de deux chiffres. De plus, la présence d'un "2" assure qu'un bloc de deux chiffres sera présent plus loin dans l'écriture décimale de S.

En particulier, A contient au moins un bloc de deux chiffres. Cela entraine que le nombre de blocs que contient A est strictement inférieur au nombre de chiffres qui composent A. (*) De plus, quitte à décaler la période, on peut supposer que la séquence A commence avec le début d'un bloc. Par suite, la séquence A se termine avec la fin d'un bloc.

Pour engendrer une séquence donnée A, il faut une séquence G de termes consécutifs de la suite de Kolakoski. Chaque terme de cette séquence G engendre un bloc de "1" ou un bloc de "2". Et, d'après (*), le nombre de chiffres qui composent la séquence G est strictement inférieur au nombre de chiffres qui composent la séquence A. (**)

Mais, puisque A se termine par la fin d'un bloc, le dernier terme de G qui a servi à engendrer cette séquence A ne sert pas à construire le début de la séquence A suivante. Cette séquence A suivante doit donc être engendrée par une autre séquence G, identique à la première, et qui succède immédiatement à la première séquence G dans la suite de Kolakoski. Une récurrence immédiate prouve alors que la suite de Kolakoski, et donc l'écriture décimale de S, est périodique de période G. Mais alors, (**) contredit la minimalité de A.

Et donc, S n'est pas rationnel.

La suite de Kolakoski est d'abord apparue en tant que problème proposé par William Kolakoski dans American Mathematical Monthly 72 (1965) p. 674 et 73 (June 1966) pp. 681-682 (Problème 5304). On trouve plus d'informations à ce sujet dans l'encyclopédie des suites entières de N.J.A. Sloane au site