La tour et l’hypercube | Le jeu des sciences

Dans une triviale tour de Hanoï à deux disques, A et B, comme nous l’avons vu la semaine dernière, la séquence de mouvements pour effectuer le transfert d’un axe à l’autre est ABA. Dans celui à trois disques, A, B et C, la séquence est ABACABA. C’est-à-dire que nous déplaçons d’abord les trois disques supérieurs comme dans la tour à trois disques, puis nous changeons l’axe du quatrième disque, et enfin nous répétons le transfert de trois disques pour les placer sur le quatrième. Et avec quatre disques, A, B, C et D, le processus est analogue : on déplace les trois premiers vers un autre axe, on change le quatrième en axe libre et on répète la séquence des trois premiers pour les placer sur le quatrième. : ABACABADABACABA. Ainsi, à mesure que le nombre de disques augmente, le nombre de coups requis augmente selon la séquence 1, 3, 7, 15, 31, 63… Pour n disques, le nombre de coups requis est de 2ⁿ– 1, ce qui explique la coïncidence numérique entre les deux supposées légendes indiennes : celle de l’inventeur des échecs et celle de la tour des 64 disques d’or du temple de Bénarès.

Comme nous l’avons également vu, la séquence de mouvements nécessaire pour déplacer une tour de trois disques correspond au chemin hamiltonien passant par les sommets d’un cube. Mais l’affaire ne s’arrête pas là (elle ne fait que commencer) : la séquence de mouvements d’une tour de quatre disques correspond au parcours hamiltonien passant par les sommets d’un tesseract (hypercube à 4 dimensions). Et ainsi de suite indéfiniment : comme l’a démontré le mathématicien DW Crowe au milieu du XXe siècle, cette correspondance vaut pour les tours de n’importe quelle hauteur et les cubes de n’importe quelle dimension : le nombre de mouvements et l’ordre dans lequel n disques doivent être déplacés de une tour de Hanoï pour les transférer sur un autre axe, correspondent exactement à la séquence directionnelle (et dimensionnelle) d’un chemin hamiltonien dans un hypercube à n dimensions.

Deux puzzles en bois conçus à la même époque par deux grands mathématiciens, le dodécaèdre de Hamilton et la tour de Hanoï de Lucas, coïncident sur une étagère d’un magasin de jouets. À première vue, il semble qu’ils n’ont rien à voir l’un avec l’autre ; mais, comme dans les feuilletons du XIXe siècle, ils finissent par découvrir qu’ils sont (topologiquement) frères.

Graphiques calligraphiques

Pour la première fois depuis neuf ans, la semaine dernière, suite à un problème technique, la section commentaires n’était pas opérationnelle, je reviens donc à il y a deux semaines. Bretos Bursó a présenté, dans les grandes lignes, sa solution à la route hamiltonienne passant par les sommets d’un dodécaèdre :

Et Salva Fuster a fait une observation intéressante sur la relation entre les graphiques et les lettres : « En pensant aux chemins eulériens et hamiltoniens, je me suis rendu compte que ni E ni H n’admettent de chemins d’un type ou d’un autre. Je suppose que le graphique le plus simple qui ne les prend pas en charge coïncide avec la lettre Y. D’ailleurs, les lettres de l’alphabet pourraient être classées en différents types de graphiques. « Combien y a-t-il de types ?

J’encourage mes lecteurs avisés à examiner les lettres (majuscules) de l’alphabet considérées comme des graphiques. Le Ñ est omis pour des raisons évidentes (il ne peut pas être considéré comme un graphique à cause du tilde) et il est recommandé de se concentrer sur une police avec un simple trait (bâton sec ou sans empattement, comme disent les typographes), comme ceci :

ABCDEFGHIJKLMNOPQRSTU VWXYZ

Vous pouvez suivre MATÉRIEL dans Facebook, X e Instagramcliquez ici pour recevoir notre newsletter hebdomadaire.