In a trivial tower of Hanoi with two discs, A and B, as we saw last week, the sequence of movements to carry out the transfer from one axis to another is ABA. In the three-disc one, A, B and C, the sequence is ABACABA. That is, first we move the three upper discs as in the three-disc tower, then we change the axis of the fourth disc, and finally we repeat the transfer of three discs to place them on the fourth. And with four discs, A, B, C and D, the process is analogous: we move the first three to another axis, we change the fourth to the free axis and we repeat the sequence of the first three to place them on the fourth: ABACABADABACABA. Therefore, as the number of disks increases, the number of moves required increases according to the sequence 1, 3, 7, 15, 31, 63… For n disks, the number of moves required is 2ⁿ– 1, which explains the numerical coincidence between the two supposed Indian legends: that of the inventor of chess and that of the tower of 64 gold discs in the temple of Benares.
As we also saw, the sequence of movements necessary to move a tower of three disks corresponds to the Hamiltonian path through the vertices of a cube. But the thing does not end there (it has only just begun): the sequence of movements for a tower of four disks corresponds to the Hamiltonian route through the vertices of a tesseract (4-dimensional hypercube). And so on and so on indefinitely: as the mathematician DW Crowe demonstrated in the mid-20th century, this correspondence holds for towers of any height and cubes of any dimensions: the number of movements and the order in which n disks must be moved from one tower of Hanoi to transfer them to another axis, correspond exactly to the directional (and dimensional) sequence of a Hamiltonian path in an n-dimensional hypercube.
Two wooden puzzles designed around the same time by two great mathematicians, Hamilton's dodecahedron and Lucas's Tower of Hanoi, coincide on a shelf in a toy store. At first glance it seems that they have nothing to do with each other; but, as in nineteenth-century soap operas, they end up discovering that they are (topologically) brothers.
calligraphic graphs
For the first time in nine years, last week, due to a technical issue, the comments section was not operational, so I'll go back to two weeks ago. Bretos Bursó sent, in outline, his solution to the Hamiltonian tour through the vertices of a dodecahedron:
And Salva Fuster made an interesting observation about the relationship between graphs and letters: “Thinking about Eulerian and Hamiltonian paths, I have realized that neither E nor H admit paths of one type or the other. I suppose that the simplest graph that does not support them coincides with the letter Y. By the way, the letters of the alphabet could be classified into different types of graphs. How many types are there?
I encourage my astute readers to examine the letters (uppercase) of the alphabet considered as graphs. The Ñ is omitted for obvious reasons (it cannot be considered a graph due to the tilde) and it is recommended to focus on a typeface with a simple stroke (dry stick or sans serif, as typographers say), like this:
ABCDEFGHIJKLMNOPQRSTU VWXYZ
You can follow SUBJECT in Facebook, x and instagramor sign up here to receive our weekly newsletter.
#tower #hypercube
