Un symbole ajouté peut-il provoquer deux carrés dans un mot?

En mathématique combinatoire, un mot est une suite de symboles qui peuvent être assemblés afin de construire une chaîne de caractères potentiellement infinie.

Voici quelques mots d’après cette definition:

• fatcha
• BBBBBB
• abcabcabc
• 1111222333
• …

Qu’est ce qu’un carré dans un mot?

Un carré est une suite de deux blocs consécutifs qui ont la même série de symboles. La taille de la répétition sera dès lors le nombre de caractères qui compose un bloc.
Le mot “ABCBA” ne contient pas de répétition alors que le mot “ABB” contient deux blocs consécutifs formés de “B” et est de taille 1, ainsi, “ABCABC” est donc un carré de taille 3.

Si nous utilisons un alphabet binaire, composé des symboles 1 & 0, il est impossible de créer un mot sans carré de longueur supérieure à 3. En effet, dans le mot suivant “010", le prochain symbole sera “0” ou “1” et donc un carré d’une taille de 1 apparaîtra si le symbole “0” est choisi; tandis qu’un carré de longueur 2 apparaîtra si l’on choisit le symbole “1”.

Un mot sans carré est un mot ne contenant pas de facteur carré.

Un symbole ajouté en fin de mot peut-il terminer 2 facteurs carrés de longueurs différentes?

Autrement dit : Est-il possible que l’ajout d’un symbole dans l’algorithme puisse provoquer deux facteurs carrés de tailles différentes?

Preuve par contradiction

Dans un mot, disons que nous détectons donc 2 facteurs carrés (un facteur est une sous partie d’un mot) de taille différente après l’ajout d’un symbole en fin de mot. Le premier bloc du carré le plus grand est A, et le deuxième bloc de ce carré est B; le deuxième facteur carré de taille plus petite est défini par les deux blocs A et B.

Prenons le mot commençant par S1 et se terminant par Sn (voir figure suivante). Le dernier symbole Sn termine un carré qui est composé des symboles S1; S2; S3; S…. C’est-à-dire que le facteur B répète la facteur A.

Concernant le deuxième carré de taille plus petite, nous pourrions donc émettre l’hypothèse qu’il se trouve complètement dans la partie B, représentée ici par A’ et B’ dans la figure suivante. Mais, si c’était le cas, elle aurait aussi été présente dans le facteur A. Cette disposition est donc impossible puisque le carré aurait été détecté plus tôt dans A.

L’autre hypothèse, c’est que le deuxième carré soit de longueur plus grande que la moitié du mot et donc, il commencerait avant le début du facteur B, c’est-à-dire sur le facteur A.

Un facteur mot qui termine le facteur A tout en étant identique à celui de la fin de la séquence B et aussi qu’il soit le début d’ A’ (puisque A’ est à cheval entre A et B) et donc aussi le début de B’ (vu que B’ serait une répétition de A’) est impossible à construire sans carré. En effet, le début de A’ (S3 S…) aura le même facteur composé de symboles que la fin de A’ (S…;Sn-2) et le début de B’, ainsi, il existera donc une répétition entre ces deux derniers éléments.

Conclusion

Nous pouvons donc en conclure qu’il n’est pas possible que l’ajout d’un seul symbole puisse provoquer deux carrés de taille différente sans que cela ne soit détecté précédemment.