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

Brieuc Barthélemy
Apr 30, 2019 · 3 min read

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.

Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store