Les suites qui se racontent et le jeu de Robinson

Les suites qui se racontent sont entrées un jour dans ma vie pour ne plus en sortir à travers une énigme mathématique que me posa un ami :

Si une suite commence par 0, 10, 1110, 3110, 132110, 13123110, quel est le nombre suivant ?

Ma réponse fût 23124110 (dans 0, je compte un 0 ce que j’écris 10 ; dans 10, je compte un 1, un 0 ce que j’écris 1110 ; dans 1110, je compte trois 1, un 0 ce qui donne 3110, etc.). En quelque sorte, chaque terme “raconte” le précédent.

L’énigme se transforme en suite … et en conjecture

J’aurais pu m’arrêter là mais, allez savoir pourquoi, je continuais : 1413223110, 1423224110, 2413323110, 1433223110, 1433223110. La suite est donc constante à partir de ce terme. Le résultat me sembla surprenant, c’est pourquoi j’essayais d’autres valeurs initiales. J’avais beau examiner un grand nombre de valeurs, je trouvais toujours une suite périodique, la période étant 1, 2 ou 3. Très vite convaincu de ce résultat, je tentais de prouver ce qui était devenu une conjecture. Après plusieurs mois de recherche, je trouvais 109 points fixes, 31 cycles de période deux et 10 cycles de période trois (voir plus loin leur liste exhaustive). 

Puis la conjecture en théorème

Pour trouver tous les cycles des suites qui se racontent, on peut utiliser un ordinateur à condition de réduire d’abord le nombre de cas à essayer. Il est également possible de faire un raisonnement analytique classique. Pour ceux que le sujet intéresse, j’ai raconté cette quête de la preuve dans :

Hervé Lehning, « Computer-aided or analytic proof? », College Mathematics Journal, vol. 21, no 3,‎ 1990, p. 228-239

Hervé Lehning, « Quelle est la meilleure preuve ? », Quadrature, n° 11, 1992 (Ce dernier article est illustré Par Charb.)

Page de l’article avec l’illustration de Charb

Le jeu de Robinson

Quand j’ai proposé mon article, on me fit remarquer que je résolvais sans le savoir une conjecture de Douglas Hofstadter (parue dans Ma Thémagie) liée à un jeu inventé dans les années soixante-dix par Raphaël Robinson (1911 – 1995), un mathématicien américain. Le but est de remplir les blancs de la phrase suivante afin qu’elle devienne vraie :

Dans cette phrase, il y a __ 0, __ 1, __ 2, __ 3, __ 4, __ 5, __ 6, __ 7, __ 8, et __ 9

On remarque immédiatement que tout point fixe utilisant les dix chiffres d’une suite qui se raconte est solution, et réciproquement. En utilisant la liste des 109 points fixes, on trouve deux solutions :

Dans cette phrase, il y a 1 0, 11 1, 2 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, et 1 9.

Dans cette phrase, il y a 1 0, 7 1, 3 2, 2 3, 1 4, 1 5, 1 6, 2 7, 1 8, et 1 9.

Les autres points fixes fournissent des solutions à un jeu de Robinson légèrement modifié où certains chiffres peuvent être supprimés. Par exemple :

Dans cette phrase, il y a 3 1, 2 2, 3 3, 1 4 et 1 5.

Suppléments : cycles des suites qui se racontent

Pour en simplifier la lecture, je noterai <n> le fait que n chiffres, choisis arbitrairement parmi les chiffres possibles, soient précédés d’un 1.

Liste des points fixes

1 9 / 1 8 / 1 7 / 1 6 / 1 5 / 1 4 / 1 3 / 2 2 / 11 1 / 1 0 et

1 9 / 1 8 / 2 7 / 1 6 / 1 5 / 2 3 / 3 2 / 7 1 / 1 0 ce qui fait 2 points fixes,

11 1 / <8> ce qui fait 9 points fixes, 2 6 / 2 3 / 3 2 / 6 1 / <5> ce qui fait 6 points fixes, 2 5 / 2 3 / 3 2 / 5 1 / <4> ce qui fait 15 points fixes, 2 4 / 2 3 / 3 2 / 4 1 / <3> ce qui fait 20 points fixes, 3 3 / 2 2 / 3 1 / <2> ce qui fait 21 points fixes, 2 3 / 3 2 / 2 1 / <1> ce qui fait 7 points fixes, 3 3 / 3 1 / <2> ce qui fait 28 points fixes, 2 2 ce qui fait 1 point fixe, d’où un total de 109 points fixes.

Liste des cycles de période deux

2 8 / 1 7 /  1 4 / 4 2 / 7 1 / <5>       1 8 / 2 7 / 2 4 / 2 2 / 8 1 / <5> ce qui fait 1 cycle, 

2 7 / 1 6 / 1 4 / 4 2 / 6 1 / <4>                   1 7 / 2 6 / 2 4 / 2 2 / 7 1 / <4> ce qui fait 5 cycles,

2 6 / 1 5 / 1 4 / 4 2 / 5 1 / <3>                   1 6 / 2 5 / 2 4 / 2 2 / 6 1 / <3> ce qui fait 10 cycles,

2 4 / 1 3 / 4 2 / 3 1 / <2>                 2 4 / 2 3 / 2 2 / 4 1 / <2> ce qui fait 15 cycles,

d’où un total de 31 cycles de période 2.

Liste des cycles de période trois

2 5 / 1 4 / 1 3 / 4 2 / 4 1 / <2>     1 5 / 3 4 / 1 3 / 2 2 / 5 1 / <2>      2 5 / 1 4 / 2 3 / 2 2 / 5 1/ <2>

ce qui fait 10 cycles de période 3.