La tour, le cube et le plateau | Science

La Tour de Hanoï est un puzzle populaire conçu par le mathématicien français Édouard Lucas à la fin du XIXe siècle. Il est constitué de trois axes verticaux, sur l’un desquels sont empilés un certain nombre de disques perforés de tailles décroissantes, du plus grand au plus petit en partant du bas. Le défi consiste à déplacer tous les disques de l’axe sur lequel ils se trouvent vers l’un des deux autres, en suivant ces règles simples :

• Un seul disque peut être déplacé à la fois et pour le déplacer, tous les autres doivent être enfilés sur un axe.
• Un disque ne peut pas être placé au-dessus d’un disque plus petit.
• Seul un disque situé au sommet d’un axe peut être déplacé.

Évidemment, plus il y a de disques, plus le transfert est compliqué (dans les versions commerciales du puzzle, il y en a généralement cinq à huit). Étant donné une tour triviale de Hanoï, avec un seul disque, il est évident qu’un mouvement suffit pour déplacer ce disque vers un autre axe. Une tour à deux disques est également triviale : on transfère le plus petit sur l’un des deux axes libres, le plus grand sur l’autre axe libre, et enfin on met le plus petit sur le plus grand. Considérons maintenant une tour de trois disques, que nous appellerons, du plus petit au plus grand, A, B et C. Pour le premier mouvement, il n’y a qu’une seule possibilité : transférer le disque A sur l’un des deux axes libres. Pour le deuxième mouvement il n’y a qu’une seule option non répétitive : déplacer le disque B vers l’axe libre. Les mouvements suivants ne sont pas uniques, mais ils sont bien évidents : 3) A sur B, 4) C sur l’axe libre, 5) A sur l’axe libre, 6) B sur C, 7) A sur B. La séquence est , donc, ABACABA.

Le cube

Comme nous l’avons vu la semaine dernière, Hamilton a étudié les chemins qui portent son nom dans les solides platoniciens, qui consistent à passer par tous les sommets une et une seule fois. Dans le cas d’un cube, si l’on appelle A la direction verticale, B la direction horizontale et C la direction antéropostérieure, en partant par exemple du sommet supérieur gauche du cube et en descendant d’abord, puis vers la droite, puis vers le haut , puis en arrière et ainsi de suite jusqu’à compléter le chemin hamiltonien simple, nous verrons que la séquence directionnelle (et dimensionnelle) est ABACABA, la même que dans une tour de Hanoï à trois disques. Simple coïncidence? J’invite mes lecteurs avisés à le vérifier, en trouvant la séquence de transferts pour une tour de quatre disques, puis en recherchant un chemin hamiltonien qui passe par les sommets d’un hypercube (pour ceux qui n’ont pas d’accès direct à la quatrième dimension, une projection tridimensionnelle comme celle de la figure ci-jointe). Y a-t-il des similitudes entre les deux itinéraires ?

Le tableau

Selon une légende bien connue, l’inventeur mythique des échecs demandait au roi de l’Inde un grain de blé pour la première case de l’échiquier, deux pour la deuxième, quatre pour la troisième, huit pour la quatrième, et ainsi de suite. au carré 64. , en doublant dans chacun le nombre de grains de blé du précédent. Eh bien, ce nombre (18 446 744 073 709 551 615) est égal au nombre de transferts nécessaires pour déplacer d’un axe à l’autre tous les disques d’une tour de Hanoï comportant 64 disques, autant qu’il y a de cases sur l’échiquier. Encore une coïncidence ?

D’ailleurs, si les 64 disques sont en or et les haches sont des aiguilles en diamant, nous sommes confrontés à la légende (apocryphe) de la tour de Brahma, selon laquelle le monde finira lorsque les prêtres du temple de Bénarès auront fini de bouger. tous les disques sur un autre axe. Mais pas de panique : même si les moines assidus déplaçaient un disque par seconde sans se reposer un seul instant, l’apocalypse ne serait pas imminente.

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

_