Article : Les motifs évitables - Lycée Condorcet (Saint Quentin)

Article
Résumé de la production
L’objectif est de créer des mots infinis (exemple : abbaabab… ) à l’aide d’un alphabet défini (exemple : avec uniquement les caractères"a" et "b"), tout en évitant la répétition d’un certain motif. Dans l’article, les auteurs prouvent qu’il n'est pas possible de créer un mot infini à l’aide d’un alphabet de 2 caractères en évitant le motif carré (répétition de deux ensembles de caractères identiques et successifs), mais qu’il est possible d’éviter le motif cube (répétition de trois ensembles de caractères identiques et successifs). La preuve s’appuie sur l’existence du mot de Morse qui, par construction, ne contient pas de motif cube. Ensuite, les auteurs prouvent qu’il est possible de créer un mot infini avec un alphabet de 3 caractères en évitant le motif carré.
Mots clés
combinatoire des mots