Boîtes à différences II

Piste rouge 11 octobre 2013  - Ecrit par  Romain Bondil Voir les commentaires

On poursuit ici le jeu des boîtes à différences, en considérant maintenant $n$ nombres au lieu de quatre au départ. La lecture de cette deuxième partie est un peu plus exigeante que celle de « Boîtes à différences I » mais devrait être à la portée d’un élève de Lycée. La parité des nombres reste le point essentiel du raisonnement, et le triangle de Sierpinski pointe le bout de son nez.

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 :

1 0 1
1 1 0
0 1 1
1 0 1

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.

  Le problème qu’on veut résoudre : on cherche à savoir pour quelles valeurs de $n$ cet algorithme s’arrête toujours sur $(0,…,0)$, quel que soit le $n$-uplet avec lequel on commence.

On sait déjà que c’est le cas pour $n=4$ et pas pour $n=3$.

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.

  Conclusion pour le problème qu’on veut résoudre : les entiers $n$ que l’on cherche sont exactement ceux pour lesquels le jeu simplifié s’arrêtera pour tout les $n$-uplets.

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.

  En conséquence, on peut voir une étape du jeu simplifié comme l’opération suivante :
On remplace : $(a_1,…,a_n)$ par $(a_1 +a_2, a_2 + a_3,…,a_n + a_1)$.

On notera $J$ cette opération, c’est-à-dire :

$J(a_1,…,a_n) = (a_1 +a_2, a_2 + a_3,…,a_n + a_1)$,

où ici $a_1,...,a_n$ ne peuvent valoir que $\underline{0}$ ou $\underline{1}$.

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 :

$(a_1,…,a_n)$ + $(b_1,…,b_n)= (a_1 + b_1,…,a_n + b_n)$

La propriété essentielle pour nous est :

  pour tous les $n$-uplets $a=(a_1,…,a_n)$ et $b=(b_1,…,b_n)$ formés de $\underline{0}$ et de $\underline{1}$, on a :
$J$($a$ + $b$)$=J(a)$ + $J(b)$

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

Une preuve plus détaillée pour n=3.

En notant $\: c=a$ + $b$, par définition : $\: c=(c_1,c_2,c_3)=(a_1+b_1,a_2+b_2,a_3+b_3)$.

Par ailleurs $\: J(c)=(c_1+c_2,c_2+c_3,c_3+c_1)$.

Donc $\: J(c)=(a_1+b_1+a_2+b_2,a_2+b_2+a_3+b_3,a_3+b_3+a_1+b_1)$.

En regroupant les termes différemment :
$\: J(c)=(a_1+a_2+b_1+b_2,a_2+a_3+b_2+b_3,a_3+a_1+b_3+b_1)$.

Et finalement $\: J(c)=J(a)$ + $J(b)$.

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

  Si on fait 2 étapes du jeu simplifié, on note $J^2(a)$ le $n$-uplet obtenu en partant de $a= (a_1,…,a_n)$.

De même on note $J^p(a)$ le $n$-uplet obtenu après $p$ étapes en partant de $(a_1,…,a_n)$.

On a encore la propriété :

$J^p$($a$ + $b$) $=J^p(a)$ + $J^p(b)$

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 :

  Propriété : pour que le jeu (simplifié) se termine pour tous les $n$-uplets, il suffit qu’il se termine pour les $n$-uplets élémentaires.

En outre, comme tous ces $n$-uplets élémentaires se déduisent par rotation à partir de l’un d’eux, par exemple,
$(\underline{0},...,\underline{0},\underline{1})$, il suffit (cf. « Boîtes à différences I ») d’étudier si le jeu se termine pour ce seul $n$-uplet !

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 :

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0

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)$.

Pourquoi ces deux évolutions indépendantes ?

Simplement grâce au $0$ qui reste à l’extrémité gauche de chacune des deux parties.

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

  Conclusion 1 : Pour tout les $n$ de la forme $2^m$, c’est-à-dire $2,4,8,16,32$,..., le jeu simplifié se termine toujours en au plus $n$ étapes et exactement en $n$ étapes en partant du $n$-uplet élémentaire $(\underline{0},...,\underline{0}, \underline{1})$.

Conclusion 2 (solution du problème de cet article pour les $n$ de la forme 2m ) : grâce au 2), on sait donc que pour ces mêmes valeurs de $n$ de la forme $2^m$, le vrai jeu des différences se termine toujours.

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 :

  Propriété : Pour un entier $n$ quelconque, si le jeu simplifié à partir d’un $n$-uplet se termine, il se termine en au plus $n$ étapes.

Preuve pour ceux qui ont fait une première année de mathématiques dans le supérieur.

On fait de l’algèbre linéaire, le paragraphe 3.2. ne dit pas autre chose. L’application $J$ est un endomorphisme de l’espace vectoriel $(Z/2Z)^n$. On cherche la C.N.S. pour que $J$ soit nilpotent. Or un endomorphisme $J$ d’un espace vectoriel de dimension finie $n$ est nilpotent si, et seulement si, $J^n=0$.

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 :

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0</font 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

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

1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

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 :

  Conclusion finale : Les entiers $n$ tels que le jeu se termine pour tous les n-uplets sont exactement les $n$ de la forme $2^k$ : $2,4,8,16,32,...$ : il n’y en a pas d’autres.

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.

Post-scriptum :

L’auteur et le comité de rédaction remercient les relecteurs Reynald Thelliez et Simon Iosti pour leurs remarques.

Article édité par Patrick Popescu-Pampu

Partager cet article

Pour citer cet article :

Romain Bondil — «Boîtes à différences II » — Images des Mathématiques, CNRS, 2013

Crédits image :

Image à la une - Le logo et les dessins ont été réalisés avec Geogebra. Le triangle de Sierpinski en langage Python.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM