1. Introduction :

Dans « Boîtes à différences I » nous avons étudié les boîtes à différences construites à partir de quatre nombres entiers.

Par commodité ici, on appellera quadruplet quatre nombres $(a,b,c,d)$ écrits entre parenthèses.

Nous avons montré que dans le jeu qui consiste à remplacer $(a,b,c,d)$ par $(dist(a,b),dist(b,c),dist(c,d),dist(d,a))$ et à recommencer, on arrivait toujours au quadruplet $(0,0,0,0)$ à partir duquel il ne se passe plus rien.

Rappelons que nous désignons ici par $dist(a,b)$ la distance de $a$ à $b$, c’est-à-dire $dist(a,b)=b-a$ si $b≥a$ et $dist(a,b)=a-b$ si $a≥b$.

Si au lieu de partir de quatre nombres, on part par exemple de trois, c’est-à-dire d’un triplet et qu’on remplace à chaque étape $(a,b,c)$ par $(dist(a,b),dist(b,c),dist(c,a))$, il n’est pas difficile de trouver un exemple de comportement très différent :

qui montre qu’au bout de trois étapes, on est ramené au point de départ, et donc que la suite des triplets sera périodique de période 3.

En termes de représentation graphique, nous aurons la mise en abyme suivante :

où le gros triangle rouge se retrouve en plus petit (tourné, il est vrai, mais le lecteur de l’article précédent sait qu’une telle rotation ne change rien à notre problème).

Convention de langage : En mathématiques, on dit aussi qu’un triplet est un $3$-uplet, un quadruplet est un $4$-uplet, et pour un entier $n$ quelconque, on parlera d’un $n$-uplet pour désigner une écriture $(a_1,…,a_n)$.

Le même jeu des boîtes à différences : D’une manière générale, on considérera pour tout entier $n≥3$, le jeu des boites à différences qui à chaque étape remplace le $n$-uplet $(a_1,…,a_n)$ par le $n$-uplet $(dist(a_1,a_2),…,dist(a_n,a_1))$. En maths, un tel jeu s’appelle plutôt un algorithme.

Exemple de début de jeu avec des sextuplets :

2. Le jeu simplifié, encore lui :

Dans l’article précédent, on a parlé du jeu simplifié qui consistait à remplacer au départ chaque nombre par « $p$ » s’il est pair et par « $i$ » s’il est impair.

Pour que l’algorithme s’arrête pour tous les entiers $(a_1,...,a_n)$ il est nécessaire qu’en particulier le jeu simplifié s’arrête, c’est-à-dire arrive à $(p,p,...,p)$.

Mais mieux, les mêmes arguments que dans « Boîtes à différences I » s’appliquent pour montrer que la réciproque est vraie.

En effet si on sait que le jeu simplifié s’arrête toujours sur $(p,..,p)$, cela signifie qu’à partir d’un $n$-uplet d’entiers $(a_1,…,a_n)$, on arrive toujours à un $n$-uplet de nombres tous pairs, puis en recommençant de même on arrive à des nombres tous divisibles par $4$, et ainsi de suite, jusqu’à ce que ce que les nombres obtenus soient divisibles par un nombre de la forme
$2 \times 2 \times \cdots \times 2$ plus grand que le maximum des nombres
$( a_1,…,a_n)$ de départ.

3. Le jeu simplifié est additif :

Pour tester si le jeu simplifié appliqué à tous les $n$-uplets $(a_1,…,a_n)$ s’arrête, sachant que $a_1$ ne peut valoir que $p$ ou $i$ et de même pour les autres, il y a quand même $2^n$ possibilités à tester.

Mais le jeu simplifié a des propriétés tout à fait remarquables qui vont nous faciliter les choses.

3.1. Une nouvelle description du jeu simplifié

Pour commencer, il est nécessaire de faire un peu plus d’algèbre : le symbole $p$ sera noté plutôt $\underline{0}$ et $i$ sera noté $\underline{1}$.

Avec ce choix de notations, le calcul précédent avec $p$ et $i$ donne un calcul naturel avec ce $\underline{0}$ et ce $\underline{1}$ (ajouter $\underline{0}$ ne change rien), à ceci près que $\underline{1} + \underline{1} =\underline{0}$.

Remarque : Dans le jeu simplifié, la « distance » entre deux pairs (respectivement deux impairs) est $\underline{0}$ et celle entre un pair et un impair est $\underline{1}$.

Or il y a une façon très simple de voir cette distance, en faisant la somme des deux nombres (toujours à cause de cette règle
$\underline{1} + \underline{1} =\underline{0}$)  : la somme de deux nombres de même parité sera toujours paire par exemple.

Par exemple $J(\underline{0}, \underline{1}, \underline{0})= ( \underline{1}, \underline{1}, \underline{0})$.

3.2. Comportement pour l’addition des $n$-uplets

On peut considérer une addition pour les $n$-uplets, qu’on va noter en rouge, définie comme suit :

La propriété essentielle pour nous est :

Ce qui fait marcher cette propriété est qu’on peut faire les additions dans l’ordre qu’on veut.

On va même généraliser un peu, en appliquant plusieurs fois la propriété précédente :

3.3. Réduction du problèmes aux $n$-uplets les plus simples

On appellera $n$-uplets élémentaires, les $n$-uplets où il n’y a qu’un et un seul $\underline{1}$ qui apparaît, toutes les autres entrées du $n$-uplet étant des $\underline{0}$.
Ainsi pour $n=3$, les trois triplets élémentaires sont $(\underline{1},\underline{0},\underline{0})$, $(\underline{0},\underline{1},\underline{0})$ et $(\underline{0},\underline{0},\underline{1})$.

En général il y a exactement $n$ tels $n$-uplets élémentaires : le premier est
$(\underline{1} , \underline{0},..., \underline{0})$ et le dernier est
$(\underline{0},..., \underline{0}, \underline{1})$.

Avec l’addition des $n$-uplets qu’on a définie au 3.2., tout $n$-uplet peut s’écrire comme une somme de $n$-uplets élémentaires.

À titre d’exemple, $(\underline{0}, \underline{1}, \underline{1}, \underline{0}, \underline{1})$ s’écrit comme somme de trois 5-uplets élémentaires :

$(\underline{0} , \underline{1}, \underline{1}, \underline{0}, \underline{1})= (\underline{0} ,\underline{1}, \underline{0}, \underline{0}, \underline{0})+(\underline{0}, \underline{0}, \underline{1}, \underline{0}, \underline{0})+(\underline{0} , \underline{0}, \underline{0} , \underline{0}, \underline{1})$.

Avec la propriété du 3.2., on déduit la :

On a quand même beaucoup simplifié le problème. Parfois les mathématiciens emploient la jolie expression : « dévisser » le problème.

A titre de comparaison, dans « Boîtes à différences I », nous avions dû étudier toutes les possibilités « à la main ».

4. L’étude à partir de (0,...,0,1) :

Pour alléger l’écriture de ce qui suit, on notera $0$ pour $\underline{0}$ et $1$ pour $\underline{1}$, mais il faut penser que $1+1=0$ dans ce cadre.

On étudie le tableau d’évolution de $(0,...,0,1)$ dans le jeu.

4.1. Cas où $n$ est une puissance de 2 : 4,8,16,32...

Pour $n=8$, on termine en exactement huit étapes :

Mais surtout, il apparaît que la ligne 4 du tableau (en faisant commencer le tableau à la ligne 0), se décompose en deux parties identiques, marquées en rouge et en vert, qui vont évoluer chacune ensuite de la même façon en suivant à l’évolution déjà connue pour le quadruplet $(0,0,0,1)$.

En généralisant cette remarque, on obtient la :

4.2 Et les autres valeurs de $n$ ?

Au niveau où nous sommes, je n’ai pas de preuve vraiment élémentaire du résultat suivant :

Or, partant de $(0,0,...,0,1)$, si on se limite aux $n-1$ premières étapes, le jeu simplifié reproduit un phénomène bien étudié par ailleurs, qui s’appelle le triangle de Sierpinski.
Le fait qu’il fasse $(0,0,..,0)$ à la $n$-ième étape se voit bien sûr à la $(n-1)$-ième, où on aura une ligne de $1$ (ou une ligne de $0$ s’il se terminait avant, mais cela ne se produit pas).

Reprenons le tableau de jeu ci-dessus en partant de $(0,0,...,0,1)$ , en enlevant la dernière ligne, et en grisant les 0 au-dessus de la diagonale sud-ouest/nord-est, comme ceci :

Si on élimine les 0 grisés et qu’au lieu d’aligner à droite, on centre, on obtient alors le tableau suivant.

Remarque : L’avantage de cette façon de présenter les calculs est que, à part le nombre n d’étapes, la représentation est indépendante de la taille des multiplets.

En remplaçant les 1 par un • et les 0 par un •, on obtient :

La règle de construction de ce nouveau tableau, équivalent au précédent pour nous, est très simple :

Règle 1 : au début et à la fin de chaque ligne, il y a toujours un point noir : •

Règle 2 : pour construire une nouvelle ligne à partir de la précédente, entre deux points de même couleur, on met un point rouge •, et entre deux points de couleurs différentes, on met un point noir •

Voici ce que donne la même construction avec 256 lignes (les ronds • et • ont été collés les uns aux autres) c’est-à-dire 255 étapes.

C’est ce type de triangle qu’on appelle triangle de Sierpinski. On peut aussi en réaliser une version 3D (pyramide de Sierpinski), comme le montre une photo déjà postée sur « Images des Maths ». On trouvera aussi sur IdM une brève biographie de W. Sierpinski.

Que comprend-on du schéma de construction d’un tel triangle ? On peut construire un tel triangle à l’envers par rapport à ce que nous venons de faire, c’est-à-dire en partant du plus gros des triangles noirs dessinés, puis en dessinant trois triangles noirs de mêmes tailles comme ceci, qui délimitent un triangle rouge vif qui ne contiendra jamais de points noirs par la suite.

Puis en recommençant dans chacun des trois triangles roses :

Et ainsi de suite !

Conséquence pour nous : En repassant à la description avec des points • et •, les seules lignes toutes noires seront les lignes dont le numéro est de la forme
$2^k-1$, autrement dit $3,7,15,31$. Ce seront donc les seules lignes du jeu simplifié qui ne contiennent que des $1$. Donc les seules qui seront suivies par une ligne qui ne contienne que des $0$ : la condition d’arrêt du jeu simplifié.

Grâce au lien déjà fait entre le vrai jeu et le jeu simplifié, on obtient donc notre :

Références :  Le problème étudié ici est connu sous le double nom de diffy boxes et de problème de Ducci.

Les références sur le triangle de Sierpinski sont très nombreuses, et notamment sur sa construction à partir du triangle de Pascal : j’aimerais juste citer le joli livre le démon des maths de Hans Magnus Enzensberger. L’excellente illustratrice R. S. Berner a aussi réalisé de nombreux livres pour enfants dont la série Le livre du printemps, Le livre de l’été,.. qui m’a fait passer des beaux moments d’observations avec mes enfants !

En écrivant cet article, j’ai reçu la Gazette des mathématiciens, consacrée à B. Mandelbrot, le père de la géométrie fractale. On y trouve une photo d’un coquillage appelé « Cymbiola innexa Reeve » dont le motif reprend le motif de Sierpinski. En voici une photo dans ce forum d’amateurs de coquillages.