E545. Le triangle de Steinhaus Imprimer
E5. Enigmes logiques

calculator_edit.png computer.png  

Soit un triangle équilatéral ABC de côté n entier ≥ 2. Sur la première ligne du côté horizontal BC, on écrit une suite de n caractères constitués de 0 et de 1 puis sur une deuxième ligne on écrit une suite de n ‒ 1 caractères selon la règle suivante: deux chiffres "1" ou deux chiffres "0" adjacents de la première ligne génèrent le chiffre "1" placé à cheval au dessus d'eux. Sinon le chiffre généré est un "0". Selon la même règle, on poursuit le remplissage des lignes supérieures avec des suites de n ‒ 2, n ‒ 3,..caractères jusqu'à la n-ième ligne du sommet A où on écrit un seul chiffre.
Exemple: avec n = 5 et la suite 1 1 0 1 0 de la première ligne, on obtient le triangle suivant:

                                           E545
 
Le triangle est appelé triangle de Steinhaus (1) si à l'intérieur du triangle ABC le nombre de "0" est identique au nombre de "1". On note que le triangle de l'exemple ci-dessus avec 7 chiffres "1" et 8 chiffres "0" n'est pas un triangle de Steinhaus.
Q1 Déterminez les valeurs de n ≤ 20 et pour chacune d'elles une suite de la première ligne qui permettent de construire des triangles de Steinhaus.
Q2 Pour quelles valeurs de n est-il toujours possible de construire des triangles de Steinhaus? Justifiez votre réponse.
Q3 Pour un entier m quelconque qui rend possible la construction d'un triangle de Steinhaus, trouvez une méthode de construction d'une suite de m caractères de la première ligne. Record à battre m = 240!

(1)H. Steinhaus: One hundred problems in elementary mathematics (1963)

 Solution


pdfFabien Gigante,pdfMichel Goudard et pdfSimon Pellicer ont très bien analysé le problème et trouvé les algorithmes permettant de battre largement le record m = 240.
Le triangle de Steinhaus a donné lieu à de nombreuses études théoriques dont on trouve ci-après quelques exemplaires accessibles par les noms de leurs auteurs:
- pdfHeiko Harborth,pdfJosep M. Brunat et Montserrat Maureso et pdfShalom Eliahou.