Des triangles équilibrés I : notions élémentaires

Piste bleue 21 juin 2014  - Ecrit par  Jonathan Chappelon Voir les commentaires (4)

Władysław Hugo Dionizy Steinhaus était non seulement un éminent mathématicien mais également un formidable vulgarisateur des mathématiques. Dans le but de promouvoir les mathématiques auprès des jeunes après la Seconde Guerre mondiale, il écrit un livre proposant une centaine de problèmes élémentaires, c’est-à-dire ne nécessitant pas de connaissances particulières ou spécifiques. Une première version de ce livre, écrite en polonais, paraît en 1958 et devant le succès rencontré, une version traduite en anglais est publiée à partir de 1964 [1]. Parmi les problèmes proposés par Steinhaus, certains le sont sans solution connue par l’auteur à cette époque. Les objets qui seront présentés ici sont issus du premier de ces problèmes ouverts, que j’appellerai simplement le problème de Steinhaus [2].

Le problème de Steinhaus

Considérons le triangle de $+$ et de $-$ dont la première ligne est $++-+-++$ et dont le reste du triangle est obtenu en appliquant la règle locale suivante : sous chaque paire de signes consécutifs on place leur produit, c’est-à-dire,
\[ \begin{array}{c@{\quad\quad}c@{\quad\quad}c@{\quad\quad}c} \cdots ++ \cdots & \cdots -- \cdots & \cdots +- \cdots & \cdots -+ \cdots \\ \color{red}{+} & \color{red}{+} & \color{red}{-} & \color{red}{-} \\ \end{array} \]
Le triangle ainsi construit est appelé le triangle de Steinhaus associé à la suite $++-+-++$

qui est constitué de $7$ lignes de signes. On dit alors que le triangle de Steinhaus est de taille $7$.

Un triangle de Steinhaus comportant autant de signes $+$ que de signes $-$ est dit équilibré.

Par exemple, le triangle associé à la suite $++-+-++$ est équilibré car il est composé de $14$ signes $+$ et $14$ signes $-$.

Steinhaus pose alors le problème de savoir pour quelles tailles il existe de tels triangles équilibrés.

Problème de Steinhaus. Pour quelles valeurs de $n$ existe-t-il un triangle de Steinhaus équilibré de taille $n$ ?

Une condition nécessaire

On appelle $\mathbf{n^{ème}}$ nombre triangulaire le nombre de signes qui constitue un triangle de taille $n$.

Un triangle de taille $n$ étant constitué de $n$ lignes, si l’on regarde les lignes du triangles une à une, la première ligne contient $n$ signes, la seconde $n-1$ signes, ... ... l’avant-dernière contient deux signes et la dernière ligne un unique signe. Le $n^{ème}$ nombre triangulaire est donc égal à la somme des $n$ premiers entiers naturels non nuls :
\[ 1+2+3+\cdots\cdots+n. \]

Les premiers nombres triangulaires sont $1,3,6,10,15,\ldots$ car
\[ \mathbf{1}\ ,\ 1+2=\mathbf{3}\ ,\ 1+2+3=\mathbf{6}\ ,\ 1+2+3+4=\mathbf{10}\ ,\ 1+2+3+4+5=\mathbf{15}\ . \]

Une condition nécessaire pour obtenir un triangle de Steinhaus équilibré de taille $n$ est donc que le $n^{ème}$ nombre triangulaire soit pair.

Proposition. Le $n^{ème}$ nombre triangulaire est pair si et seulement si $n=4q$ ou $n=4q+3$ pour un certain entier naturel $q$.

Ainsi donc, seules les longueurs de la forme $\mathbf{n = 4q}$ et $\mathbf{n = 4q+3}$ restent à considérer.

Solutions du problème de Steinhaus

Une première solution a été donnée en 1972 par le mathématicien H. Harborth. Voici son résultat, obtenu par constructions explicites.

Théorème. Pour tout entier naturel $n$ de la forme $n=4q$ et $n=4q+3$, il existe une suite de signes $+$ et $-$ de longueur $n$ dont le triangle de Steinhaus associé est équilibré.

La preuve donnée par Harborth est assez technique et ne sera pas présentée ici. Depuis, d’autres preuves de ce résultat, souvent plus simples ou alors plus conceptuelles, sont apparues dans la littérature. Voici une construction alternative donnée par S. Eliahou et D. Hachez en 2004.

Le triangle de Steinhaus associé à une suite de longueur $n$ est dit fortement équilibré si, pour tous les entiers naturels $k$ tels que $n-4k\geqslant 0$, les sous-triangles issus des $n-4k$ premiers éléments de la suite sont équilibrés. Par exemple, le triangle de Steinhaus de taille $16$ ci-dessous est fortement équilibré.

Le nombre de signes $-$ et de signes $+$ dans chaque bloc sont donnés dans le tableau suivant :
\[ \begin{array}{|c|c|c|} \hline \text{Bloc} & \text{Nombre de}\ - & \text{Nombre de}\ + \\ \hline \text{Triangle noir} & 5 & 5 \\ \hline \text{Trapèze rouge} & 13 & 13 \\ \hline \text{Trapèze vert} & 21 & 21 \\ \hline \text{Trapèze bleu} & 29 & 29 \\ \hline \end{array} \]

Comme le triangle noir, les trapèzes rouge, vert et bleu comportent autant de signes $+$ que de signes $-$, on en déduit que les triangles de Steinhaus issus des suites $+-++$ de longueur $4$, $+-++\color{Red}{++-+}$ de longueur $8$, $+-++\color{Red}{++-+}\color{Green}{+-+-}$ de longueur $12$ et $+-++\color{Red}{++-+}\color{Green}{+-+-}\color{Blue}{--++}$ de longueur $16$ sont équilibrés. C’est pourquoi le triangle associé à la suite $+-++\color{Red}{++-+}\color{Green}{+-+-}\color{Blue}{--++}$ est fortement équilibré.

L’intérêt de l’utilisation des triangles de Steinhaus fortement équilibrés est qu’il est ainsi envisageable de construire des triangles équilibrés par accrétions successives de bandes de signes équilibrées. En utilisant cette propriété, Eliahou et Hachez sont parvenus à montrer l’existence de triangles de Steinhaus fortement équilibrés pour toutes les tailles de la forme $n=4q$ et $n=4q+3$. Puisqu’un triangle fortement équilibré est équilibré, on obtient ainsi une réponse positive et complète au problème de Steinhaus.

Généralisation modulo un entier naturel

On va maintenant considérer un problème analogue à celui de Steinhaus, dans un contexte appelé l’arithmétique modulaire. Supposons que m est un entier naturel non nul. La somme modulo $\mathbf{m}$ de deux entiers $x$ et $y$ est le reste de la division euclidienne de $x+y$ par $m$, c’est-à-dire l’entier $r$ si $x+y=qm+r$, où $q$ est entier et $r\in\{0,1,\ldots,m-1\}$.

L’arithmétique modulaire est utilisée dans notre vie quotidienne. En effet, la somme modulo $12$ peut être illustrée de la manière suivante : s’il est 8h du matin à l’instant $t$, alors à l’instant $t+6$ il sera 2h de l’après-midi car la somme modulo $12$ de $8$ et $6$ vaut $2$ : $8+6=14=12+2$.

En guise d’exercice, toujours pour $m=12$, le lecteur peut chercher la règle de calcul modulo $12$ sur $\{0,1,\ldots,11\}$, c’est-à-dire on calcule toutes les sommes modulo $12$ de $x$ et $y$ pour toutes valeurs de $x$ et $y$ dans $\{0,1,\ldots,11\}$.

\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \mathbf{x\setminus y} & \mathbf{0} & \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} & \mathbf{6} & \mathbf{7} & \mathbf{8} & \mathbf{9} & \mathbf{10} & \mathbf{11} \\ \hline \mathbf{0} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline \mathbf{1} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 \\ \hline \mathbf{2} & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \hline \end{array} \]

Solution

\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \mathbf{x\setminus y} & \mathbf{0} & \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} & \color{Red}{\mathbf{6}} & \mathbf{7} & \mathbf{8} & \mathbf{9} & \mathbf{10} & \mathbf{11} \\ \hline \mathbf{0} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline \mathbf{1} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 \\ \hline \mathbf{2} & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 \\ \hline \mathbf{3} & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 \\ \hline \mathbf{4} & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 \\ \hline \mathbf{5} & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 \\ \hline \mathbf{6} & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \mathbf{7} & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \color{Red}{\mathbf{8}} & 8 & 9 & 10 & 11 & 0 & 1 & \color{Red}{2} & 3 & 4 & 5 & 6 & 7 \\ \hline \mathbf{9} & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \mathbf{10} & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \mathbf{11} & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \end{array} \]

On définit maintenant les triangles de Steinhaus modulo $m$ de la même manière que les triangles de Steinhaus de signes $+$ et $-$ mais en remplaçant la règle locale du produit de signes par la somme modulo $m$.

Un triangle de Steinhaus modulo $\mathbf{m}$ de taille $\mathbf{n}$ est un triangle à $n$ lignes dont la première ligne est constituée de $n$ éléments dans $\{0,1,\ldots,m-1\}$ et dont le reste du triangle est obtenu en appliquant la règle locale suivante : sous chaque paire d’éléments consécutifs on place leur somme modulo $m$.

Par exemple, pour $m=5$, le triangle de Steinhaus modulo $5$ associé à la suite $(2,2,0,3,3)$ est le triangle suivant :

Remarquons que pour $m=2$ on retrouve les triangles de Steinhaus définis au début de cet article où les signes $+$ et $-$ sont remplacés par les entiers $0$ et $1$, respectivement. En effet, on peut voir la correspondance entre les opérations de produit de signes et la somme modulo $2$ :
\[ \begin{array}{ccc} +.+ & = & + \\ +.- & = & - \\ -.+ & = & - \\ -.- & = & + \\ \end{array} \quad \Longleftrightarrow \quad \begin{array}{ccc} 0+0 & = & 0 \\ 0+1 & = & 1 \\ 1+0 & = & 1 \\ 1+1 & = & 0 \\ \end{array} \]

On remarque qu’un triangle de Steinhaus modulo $m$ de taille $n$ est composé d’un nombre d’éléments de $\{0,1,\ldots,m-1\}$ égal au $n^{ème}$ nombre triangulaire $1+2+\cdots+n$.

Un triangle de Steinhaus modulo $m$ est dit équilibré s’il contient chaque élément de $\{0,1,\ldots,m-1\}$ en même nombre.

Par exemple, le triangle $\bigtriangledown (2,2,0,3,3)$, représenté ci-dessus, est équilibré modulo $5$ car il contient chaque élément de $\{0,1,2,3,4\}$ exactement trois fois.

Cette généralisation modulo $m$ des triangles de Steinhaus a été proposée en 1976 par John C. Molluzzo. Tout comme dans le cas $m = 2$, une condition arithmétique évidente sur la taille d’un triangle de Steinhaus doit être satisfaite pour que celui-ci puisse être équilibré modulo $m$. Cette condition est tout simplement que le nombre d’éléments du triangle doit être divisible par $m$, c’est-à-dire,

Pour avoir un triangle de Steinhaus de taille $n$ qui soit équilibré modulo $m$, le $n^{ème}$ nombre triangulaire $1+2+\cdots+n$ doit être divisible par $m$.

Molluzzo pose alors la question suivante.

Problème de Molluzzo. Fixons un entier $m \geqslant 2$. Pour chaque entier naturel $n$ vérifiant la condition arithmétique ci-dessus, à savoir que le $n^{ème}$ nombre triangulaire est divisible par $m$, existe-t-il un triangle de Steinhaus de taille $n$ qui soit équilibré modulo $m$ ?

Comme nous l’avons vu auparavant, ce problème est complètement résolu de manière positive dans le cas binaire $m=2$. Dans la seconde partie de cet article, on s’intéressera au cas $m\geqslant 3$ et plus particulièrement à la conjecture suivante.

Conjecture.
Pour tout entier $m\geqslant 2$, il existe une infinité de triangles de Steinhaus équilibrés modulo $m$.

En l’état actuel des connaissances, cette conjecture est complètement ouverte pour $m$ pair supérieur ou égal à $12$. Par contre, elle est bien vraie pour tout $m$ impair, comme nous le verrons dans la seconde partie de cet article.

En guise d’exercice de préparation à la seconde partie à venir de cet article, je propose au lecteur de tenter de vérifier le cas $m = 3$ de la conjecture ci-dessus, à savoir de montrer l’existence d’une infinité de triangle de Steinhaus équilibrés modulo $3$.

Quelques essais en longueurs $n = 3$ et $n = 6$ pourraient bien suffire pour deviner une construction plus générale ...

Post-scriptum :

L’auteur tient à remercier les responsables de cette rubrique Shalom Eliahou et Bruno Martin pour leurs précieux commentaires et suggestions, ainsi que les relecteurs jeanpol3 et P. Levallois pour leur relecture attentive.

Article édité par Shalom Eliahou

Notes

[1H. Steinhaus. One hundred problems in elementary mathematics. Basic Books Inc. Publishers, New York, 1964. With a foreword by Martin Gardner.

[2Un article sur un autre problème proposé par Steinhaus est disponible ici : Hexagones et démocratie.

Partager cet article

Pour citer cet article :

Jonathan Chappelon — «Des triangles équilibrés I : notions élémentaires» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

  • Des triangles équilibrés I : notions élémentaires

    le 23 juin 2014 à 08:19, par ROUX

    Je l’ai fait, et c’est bon. Je suis donc préparé.

    Répondre à ce message
  • Des triangles équilibrés I : notions élémentaires

    le 7 juillet 2014 à 16:48, par bayéma

    une question : comment trouver la « bonne » suite de signes pour construire un triangle équilibré ? en effet, le théorème sur l’existence de « bonnes » suites ne précise pas lesquelles.
    si, sur l’exemple que vous donnez, ++-+-++, on permute deux signes, par exemple +-++-++, l’équilibre disparaît.
    josef bayéma, plasticien, guadeloupe.

    Répondre à ce message
  • Des triangles équilibrés I : notions élémentaires

    le 10 juillet 2014 à 09:12, par Jonathan Chappelon

    Il existe de nombreuses méthodes pour rechercher des triangles équilibrés. On peut par exemple, pour une taille donnée, faire une recherche exhaustive. Dans l’article, je cite une solution qui a été proposée par S. Eliahou et D. Hachez en 2004 qui consiste à construire des triangles fortement équilibrés. Les détails de cette construction peuvent être consultés dans leur article disponible librement à cette adresse :

    http://projecteuclid.org/euclid.em/1090350936

    Dans la seconde partie de cet article, une construction explicite de triangles équilibrés modulo un nombre impair sera donnée.

    Répondre à ce message
  • Des triangles équilibrés I : notions élémentaires

    le 12 juillet 2014 à 21:36, par bayéma

    bon, j’attends donc la seconde partie avec impatience. je suis allé à l’adresse que vous m’indiquez, merci.
    josef bayéma.

    Répondre à ce message

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